# Open problems on the frontiers of TCS

In the thread Major unsolved problems in theoretical computer science?, Iddo Tzameret made the following excellent comment:

I think we should distinguish between major open problems that are viewed as fundamental problems, like $P\neq NP$, and major open problems which will constitute a technical breakthrough, if solved, but are not necessarily as fundamental, e.g., exponential lower bounds on $AC^0(6)$ circuits (i.e., $AC^0+\mod 6$ gates). So we should possibly open a new community wiki entitled "open problems in the frontiers of TCS", or the like.

Since Iddo did not start the thread, I thought I'll start this thread.

Often the main open problems of fields are known to researchers working in related fields, but the point at which current research is stuck is unknown to outsiders. The quoted example is a good one. As an outsider, it is clear that one of the biggest problems in circuit complexity is to show that NP requires super-polynomial size circuits. But outsiders may not be aware that the current point at which we are stuck is trying to prove exponential lower bounds for AC0 circuits with mod 6 gates. (Of course there could be other circuit complexity problems of similar difficulty which would describe where we are stuck. This is not unique.) Another example is to show time-space lower bounds for SAT better than n1.801.

This thread is for examples like this. Since it is hard to characterize such problems, I'll just give some examples of properties that such problems possess:

1. Will often not be the big open problems of the field, but will be a big breakthrough if solved.
2. Usually not unbelievably hard, in the sense that if someone told you that the problem was solved yesterday, this would not be too hard to believe.
3. These problems will also often have numbers or constants that are not fundamental, but they arise because this happens to be where we are stuck.
4. The problem at the frontiers of a particular field will keep changing from time to time, as opposed to the biggest problem in the field, which will remain the same for many many years.
5. Often these problems are the easiest problems that are still open. For example we don't have exponential lower bounds for AC1 either, but since $AC^0$[6] is included in that class, it is formally easier to show lower bounds for $AC^0$[6], and thus that is at the current frontier of circuit complexity.

Please post one example per answer; standard big-list and CW conventions apply. If someone can explain what types of problems we're looking for better than I have, please feel free to edit this post and make appropriate changes.

EDIT: Kaveh suggested that answers also include an explanation as to why a given problem is at the frontier. For example, why are we looking for lower bounds against AC0[6] and not AC0[3]? The answer is that we do have lower bounds against AC0[3]. But then the obvious question is why do those methods fail for AC0[6]. It would be nice if answers could explain this too.

• Is this only about complexity theory ? I'm asking because on the cited thread, there are many problems that would fit the stated description of this question, and also have no direct bearing on P vs NP (edit distance, matrix multiplication, and so on) – Suresh Venkat Sep 6 '10 at 5:15
• I meant to include all of TCS. I only used complexity examples because that's what I am familiar with. There will be some overlap with that thread since people posted major open problems and problems at the frontier of our knowledge. – Robin Kothari Sep 6 '10 at 5:40
• I think that this is an excellent question, much more interesting and useful than the one about "major open problems". Hence I decided to start a bounty, even though this wasn't my question. I'm not 100% sure what happens if I give a bounty to a CW answer, but we'll see it in 7 days. :) – Jukka Suomela Sep 8 '10 at 16:34
• Good idea. I'm also curious to know what happens if you award a bounty to a CW answer. – Robin Kothari Sep 8 '10 at 20:08
• And the bounty went to the current top-ranking answer. (Seems that it worked as expected; the user who posted the CW answer got +50 rep.) – Jukka Suomela Sep 14 '10 at 21:51

Here are three in shortest paths research:

