key: cord-0043818-7ke0z029
authors: de Oliveira Oliveira, Mateus; Wehar, Michael
title: On the Fine Grained Complexity of Finite Automata Non-emptiness of Intersection
date: 2020-05-26
journal: Developments in Language Theory
DOI: 10.1007/978-3-030-48516-0_6
sha: 11b337abe19cb271d6f1d887141d9bab7527e399
doc_id: 43818
cord_uid: 7ke0z029

We study the fine grained complexity of the DFA non-emptiness of intersection problem parameterized by the number k of input automata (k -DFA-NEI). More specifically, we are given a list [Formula: see text] of DFA’s over a common alphabet [Formula: see text], and the goal is to determine whether [Formula: see text]. This problem can be solved in time [Formula: see text] by applying the classic Rabin-Scott product construction. In this work, we show that the existence of algorithms solving k -DFA-NEI in time slightly faster than [Formula: see text] would imply the existence of deterministic sub-exponential time algorithms for the simulation of nondeterministic linear space bounded computations. This consequence strengthens the existing conditional lower bounds for k-DFA-NEI and implies new non-uniform circuit lower bounds.

In the DFA non-emptiness of intersection problem (DFA-NEI), the input consists of a list A 1 , ..., A k of DFA's over a common alphabet Σ, and the goal is to determine whether the intersection of the languages L(A 1 ), ..., L(A k ) is nonempty. When no restriction is imposed on the input, DFA-NEI is a PSPACEcomplete problem [18] . Nevertheless, the classic Rabin-Scott product construction for finite automata yields a simple algorithm that solves DFA-NEI in time O(n k ) where n is the number of states and k is the number of input automata. Therefore, for a fixed number of input automata, the problem can be solved in polynomial time.

In this work, we study the fine grained complexity of DFA-NEI parameterized by the number of input automata k. For clarity, we refer to this parameterized version as k-DFA-NEI. Interestingly, Rabin and Scott's six-decades-old time O(n k ) algorithm for k-DFA-NEI remains unimproved, and in particular, time O(n 2 ) is still the best we can get for deciding non-emptiness of intersection for two DFA's. Kasai and Iwata [17] are believed to be the first to provide conditional lower bounds for k-DFA-NEI. They showed that k-DFA-NEI requires deterministic time Ω(n (k−2)/2 ) under the conjecture that NSPACE[k · log n] ⊂ DTIME[n k−ε ] for all ε > 0.

Almost two decades later, Karakostas, Lipton, and Viglas showed that faster algorithms for certain variants of k-DFA-NEI would imply both faster algorithms for certain NP-hard problems and new complexity class separations [16] . In particular, they showed that an algorithm solving k-DFA-NEI in time n o(k) would have two consequences. First, this would imply that the well studied subset sum problem can be solved in time O(2 ε·n ) for every ε > 0. Second, this would imply that NTIME[n] ⊆ DTIME [2 o(n) ]. They also showed some remarkable consequences of the existence of algorithms solving k-DFA-NEI in time s · r o(k) where s is the number of states in the largest input automaton and r is the number of states in the second largest input automaton. In particular, such an algorithm would imply that NSPACE[O(log s)] ⊂ DTIME[s 1+ ] for all > 0, which would further imply that P = NL. Additionally, by padding, we would also have NSPACE[s] ⊆ DTIME [2 o(s) ]. It is worth noting that this last result strongly requires that the runtime has only a marginal dependence on the size s of the largest automaton. Further, this last result is in a similar spirit as conditional lower bounds for weighted satisfiability problems from [8] [9] [10] .

It was shown by Fernau and Krebs [12] , and independently in [30] , that an algorithm solving k-DFA-NEI in time n o(k) would contradict the celebrated exponential time hypothesis (ETH). Using a refinement of the proof technique introduced in [16] , it was shown in [29, 30] that if k-DFA-NEI can be solved in time n o(k) , then P = NL. Additional results on the parameterized complexity of non-emptiness of intersection for DFA's are presented in [17, 19, 26] and results on the fine grained complexity of non-emptiness of intersection specifically for two and three DFA's are presented in [23] .

