This page presents a focused view of some of my favorite research results that I have shown with collaborators. It focuses on questions that I find natural, with elementary prerequisites. I hope it can serve as an entry point to quickly get an idea of the kind of results that I prove and the flavor of problems that I enjoy. For more information, you can also refer to a more general overview of my research, or my publication list.
Dynamic membership: Fix a regular language L. We consider the dynamic membership problem to L, where we read a word w and must decide whether w belongs to L and maintain this information under substitution updates on the word (i.e., replace the i-th position to be the letter a; the length n of the word never changes). This can always be done in time O(log|w|) per character, but for some fixed languages we can improve on this bound (e.g., O(1)). What are the possible regimes?
Query complexity with promises: When you fix a regular language L, and you are given a word w, how many positions of w do you need to read to know whether w∈L? There are languages for which O(1) positions suffice (e.g., "the word ends with b"), and otherwise you need to query Ω(|w|) positions. But what about the promise version where you also promised that w∈L′ for a fixed regular language L′?
Enumerating words with few changes: Consider a regular language L. We want to enumerate the words of L with constant delay, i.e., producing each word exactly once and obtaining it by performing a small number of changes on the preceding word. For some languages this is not possible, for instance a∗+b∗. For others it can be done, e.g., for a∗ (e.g., with the infinite sequence ϵ, a, aa, ...), for (a+b)∗ (using a form of Gray code), or for a∗b∗ (using the Cantor pairing function that gives a bijection between N2 and N). For which regular languages is this possible?
Infix enumeration: Given a word w of length n and a regular language provided as a regular expression e of length m, we want to efficiently enumerate all factors of w that match e. The naive algorithm for this is in O(n2m), simply by doing state-set simulation of a nondeterministic automaton for e from each starting point in w. Can we avoid the quadratic dependency in the word by measuring complexity as a function of the input?
Probabilistic membership: Fix a language L over Σ={0,1} and read as input a probabilistic word w, i.e., each w[i] is a rational number indicating the probability that w has a 1 at position i (all positions being independent). We want to compute the probability that a word drawn according to the distribution of w will belong to L. This can be computed in PTIME if L is a regular language, but does this generalize to context-free languages?
Efficient subsequence and supersequence matching: When you are given a deterministic finite automaton A and a word w, you can test if A accepts w in time O(|w|). By contrast, when A is nondeterministic, you can do O(|A|⋅|w|) by state-set simulation and this is conditionally optimal. But what if you just want to know whether some subsequence of w satisfies A? or whether some supersequence of w satisfies A?
Counting subgraphs: Fix a certain property P on directed graphs. We are given as input a directed graph G, and want to count how many subgraphs of G satisfy the property P. We can always do so by going over all subgraphs, but there are exponentially many (there are 2m if G has m edges), so we want to find the properties P admitting more efficient algorithms. One kind of requirement that we can ask of P is closure under homomorphisms, i.e., if a graph G1 has property P and it admits a homomorphism to a graph G2 then G2 must also have property P. (For instance, the property "G contains a directed triangle x→y→z→x" is closed under homomorphisms provided x and y and z are not required to be mapped to distinct vertices.) Can we efficiently count the number of subgraphs satisfying such a property?
Edge-minimum walks of modular length: Fix two integers p and q. Given a directed graph G and two vertices s and t, we want to know if there is a walk in G from s to t (i.e., a path which may revisit some edges and vertices) whose length is pmodq. It is possible to find the shortest such walk in polynomial time (by making q copies of the graph, routing the edges appropriately, and computing a shortest path). However, what if we want the edge-minimum such walk, i.e., a walk using the fewest number of distinct edges?
Enumerating walks with few changes: Say you want to enumerate the infinite list of the walks over a directed graph G, each walk being produced exactly once, and any two consecutive walks differing by a small number of push-pop edits (adding or removing edges at the beginning or end of the walk). When can such an enumeration be achieved?
Counting matchings: What are the families F of undirected graphs on which we can tractably perform weighted counting of the matchings? More precisely, fixing a family F, given a graph G of F and a function π giving a probability to each edge of G (assuming independence across edges), we want to determine the probability that a random subgraph of G drawn according to π is a matching, i.e., does not contain two edges sharing an incident vertex. It is well-known that the task is tractable if the treewidth of the graphs in F is bounded by a constant. Is the task tractable for other families of graphs?
Resilience for regular walks: Fix a regular language L on alphabet Σ. We receive as input a directed graph G whose edges are labeled with letters of Σ. The resilience problem asks us to find the smallest number of edges to remove from G so that it no longer has any walk achieving a word of L; this problem can be seen as a generalization of the minimum cut problem in directed graphs (essentially corresponding to the language ab∗c). What is the complexity of this problem, depending on the fixed language L?
Topological sorting with regular constraints: Fix a regular language L on alphabet Σ. We receive as input a directed acyclic graph G whose vertices are labeled with letters from Σ. Every topological sort of G gives a word over Σ (of length n if G has n vertices). We want to know, given G, whether it admits a topological sort forming a word from L. What is the complexity of this problem, depending on the fixed language L?
Universal-tape Turing machines: Consider a Turing machine running on a tape of length n on the alphabet Σ={0,1} (initially the tape is 0n and the head is to the left). We want the machine to put the tape in all the 2n possible configurations that it can take, and output each of them exactly once (by visiting special output states), with a constant bound on the delay between two consecutive outputs, and then terminate. Is this possible, or must such a machine necessarily loop or fail to visit all possible tape configurations?
Enumerating satisfying assignments: Given an ordered binary decision diagram (OBDD), can we efficiently enumerate its satisfying assignments, with as little time as possible between any two successive assignments?