$1$. Is there a linear time algorithm for single source shortest paths in directed graphs with nonnegative weights, at least in the word-RAM model of computation? Note that a linear time algorithm exists for undirected graphs (see Thorup's paper). Based on that, Hagerup has a runtime of $O(n+m\log w)$ for directed graphs with weights bounded by $2^w$. Is there a faster algorithm?

$2$. Is there an $O(n^\omega$ polylog $n)$ algorithm for all pairs shortest paths in unweighted directed graphs? ($\omega<2.376$ is the exponent of matrix multiplication) The current best runtime is $O(n^{2.575})$ by Zwick, and for undirected graphs the problem can be solved in $O(n^\omega$ polylog $n)$.

(Are the directed problems actually harder?)

$3$. Is there an $O(n^{2.9})$ algorithm for all pairs shortest paths in $n$-node graphs with weights in {$0,\ldots,n$}? Or, is there a reduction from the general all pairs shortest paths problem to this restriction?

This is already mentioned in the question:

## Open:

Separate $EXP^{NP}$ from $AC^0_2[6]$ ($AC^0[6]$ circuits of depth 2). (see the update below)

[Nov. 11, 2010] Separate $EXP$ from $AC^0_2[6]$. Separate $EXP^{NP}$ from $TC^0$.

## Known:

1. [Alexander Razborov 1987 - Roman Smolensky 1987] $MOD_m$ is not in $AC^0[p^k]$ if $p$ is a prime and $m$ is not a power of $p$.

2. [Arkadev Chattopadhyay and Avi Wigderson 2009] Let m, q be co-prime integers such that m is square-free and has at most two prime factors. Let C be any circuit of type $MAJoGoMOD^A_m$ where $G$ is either $AND$ or $OR$ gate and the $MOD_m$ gates at the base have arbitrary accepting sets. If C computes $MOD_q$ then the top fan-in, and hence the circuit size, must be $2^{{\Omega(n)}}$.

The later result is based on obtaining exponentially small correlation bound of $MOD_q$ function with depth-2 subcircuits and estimating exponential sums involving low degree polynomials.

Obstacles: ?

### Update [Nov. 10, 2010]

A paper by Ryan Williams seems to have settled this open problem using methods which seem to be essentially different from those mentioned above:

[Ryan Williams 2010] $E^{NP}$ does not have non-uniform $ACC^0$ circuits of size $2^{n^{o(1)}}$.

References:

• A. A. Razborov. Lower bounds on the size of bounded depth networks over a complete basis with logical addition (Russian), in Matematicheskie Zametki, 41(4):598–607, 1987. English Translation in Mathematical Notes of the Academy of Sciences of the USSR, 41(4):333–338, 1987.

• R. Smolensky. Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In STOC, pages 77–82. ACM, 1987.

• Arkadev Chattopadhyay and Avi Wigderson. Linear Systems over Composite Moduli, FOCS 2009

• Ryan Williams. Non-Uniform ACC Circuit Lower Bounds, 2010, draft (submitted?).

• Is NP the largest class not known to strictly include $AC^0$[6]? – Robin Kothari Sep 6 '10 at 4:57
• I guess $AC^0$[6] here refers to the non-uniform version of the class (else it would be strictly contained in EXP since it is contained in P). Perhaps someone can add the current state of knowledge for the uniform version too. – Robin Kothari Sep 6 '10 at 5:45
• To clarify: Whether lower bounds are known for depth 2 $AC^0$6$$ circuits depends crucially on the exact definition of $MOD_6$ gates. If we define (as is mostly done) $MOD_6(x)=1$ if and only if $\sum x_i \not\equiv 0 \pmod 6$ then lower bounds are known. We get into open question territory by allowing "generalized" acceptance criteria, i.e $MOD_6^A$ gates that are 1 if the sum modulo 6 is in $A$ for some $A \subseteq \{0,\dots,5\}$. – Kristoffer Arnsfelt Hansen Sep 6 '10 at 22:29
• One additional point: if you increase the depth from 2 to 3, then the distinction between $MOD_6$ gates no longer matters... no lower bounds known for either gate type. – Ryan Williams Oct 13 '10 at 7:51
• Now this one is settled by Ryan: cs.cmu.edu/~ryanw/acc-lbs.pdf. Congratulations!!! – Hsien-Chih Chang 張顯之 Nov 10 '10 at 2:31

Let CNF-SAT be the problem of determining whether a given CNF formula is satisfiable (no restrictions on the width of clauses).

Is CNF-SAT on $n$ variables and $m$ clauses solvable in $2^{\delta n} poly(m)$ time, for some $\delta < 1$?

This is a well-known open problem in the area of "faster algorithms for NP". I don't think it has achieved the status of "major open problem" but it has attracted quite a bit of attention. The best known algorithms run in $2^{n-\Omega(n/\log (m/n))}$ time (e.g., here).

Related to the Exponential Time Hypothesis (that 3SAT is not in subexponential time), there is also a "Strong Exponential Time Hypothesis" that the optimal running time for $k$-SAT converges to $2^{n}$ as $k \rightarrow \infty$. One consequence of Strong-ETH would be that the answer to the above question is no. Several plausible hypotheses imply that the answer is yes, but who knows.

I think it's one of those problems that seem likely to be "resolved" either way: either we'll show a yes-answer, or we'll show that a yes-answer implies something very major. In the first case, we'll have the satisfaction of resolving the problem, in the second case we'll have elevated the question to that of a "major open problem"... a no-answer implies $P \neq NP$, and a yes-answer implies something very major. :)

The question of whether decision trees are PAC learnable seems to be at the frontier of computational learning theory.

OPEN

Are decision trees (DTs) PAC learnable under the uniform distribution on examples (or in general)?

KNOWN

The reason this is an interesting and important problem is because decision trees are a very natural class, and unlike, say automata, we do not have cryptographic hardness results that make the problem hopeless. Progress on this question can perhaps give insight into whether DTs (and similar classes) are learnable without distributional assumptions. This could have practical impact in addition to being a theoretical breakthrough.

This problem also seems to have been tackled from all sides. We know that under the uniform distribution on examples: monotone decision trees are learnable, that random decision trees are learnable, and that there exists a smoothed analysis as well. We also know that a SQ algorithm won't solve this problem. And there is also steady progress in this area. On the other hand, this is a hard problem that has been open for a while, so this seems to fit the bill of "Open Problems on the Frontiers of TCS."

Note there are other results I did not go into on the hardness of proper learning DTs, on the ability to learn DTs with queries, and on the hardness of learning even random DTs with SQs.

OPEN:

Show a lower bound in the cell probe model for an explicit static data-structures problem, that proves that under some "reasonable" space restriction (e.g. that the space is polynomial in the size of the input), then the query time must be at least T, where T is larger than log|Q|, where Q is the set of queries. This is called the "log|Q|-barrier" (or sometimes, in a somewhat misnamed way, the "logn-barrier").

KNOWN:

1. lower bounds higher than log|Q| for an implicit problem (see Miltersen's survey)

2. lower bounds higher than log|Q| with extreme space restrictions (e.g. Succinct lower bounds)

3. lower bounds higher than log|Q| for dynamic problems (where I mean that if the update time is very small then the query time must be very large, or vice-versa; see e.g. Patrascu's lower bound for partial sum)

4. Lower bounds in restricted models, such as pointer machines, comparison model, etc

5. lower bounds that break the log|Q| barrier cannot be proved by the standard kind of reduction to communication complexity, because Alice can just send the query itself, which takes only log|Q| bits, and it is thus easy to verify that the reduction will never give a better lower bound than this. Thus, either a bound "native" to the cell probe model must be used, or some more clever reduction to communication complexity must be used.

• Perhaps I'm misunderstanding the question, but how is this known? "Lower bounds higher than log|Q| for dynamic problems (reference?)" – Mihai Sep 7 '10 at 17:34
• added the appropriate reference, and clarified. – Elad Sep 13 '10 at 0:37

In low-level complexity classes, there is an interesting problem about the characterization of $\mathsf{NL}$.

## OPEN:

Show that whether $\mathsf{NL}$ is equal to $\mathsf{UL}$.

$\mathsf{UL}$, the unambiguous logspace, is the class consists of problems that can be solved by an $\mathsf{NL}$-machine with additional constrain that there are at most one accepting computation path.

## KNOWN:

• Under non-uniform circumstances, $\mathsf{NL/poly} = \mathsf{UL/poly}$. [RA00]
• Under plausible hardness assumptions ($\mathsf{SPACE}(n)$ requires exponential size circuits), the result of [RA00] can be derandomized to show that $\mathsf{NL} = \mathsf{UL}$. [ARZ99]
• Reachability on 3-page graphs is complete for $\mathsf{NL}$. [PTV10]
• Reachability on 2-page graphs is solvable for $\mathsf{UL}$. [BTV09]
• If $\mathsf{NL} = \mathsf{UL}$, then $\mathsf{FNL} \subseteq \mathsf{\sharp L}$. [AJ93]

## UNKNOWN:

• An intermediate class $\mathsf{FewL}$, which is defined to be problems solvable by an $\mathsf{NL}$-machine with at most polynomially many accepting computation path, lies between $\mathsf{NL}$ and $\mathsf{UL}$. No collapses are known.
• It is known that $\mathsf{NL} = \mathsf{coNL}$ by the famous Immerman-Szelepcsényi Theorem, while whether $\mathsf{UL}$ is closed under complement is still open.
• you may want to add NL=coNL, it is a classic result but it is related. – Kaveh Nov 10 '10 at 8:12
• @Kaveh: Do you mean that whether UL is closed under complement? – Hsien-Chih Chang 張顯之 Nov 10 '10 at 9:03
• Got it! Sorry for the misunderstanding... I put it in the UNKNOWN part instead, for emphasizing as a property of UL. – Hsien-Chih Chang 張顯之 Nov 10 '10 at 11:05

Some PCP open problems:

• The Sliding Scale Conjecture. In PCP we want the error of the verifier to be as small as possible. BGLR conjectured that the error can go all the way to $2^{-\Theta(r)}$ where $r$ is the randomness (there is clearly a $2^{-r}$ lower bound). The price you pay for decreasing the error is only increasing the alphabet appropriately.

More formally: the conjecture is that there exists a c, such that for all natural r, for all $\varepsilon \geq 2^{-cr}$, there is a PCP verifier that uses r randomness to make two queries to its proof, has perfect completeness and soundness error $\varepsilon$. The alphabet of the proof depends only on $1/\varepsilon$.

For two queries, the best known error is $1/r^{\beta}$ for some specific $\beta>0$ (M-Raz, 2008). One can also achieve error $2^{-r^{\alpha}}$ for any $\alpha <1$, with a number of queries that depends on $\alpha$ (DFKRS).

Lower bounds on c (i.e., approximation algorithms) are also sought after.

See Irit Dinur's survey for more details.

• Linear length PCP. There are high distance error correcting codes with linear length. Is there a PCP with linear length?

Specifically, we want a verifier for satisfiability of a SAT formula that has constant number of queries, constant alphabet and constant error, and accesses a proof of length linear in the length of the formula? This is open even for error close to 1 (but better than the trivial $1-1/n$), sub-exponential alphabet, and sub-linear number of queries.

The best known length is $n polylog n$ for constant error, and $n \cdot 2^{(log n)^{1-\beta}}$ for sub-constant error.

Prove that for every $c > 0$, there is a language in $E^{NP}$ that doesn't have (non-uniform) circuits with $c n$ wires. Recall that $E = \bigcup_{k \geq 1} TIME[2^{k n}]$. That is, prove superlinear circuit lower bounds for exponential time with access to an $NP$ oracle.

• What's the smallest class for which we do have superlinear circuit lower bounds? – Robin Kothari Sep 12 '10 at 3:26
• @Robin: Good question. There isn't really a "unique" minimum here. In terms of "polynomial bound classes", it is known that the class $S_2 P \subseteq ZPP^{NP}$ does not have superlinear circuits. One can also prove superlinear circuit lower bounds for $TIME[2^{f(n)\cdot n \log n}]$ for unbounded $f$. (Let me leave this as an exercise... hint: the set of all $cn$-size circuits has cardinality $2^{O(n \log n)}$.) – Ryan Williams Sep 13 '10 at 2:44

A $(q,\delta,\epsilon)$-locally decodable code (LDC) is a map $C: \mathbb{F}^m \to \mathbb{F}^n$ such that there is an algorithm $A$, called the local decoder, which, given as input an integer $i \in [m]$ and a received word $y \in \mathbb{F}^n$ that differs from $C(x)$ for some $x \in \mathbb{F}^m$ on at most $\delta$ fraction of positions, looks up at most $q$ coordinates of $y$ and outputs $x_i$ with probability at least $1/|\mathbb{F}| + \epsilon$. The LDC is said to be linear if $\mathbb{F}$ is a field and $C$ is $\mathbb{F}$-linear. LDC's have many applications in complexity theory and privacy, among others.

For $q=2$ and constant $\delta,\epsilon$, the situation is completely resolved. The Hadamard code is a linear $2$-query LDC with $n = \exp(m)$, and this is known to be essentially optimal, even for non-linear LDC's. But here, $q=2$ is the frontier! As soon as we make $q=3$, there is a huge gap between known upper and lower bounds. The current best upper bound is a linear $3$-query LDC over any finite field (and even the reals and complexes) with query complexity $n=\exp(\exp(\sqrt{\log m \log \log m})) = 2^{m^{o(1)}}$ [Efremenko '09, Dvir-Gopalan-Yekhanin '10]. The best lower bounds is $\Omega(m^2)$ for linear $3$-query LDC's over any field and $\Omega(m^2/\log m)$ for general $3$-query LDC's [Woodruff '10]. The situation for larger numbers of queries is even more dire.

What is the largest possible gap between deterministic and (2-sided bounded-error) quantum query complexities for total functions?

## Open:

Does there exist a total function whose quantum query complexity is T, and deterministic query complexity is ω(T2)?

Does there exist a total function whose quantum query complexity is T, and deterministic query complexity is ω(T4)?

If a total function can be computed with T queries by a quantum algorithm, can it always be computed by $o(T^6)$ queries by a deterministic algorithm?

## Known:

If the quantum query complexity of a total function is T, its deterministic query complexity is $O(T^6)$. (Reference)

The largest known gap is achieved by the OR function, which achieves a quadratic gap.

Update (June 21, 2015): We now know a function that achieves a quartic (4th power) separation. See http://arxiv.org/abs/1506.04719.

It is conjectured that the OR function achieves the maximum possible gap.

As per Ashley's suggestion let me add the same problem for exact computation.

## Open:

Does there exist a total function whose exact quantum query complexity is T, and whose deterministic query complexity is $\omega(T)$?

## Known:

If the exact quantum query complexity of a total function is T, its deterministic query complexity is $O(T^3)$. (Reference)

The best known gap is a factor of 2.

Update (Nov 5, 2012): This has been improved in Superlinear advantage for exact quantum algorithms by Andris Ambainis. From the abstract: "We present the first example of a Boolean function f(x_1, ..., x_N) for which exact quantum algorithms have superlinear advantage over the deterministic algorithms. Any deterministic algorithm that computes our function must use N queries but an exact quantum algorithm can compute it with O(N^{0.8675...}) queries."

• This is one of my favourite open problems too. But I would also add the following question: does there exist a total function whose exact quantum query complexity is T, and whose deterministic query complexity is ω(T)? The best known gap is a factor of 2. I find it somewhat shocking that this is an open problem. – Ashley Montanaro Sep 13 '10 at 8:04

There a number of open problems in proof complexity, I will mention only one which remains open even after some experts spent years on trying to settle it. It is the proof complexity version of the state in circuit complexity. (See [Segerlind07] if you want to see more open problems in proof complexity.)

## Open

Prove superpolynomial proof size lowerbounds for the proof system $AC^0[2]$-Frege.

$AC^0[2]$-Frege (a.k.a. d-Frege+$CG_2$) is the proposition proof system that only allows $AC^0[2]$ ($AC^0$ with $\bmod 2$ gates) circuits.

## Known

1. There are exponential proof size lowerbound for $AC^0$-Frege (a.k.a. constant depth Frege, d-Frege) for $PHP^{n+1}_{n}$ (propositional formulation of the Pigeon-Hole Principle with $n+1$ pigeons and $n$ holes). There are also exponential lowerbounds for $AC^0$-Frege + $CA_p$ (constant depth Frege with counting $\bmod p$ axioms). It is also known that $AC^0$-Frege + $CA_m$ are not polynomially bounded.

2. There are exponential circuit size lowerbounds for the corresponding circuit class namely $AC^0[2]$.

References:

• Nathan Segerlind, "The Complexity of Propositional Proofs", Bulletin of Symbolic Logic 13(4), 2007

## Open:

Show an oracle separation between QIP(2) and AM. That is, show a problem in QIP(2)A that is not in AMA.

The big open problem is to show an oracle separation between BQP and PH. But we don't even have a separation between BQP and AM (since AM is in PH, this should be easier). Even worse, make BQP considerably more powerful by allowing 1 round interactions with Merlin, giving you the class QAM or QIP(2) (depending on public coins or private coins) and we still don't have a separation.

## Known:

The best known separation is between BQP and MA, which comes from this paper by John Watrous. For complexity classes that are not decision problem classes, see these results by Scott Aaronson.

I'm not sure if this belongs to the class of frontier open problems or major open problems, so comments are welcomed.

## Open:

Show that whether $\mathsf{NP} = \mathsf{UP}$ implies $\mathsf{PH}$ collapses or not.

$\mathsf{UP}$ (the unambiguous polynomial time) is a class defined as decision problems decided by an NP-machine with an additional constrain that

• there is at most one accepting computation path on any input.

## Known:

A result by Hemaspaandra, Naik, Ogiwara and Selman shows that if the following statement holds, then the polynomial hierarchy collapses to the second level.

• There is an $\mathsf{NP}$ language $L$ such that for each formula $\phi$ in SAT, there is a unique satisfying assignment $x$ with $(\phi,x)$ in $L$.

## Unknown:

Any unlikely collapses or separations.

Related post: More on syntactic vs semantic classes, and UP vs NP.

• Are any weaker statements also open? For example, does MA = UP imply a collapse? or AM = UP? – Robin Kothari Dec 29 '10 at 22:28
• @Robin: In my knowledge, no. But I'm new to this area, and still surveying results within. Maybe something relevant will come up! – Hsien-Chih Chang 張顯之 Dec 31 '10 at 1:20