Finer Simulations for Nondeterministic Linear Space. Our first result (Theorem 1) provides a finer reduction from the problem of simulating a nondeterministic space bounded Turing machine to k-DFA-NEI. The following two corollaries of Theorem 1 fill in some gaps in the literature related to nonemptiness of intersection. In this work, NSPACE[n] denotes the class of functions computable by 2-tape Turing Machines over a binary alphabet using at most n bits on its work tape. As mentioned in the first part of the introduction, the conclusion that NSPACE[n] ⊆ DTIME [2 o(n) ] can be obtained from the results in [16] under the assumption that there exists an algorithm for k-DFA-NEI running in time s · r o(k) where s is the size of the largest automaton and r is the size of the second largest automaton. Corollary 1.1 relaxes this assumption to the existence of an algorithm running in time n o(k) , with no regard to the way in which the sizes of the input automata compare with each other. We observe that the same assumption as ours was shown in [16] to imply that NTIME[n] ⊆ DTIME [2 o(n) ]. Therefore, we improve the consequence in [16] from NTIME[n] ⊆ DTIME [2 o(n) ] to NSPACE[n] ⊆ DTIME [2 o(n) ]. Corollary 1.2 states that for each k > 1, any additive constant improvement on the running time of the Rabin-Scott algorithm for k-DFA-NEI would imply the existence of faster than state-of-the art algorithms for the simulation of nondeterministic linear space bounded computations. In particular, an algorithm solving non-emptiness of intersection for two DFA's in time O(n 2−ε ), for some ε > 0, would imply that NSPACE[n + o(n)] ⊆ DTIME[2 (1−δ)n ] for some δ > 0.

In the satisfiability problem for Boolean formulas (SAT), we are given a Boolean formula. The goal is to determine if there exists an assignment that satisfies the formula. It is common to restrict the inputs for SAT to formulas in conjunctive normal form (CNF-SAT). Further, it is common to restrict the inputs for SAT to formulas in conjunctive normal form with clause width at most k (k-CNF-SAT) for some fixed number k.

The Exponential Time Hypothesis (ETH) asserts that for some ε > 0, 3-CNF-SAT cannot be solved in time (1 + ε) n [14] . The strong exponential time hypothesis (SETH) asserts that for every ε > 0, there is a large enough integer k such that k-CNF-SAT cannot be solved in time (2−ε) n [7, 14, 15] . ETH has been used to rule out the existence of subexponential algorithms for many decision problems [14] , parameterized problems [8, 20] , approximation problems [22] , and counting problems [11] . On the other hand, SETH has been useful in establishing tight lower bounds for many problems in P such as Edit Distance [3] , k-Dominating Set [24] , k-DFA-NEI [30] , and many other problems [2, 27, 33] .

Our next results state that slightly faster algorithms for k-DFA-NEI would contradict much stronger versions of ETH and SETH. First, we show that if there exists k ≥ 2 such that k-DFA-NEI can be solved in time O(n k−ε ) for some ε > 0, then satisfiability for n-variable Boolean formulas of size 2 o(n) can be solved in time O(2 (1−δ)n ) for some δ > 0 (Corollary 2). The inexistence of such fast algorithms for satisfiability for n-variable Boolean formulas of subexponential size is a safer assumption than SETH. Going further, we show that if k-DFA-NEI can be solved in time n o(k) , then satisfiability for n-input fanin-2 Boolean circuits of depth O(n) and size 2 o(n) can be solved in time 2 o(n) (Corollary 3). We note that this consequence is stronger than the existence of algorithms solving CNF-SAT in sub-exponential time. Indeed, CNF formulas of polynomial size are a very weak model of computation, which are unable, for instance, to compute the parity of their input bits [13] . On the other hand, circuits of linear depth can already simulate complicated cryptographic primitives. Therefore, the inexistence of satisfiability algorithms for such circuits is a safer assumption than ETH.

Non Uniform Circuit Lower Bounds. Finally, from the results mentioned above together with results obtained within the context of Williams' algorithms versus lower bounds framework [1, 31, 32] (as well as [4] ), we infer that faster algorithms for k-DFA-NEI would imply non-uniform circuit lower bounds that are sharper than what is currently known. In particular, an algorithm running in time n o(k) for k-DFA-NEI would imply that there are problems in E NP that cannot be solved by non-uniform fan-in-2 Boolean circuits of linear depth and sub-exponential size (Corollary 4). We note that currently it is still open whether every problem in E NP can be solved by non-uniform fan-in-2 Boolean circuits of linear size. Additionally, we show that an algorithm running in time O(n 2−ε ) for 2-DFA-NEI would imply that there are problems in E NP that cannot be solved by non-uniform Boolean formulas of sub-exponential size (Corollary 5).

