Open problems on the frontiers of TCS

Question

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 AC⁰ 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 n^1.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 AC¹ 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 AC⁰[6] and not AC⁰[3]? The answer is that we do have lower bounds against AC⁰[3]. But then the obvious question is why do those methods fail for AC⁰[6]. It would be nice if answers could explain this too.

Answer 1

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?

Answer 2

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?).

Answer 3

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. :)

Answer 4

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

OPEN:

Show 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.

Answer 5

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

• DTs are not learnable under the uniform distribution with Statistical Queries (SQs) [Blum et al. '94]
• random DTs are learnable under the uniform distribution [Jackson, Servedio '05]
• monotone DTs are learnable under the uniform distribution [O'Donnell, Servedio '06]
• a smoothed analysis for learning DTs under the uniform distribution [Kalai, Teng '08]

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.

Answer 6

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.

Answer 7

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.

Answer 8

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.

Answer 9

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

Answer 10

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.

Answer 11

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 ω(T²)?

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

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."

Answer 12

Open:

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

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.

Answer 13

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.

This problem has been stated in the complexity blog in 2003.

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.