Further, we have that even polylogarithmic improvements for the running time of algorithms solving 2-DFA-NEI would imply interesting lower bounds. More specifically, if 2-DFA-NEI can be solved in time O(n 2 / log c n) for every c > 0, then there are functions that can be computed in NTIME [2 O(n) ] but not by non-uniform NC 1 circuits.

Analogous conditional non-uniform circuit lower bounds have been obtained in [1] under the assumptions that the Edit Distance problem can be computed in time O(n 2−ε ) for some ε > 0 and in time O(n 2 / log c n) for every c ≥ 1. It is worth noting that Theorem 5 which establishes conditional lower bounds for fan-in-2 Boolean circuits of linear depth and sub-exponential size is not explicitly stated in [1] and no parallel to the associated conditional lower bound for k-DFA-NEI is given for Edit Distance.

In this section we provide a reduction from the problem of simulating 2-tape Turing machines to DFA-NEI. For any k, the reduction in Theorem 1 outputs k DFA's each with at most O(m 2 ·n·σ 1+c ·2 σ k ) states where m denotes the number of states in the Turing machine, n denotes the input string length, σ denotes the amount of space on the binary work tape, and c denotes the maximum number of occurrences of a special delimiter symbol # that can simultaneously appear on the work tape during the computation. The parameter c is a constant associated with the Turing machine and is independent of the parameters n and σ.

2-tape Turing Machines: A 2-tape Turing machine with binary alphabet is a machine with a two-way read-only input tape and a two-way binary work tape.

More formally, it is a tuple M = (Q, {0, 1}, c, q 0 , F, δ) where Q is a set of states, c is the maximum number of occurrences of special delimiter symbol #, q 0 ∈ Q is an initial state, F is a set of final states, and

is a partial transition function that assigns to each triple

We say that a tuple

is an instruction that sets the machine to state q, moves the input head from position p to position p + d, moves the work head from position p to position p + d , and writes symbol w at position p on the work tape. The transition function δ specifies that if the machine M is currently at state q, reading symbol b 1 on the input tape and symbol b 2 on the work tape, then the next instruction of the machine must be an element of the set δ(q, b 1 , b 2 ).

is the position of M 's work tape head, and y ∈ ({0, 1} ∪ {#}) σ is the binary string (containing at most c special delimiter symbols) corresponding to the first σ symbols on the work tape of M .

satisfying the following conditions.

2. q 0 is the initial state of M , y 0 = 0 σ , meaning that the work tape is initialized with zeros, and h 0 = h 0 = 1, meaning that the input tape head and work tape head are in the first position of their respective tapes. 

, and y i is obtained from y i−1 by substituting w i for the symbol

, and by leaving all other symbols untouched. Intuitively, this means that the configuration at time i is obtained from the configuration at time i − 1 by the application of the transition (q i , d i , d i , w i ). 5. For each i ∈ {0, 1, ..., k}, y i contains at most c occurrences of the special delimiter symbol #.

We say that the sequence

that induces a configuration sequence S as above is a space-σ instruction sequence for M on input x. We say that I is accepting if q k ∈ F .

As suggested in [17] , the technique provided in the proof of Proposition 3 from [25] can be applied to remove the special delimiter symbol from the work tape by increasing the Turing machine's state and space complexities. However, without a formal proof in the literature of the stated result from [17] and because it is not required in our work, we decided to refrain from using it. Consider splitting the work tape of M into k equal sized blocks each consisting of σ k work tape cells. A block-i space-σ configuration for M on input x consists of the state, input tape head, work tape head, the contents of the work tape from position lbound i := (i − 1) · σ k + 1 to position rbound i := i · σ k , and all c positions of the occurrences of special delimiter symbol #. We construct k DFA's A 1 , A 2 , ..., A k where each DFA A i keeps track of the current block-i space-σ configuration for M on input x. The DFA's read in space-σ instructions one at a time and transition accordingly where each instruction is encoded as a unique bit string of length O(log(m)).

The start state of DFA A i represents the block-i space-σ configuration (q 0 , 1, 1, 0 σ k ) where q 0 is the start state of M . Further, a state representing a block-i space-σ configuration (q j , h j , h j , contents j ) is accepting if q j is a final state of M . Suppose that the DFA A i is currently at a state representing a blocki space-σ configuration (q j , h j , h j , contents j ) and reads in a space-σ instruction (q, d, d , r, r , w) . The DFA A i transitions to a state representing a block-i space-σ configuration (q j+1 , h j+1 , h j+1 , contents j+1 ) if:

Collectively the DFA's determine whether the input string encodes an accepting space-σ instruction sequence for M on x. Therefore Remark 2. The preceding simulation is sufficient for our purposes. However, we suggest that it could be refined by having only one DFA keep track of the Turing machine's tape heads. When σ = O(log(n)), such a refinement could be used to obtain a tighter connection between k-DFA-NEI and nondeterministic logspace. 

In this section we apply results obtained in Theorem 1 to show that even a slight improvement in running time of the classic algorithm for non-emptiness of intersection for finite automata would yield faster than state of the art algorithms for satisfiability for Boolean formulas and Boolean circuits. Therefore, this result implies that the impossibility of obtaining better algorithms for non-emptiness of intersection for k finite automata can be based on assumptions that are safer than the exponential time hypothesis (ETH). An analogous result is proven with respect to non-emptiness of intersection for a constant number of finite automata (say two). We will show that the existence of algorithms that are faster than time O(n 2−ε ) for non-emptiness of intersection for 2 DFA's would contradict assumptions that are safer than the strong exponential time hypothesis (SETH). We note that the endeavour of basing lower bounds for algorithms in P on assumptions that are safer than ETH or SETH has been pursued before [1] . In this work, we obtain lower bounds using assumptions like those used in [1] , with the advantage that our reductions are simpler. Therefore, we believe that the techniques employed here provide a cleaner framework that can potentially be used to strengthen the analysis of the fine grained complexity of other algorithmic problems in P. Finally, by applying Williams' algorithms versus lower bounds framework, we are able to show that faster algorithms for non-emptiness of intersection for finite automata would also imply non-uniform circuit lower bounds that are much better than those that are currently known.

Proof. The machine uses n tape cells to guess an assignment x ∈ {0, 1} n to the input variables. Subsequently, using O(log s) work tape cells, the machine evaluates the Boolean formula from the input tape on the guessed assignment from the work tape. This evaluation problem is referred to as the Boolean formula value problem (BFVP) and has been shown to be solvable in space O(log s) on formulas of size s in [6, 21] . Storing both the assignment and the formula evaluation on the same work tape, it will be necessary to use a fixed number of occurrences of the delimiter symbol # as left/right tape markers, a delimiter between assignment and formula evaluation, and markers for remembering the position in the formula evaluation and the assignment when the work tape head moves from formula evaluation to assignment or vice versa.

By combining Theorem 1 with Lemma 1, we obtain the following. Proof. Suppose that there exists k ≥ 2 and ε > 0 such that k-DFA-NEI can be solved in time O(n k−ε ). Let a n-variable Boolean formula φ of size s be given. By Theorem 1 and Lemma 1, we can reduce satisfiability for φ to non-emptiness of intersection for k DFA's each with poly(s) · 2 n k states. Therefore, by assumption, we can determine whether φ has a satisfying assignment in time s O(k) · 2 k−ε k ·n . It follows that satisfiability for n-variable Boolean formulas of size s is solvable in time poly(s) · 2 n(1−δ) for some δ > 0.

It was shown in [30] that if there exists some k ≥ 2 and ε > 0 such that k-DFA-NEI can be solved in time O(n k−ε ), then SETH is false. The following corollary improves this result by showing a much stronger consequence. The corollary follows directly from Theorem 2.

If there exists k ≥ 2 and ε > 0 such that k-DFA-NEI can be solved in time O(n k−ε ), then satisfiability for n-variable Boolean formulas of size 2 o(n) can be solved in time O (2 n(1−δ) ) for some δ > 0.

Note that while CNF's of bounded width and polynomial size are a very weak computational model, Boolean formulas of sub-exponential size can already simulate any circuit in the class NC. Therefore, the consequence of Corollary 2 would contradict the NC-SETH hypothesis, a more robust version of SETH which states that satisfiability for circuits of polynomial size and polylogarithmic depth cannot be solved in time O (2 n(1−δ) ) for any δ > 0 [1] . In the next subsection we show that the existence of an algorithm running in time n o(k) for k-DFA-NEI would imply faster satisfiability algorithms for even larger classes of circuits.

In the circuit value problem (CV), we are given a n-input fan-in-2 Boolean circuit C and a string x ∈ {0, 1} n . The goal is to determine whether the circuit C(x), obtained by initializing the input variables of C according to x, evaluates to 1. Let the size of C denote the number of gates of C. The next lemma, which is a classic result in complexity theory [5] , states that the circuit value problem for circuits of depth d and size s can be solved in space O(d) + O(log s) on a 2-tape Turing machine. [5] ). There is a deterministic 2-tape Turing machine M with binary alphabet, that takes as input a pair C, x where x is a string in {0, 1} n and C is a n-input fan-in-2 Boolean circuit of depth d and size s, and determines, using at most O(d)+O(log s) work tape cells, whether C(x) evaluates to 1.

In the satisfiability problem for Boolean circuits, we are given a n-input fanin-2 Boolean circuit C. The goal is to determine whether there exists a string x ∈ {0, 1} n such that C(x) evaluates to 1. As a consequence of Lemma 2, we have that satisfiability for Boolean circuits can be decided by a nondeterministic 2-tape Turing machine using at most n + O(d) + O(log s) tape cells.

There is a nondeterministic 2-tape Turing machine M with binary alphabet and a fixed number of delimiter symbol # occurrences, that takes as input a n-input fan-in-2 Boolean circuit C of depth d and size s, and determines, using at most n + O(d) + O(log s) tape cells, whether C is satisfiable.

By combining Theorem 1 with Lemma 3, we obtain the following.

where k is allowed to depend on n, d, and s.

Proof. Suppose that k-DFA-NEI can be solved in time O(n f (k) ). Let a ninput fan-in-2 Boolean circuit C of depth d and size s be given. By Theorem 1 and Lemma 3, for any k, we can reduce satisfiability for C to non-emptiness of intersection for k DFA's each with poly(s) · 2 n+O(d) k states. Therefore, by assumption, we can determine whether C has a satisfying assignment in time ) . It follows that satisfiability for n-input fan-in-2 Boolean circuits of depth d and size s is solvable in the desired time.

It was shown in [12, 30] that if k-DFA-NEI can be solved in time n o(k) , then ETH is false. The following corollary improves this result by showing a much stronger consequence. The corollary follows directly from Theorem 3. Note that the consequence in the preceding corollary is stronger than ETH because circuits of linear depth and sub-exponential size are a stronger computational model than formulas in conjunctive normal form.

Corollaries 2 and 3 lead us to the following questions.

-What are the barriers (beyond ETH) to solving satisfiability for fan-in-2

Boolean circuits of depth O(n) and size 2 o(n) more efficiently? -What are the barriers (beyond SETH) to solving satisfiability for Boolean formulas of size 2 o(n) more efficiently? -What are the barriers to solving satisfiability only slightly faster for Boolean formulas of polynomial size?

Below, we investigate the preceding questions and reference recent works [1, 4, 31, 32] that connect satisfiability problems to non-uniform circuit complexity lower bounds. From these connections, we observe that faster algorithms for k-DFA-NEI would imply new non-uniform circuit complexity lower bounds.

Barriers Beyond ETH. The following is a slightly modified restatement of a technical theorem from [1] (with related results in [4, 31, 32] ) that connects circuit satisfiability to non-uniform circuit complexity lower bounds for E NP . Recall that E NP is the class of functions that can be computed by Turing machines that operate in time 2 O(n) with the help of an NP oracle. Note that the strings that are passed to each call of the oracle may have size up to 2 O(n) . [1] ). Let S(n) be a time constructible and monotone non-decreasing function such that n ≤ S(n) ≤ 2 o(n) . Let C be a class of circuits. Suppose there is a SAT algorithm for n-input circuits which are arbitrary functions of three O(S(n))-size circuits from C, that runs in time O(2 n /(n 10 · S(n))). Then E NP does not have S(n)-size circuits from C.

Notice that if we take three circuits of linear depth and sub-exponential size and combine their outputs using a constant number of additional gates, then the resulting circuit still has linear depth and sub-exponential size. Therefore, a satisfiability algorithm running in time 2 o(n) for n-input fan-in-2 Boolean circuits of linear depth and sub-exponential size would imply that there are functions in E NP that cannot be computed by such circuits. This would be a significant consequence in complexity theory since to date it is not even known whether all functions in E NP can be computed by non-uniform circuits of linear size. In view of our discussion, Theorem 5 directly follows from Theorem 4, but is not explicitly stated in [1] . By combining the preceding theorem with Corollary 3, we obtain the following. Barriers Beyond SETH. Next, we look at another known result that connects formula satisfiability to non-uniform formula complexity lower bounds for E NP . The following theorem is similar to Corollary 1.1 in [1] and directly follows from Theorem 4. By combining the preceding theorem with Corollary 2, we obtain the following. [1] ). Suppose that there is a satisfiability algorithm for bounded fan-in formulas of size n r running in time O(2 n /n r ), for each constant r > 0. Then NTIME [2 O(n) ] is not contained in non-uniform NC 1 .

By combining the preceding theorem with Theorem 1 and Lemma 1, we obtain the following.

If k-DFA-NEI can be solved in time O(n k /(log n) c ) for every c > 0, then NTIME [2 O(n) ] is not contained in non-uniform NC 1 .

Proof. Suppose that there exists k ≥ 2 such that k-DFA-NEI can be solved in time O(n k /(log n) c ) for every c > 0. By combining Theorem 1 and Lemma 1, it follows that for all r > 0, satisfiability for n-variable Boolean formulas of size n r can be reduced to intersecting k DFA's with at most poly(n) · 2 n k states where k and r are treated as constants. Therefore, satisfiability for n-variable Boolean formulas of size n r can be solved in time for all c > 0 and some constant d that is independent of c. If we set c = d · r, then we have that satisfiability for Boolean formulas of size n r can be solved in time O(2 n /n r ). It follows that satisfiability for Boolean formulas of size n r can be solved in time O(2 n /n r ) for all r > 0. Moreover, by Theorem 7, it follows that NTIME [2 O(n) ] does not have non-uniform NC 1 circuits.

Notice that if we set k = 2 in the preceding corollary, then it follows that if 2-DFA-NEI can be solved in time O(n 2 /(log n) c ) for every c > 0, then NTIME [2 O(n) ] is not contained in non-uniform NC 1 .

We analyzed the fine grained complexity of the non-emptiness of intersection problem parameterized by the number of input DFA's (k-DFA-NEI). Despite the fact that this problem has been studied for at least six decades, the fastest known algorithm for k-DFA-NEI is still the O(n k ) time algorithm obtained by a direct application of the classic Rabin-Scott product construction.

The lack of progress in the task of developing a faster algorithm for k-DFA-NEI motivated the search for evidence supporting the possibility that substantially faster algorithms for this problem do not exist. In this work, we have simplified and strengthened several previous conditional lower bounds for k-DFA-NEI under a unified perspective. In particular, we have shown that if k-DFA-NEI can be solved in time n o(k) then NSPACE[n] ⊆ DTIME [2 o(n) ]. Additionally, we have shown that solving non-emptiness of intersection for two DFA's in time O(n 2−ε ) for some ε > 0 would imply that NSPACE[n + o(n)] ⊆ DTIME[2 (1−δ)n ] for some δ > 0. Further, we have unveiled several connections between k-DFA-NEI and non-uniform circuit complexity theory. In particular, we have shown that even improving non-emptiness of intersection for two DFA's by a log c n factor for every c > 0 would imply non-uniform NC 1 circuit lower bounds.

Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made

Popular conjectures imply strong lower bounds for dynamic problems

Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)

Short PCPs with projection queries

On relating time and space to size and depth

Algorithms for boolean formula evaluation and for tree contraction

The complexity of satisfiability of small depth circuits

Tight lower bounds for certain parameterized NP-hard problems

W -Hardness under linear FPT-reductions: structural properties and further applications

Strong computational lower bounds via parameterized complexity

Exponential time complexity of the permanent and the Tutte polynomial

Problems on finite automata and the exponential time hypothesis

Parity, circuits, and the polynomial-time hierarchy

On the complexity of k-SAT

Which problems have strongly exponential complexity?

On the complexity of intersecting finite state automata and NL versus

Gradually intractable problems and nondeterministic logspace lower bounds

Lower bounds for natural proof systems

The emptiness problem for intersections of regular languages

Slightly superexponential parameterized problems

Log space recognition and translation of parenthesis languages

On the optimality of planar and geometric approximation schemes

Intersection non-emptiness and hardness within polynomial time

On the possibility of faster SAT algorithms

Relating refined space complexity classes

The parameterized complexity of intersection and composition operations on sets of finite-state automata

Exact algorithms and strong exponential time hypothesis

Intersection emptiness for finite automata. Honors thesis

Hardness results for intersection non-emptiness

On the complexity of intersection non-emptiness problems

Non-uniform ACC circuit lower bounds

Improving exhaustive search implies superpolynomial lower bounds

Hardness of easy problems: basing hardness on popular conjectures such as the strong exponential time hypothesis