<p>Here are three in shortest paths research:</p>

<p>$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?</p>

<p>$2$. Is there an $O(n^\omega$ polylog $n)$ algorithm for all pairs shortest paths in unweighted directed graphs? ($\omega&lt;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)$. </p>

<p>(Are the directed problems actually harder?)</p>

<p>$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?</p>

CC BY-SA 2.5
2010-09-06T07:56:59.930Z
2010-09-07T16:55:21.153Z
2010-09-07T16:55:21.153Z
virgi
<p>This is already mentioned in the question:</p>

<h2>Open:</h2>

<blockquote>
  <p><strike> Separate $EXP^{NP}$ from $AC^0_2[6]$ ($AC^0[6]$ circuits of depth 2). </strike> (see the update below)</p>
  
  <p>[Nov. 11, 2010] Separate $EXP$ from $AC^0_2[6]$.
  Separate $EXP^{NP}$ from $TC^0$.</p>
</blockquote>

<h2>Known:</h2>

<ol>
<li><p>[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$.</p></li>
<li><p>[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)}}$.</p></li>
</ol>

<p>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.</p>

<p>Obstacles:
?</p>

<hr>

<h3>Update [Nov. 10, 2010]</h3>

<p>A <a href="http://www.cs.cmu.edu/~ryanw/acc-lbs.pdf">paper</a> by <a href="http://www.cs.cmu.edu/~ryanw/">Ryan Williams</a> seems to have settled this open problem using methods which seem to be essentially different from those mentioned above:</p>

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

<hr>

<p>References: <br/></p>

<ul>
<li><p>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.</p></li>
<li><p>R. Smolensky. Algebraic methods in the theory of lower bounds for Boolean
circuit complexity. In STOC, pages 77–82. ACM, 1987.</p></li>
<li><p>Arkadev Chattopadhyay and Avi Wigderson. <a href="http://www.cs.mcgill.ca/~achatt3/singleLayer2G.pdf">Linear Systems over Composite Moduli</a>, FOCS 2009</p></li>
<li><p>Ryan Williams. <a href="http://www.cs.cmu.edu/~ryanw/acc-lbs.pdf">Non-Uniform ACC Circuit Lower Bounds</a>, 2010, draft (submitted?).</p></li>
</ul>

CC BY-SA 2.5
2010-09-06T04:57:32.250Z
Is NP the largest class not known to strictly include $AC^0$[6]?
Robin Kothari
CC BY-SA 2.5
2010-09-06T05:13:26.727Z
No, improved it based on Ryan O'Donnell answer on MO: http://mathoverflow.net/questions/35422/most-obvious-open-problems-in-complexity-theory/35480#35480
Kaveh
CC BY-SA 2.5
2010-09-06T05:45:04.363Z
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
CC BY-SA 2.5
2010-09-06T22:29:14.743Z
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
CC BY-SA 2.5
2010-10-13T07:51:10.233Z
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
CC BY-SA 2.5
2010-11-10T02:31:16.400Z
Now this one is settled by Ryan: http://www.cs.cmu.edu/~ryanw/acc-lbs.pdf. Congratulations!!!
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-11-10T11:07:33.040Z
@Kaveh: nice time machine you have there.
András Salamon
CC BY-SA 2.5
2010-11-11T01:56:54.037Z
@András Salamon: typo :). Thanks to @Iddo for fixing it.
Kaveh
CC BY-SA 2.5
2010-09-06T04:52:22.743Z
2010-11-10T12:19:51.793Z
2010-11-10T12:19:51.793Z
Kaveh
<p>Let CNF-SAT be the problem of determining whether a given CNF formula is satisfiable (no restrictions on the width of clauses).</p>

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

<p>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., <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.137.8758">here</a>).</p>

<p>Related to the Exponential Time Hypothesis (that 3SAT is not in subexponential time), there is also a <a href="http://faculty.cs.tamu.edu/chen/iwpec2009/images/52.pdf">"Strong Exponential Time Hypothesis"</a> 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 <a href="http://www.cs.cmu.edu/~ryanw/cnf-sat-feasible.pdf">the answer is yes</a>, but who knows. </p>

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

CC BY-SA 2.5
2010-09-13T17:33:28.873Z
2010-09-13T17:33:28.873Z
Ryan Williams
<p>In low-level complexity classes, there is an interesting problem about the characterization of  <span class="math-container">$\mathsf{NL}$</span>.</p>

<h2><strong>OPEN:</strong></h2>

<blockquote>
  <p>Show whether <span class="math-container">$\mathsf{NL}$</span> is equal to <span class="math-container">$\mathsf{UL}$</span>.</p>
</blockquote>

<p><span class="math-container">$\mathsf{UL}$</span>, the <strong>unambiguous logspace</strong>, is the class consists of problems that can be solved by an <span class="math-container">$\mathsf{NL}$</span>-machine with additional constrain that there are at most one accepting computation path.</p>

<h2><strong>KNOWN:</strong></h2>

<blockquote>
  <ul>
  <li>Under <strong>non-uniform</strong> circumstances, <span class="math-container">$\mathsf{NL/poly} = \mathsf{UL/poly}$</span>. <a href="http://eccc.uni-trier.de/eccc-reports/1997/TR97-014/" rel="nofollow noreferrer">[RA00]</a></li>
  <li>Under plausible hardness assumptions (<span class="math-container">$\mathsf{SPACE}(n)$</span> requires exponential size circuits), the result of [RA00] can be <strong>derandomized</strong> to show that <span class="math-container">$\mathsf{NL} = \mathsf{UL}$</span>. <a href="http://www.cs.rutgers.edu/pub/allender/matching.pdf" rel="nofollow noreferrer">[ARZ99]</a></li>
  <li><strong>Reachability</strong> on 3-page graphs is complete for <span class="math-container">$\mathsf{NL}$</span>. <a href="http://cse.unl.edu/~rtewari/unamb.pdf" rel="nofollow noreferrer">[PTV10]</a></li>
  <li><strong>Reachability</strong> on 2-page graphs is solvable for <span class="math-container">$\mathsf{UL}$</span>. <a href="http://www.cse.unl.edu/~rtewari/DPRinUL.pdf" rel="nofollow noreferrer">[BTV09]</a></li>
  <li>If <span class="math-container">$\mathsf{NL} = \mathsf{UL}$</span>, then <span class="math-container">$\mathsf{FNL} \subseteq \mathsf{\sharp L}$</span>. <a href="http://portal.acm.org/citation.cfm?id=155687" rel="nofollow noreferrer">[AJ93]</a></li>
  </ul>
</blockquote>

<h2><strong>UNKNOWN:</strong></h2>

<blockquote>
  <ul>
  <li>An intermediate class <span class="math-container">$\mathsf{FewL}$</span>, which is defined to be problems solvable by an <span class="math-container">$\mathsf{NL}$</span>-machine with at most polynomially many accepting computation path, lies between <span class="math-container">$\mathsf{NL}$</span> and <span class="math-container">$\mathsf{UL}$</span>. No collapses are known.</li>
  <li>It is known that <span class="math-container">$\mathsf{NL} = \mathsf{coNL}$</span> by the famous Immerman-Szelepcsényi Theorem, while whether <span class="math-container">$\mathsf{UL}$</span> is closed under complement is still open.</li>
  </ul>
</blockquote>

CC BY-SA 2.5
2010-11-10T08:12:07.327Z
you may want to add NL=coNL, it is a classic result but it is related.
Kaveh
CC BY-SA 2.5
2010-11-10T09:03:21.930Z
@Kaveh: Do you mean that whether UL is closed under complement?
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-11-10T11:05:10.700Z
Got it! Sorry for the misunderstanding... I put it in the UNKNOWN part instead, for emphasizing as a property of UL.
Hsien-Chih Chang 張顯之
CC BY-SA 4.0
2010-11-10T03:31:22.433Z
2020-06-04T02:45:35.147Z
2020-06-04T02:45:35.147Z
Hsien-Chih Chang 張顯之
<p>The question of whether decision trees are PAC learnable seems to be at the frontier of computational learning theory.</p>
<p><strong>OPEN</strong></p>
<blockquote>
<p>Are decision trees (DTs) PAC learnable under
the uniform distribution on examples (or in general)?</p>
</blockquote>
<p><strong>KNOWN</strong></p>
<blockquote>
<ul>
<li>DTs are not learnable under the uniform distribution with Statistical
Queries (SQs) [<a href="https://dl.acm.org/doi/10.1145/195058.195147" rel="nofollow noreferrer">Blum et al. '94</a>]</li>
<li>random DTs are learnable under the uniform distribution [<a href="http://www.cs.columbia.edu/%7Erocco/papers/colt03rt.html" rel="nofollow noreferrer">Jackson, Servedio
'05</a>]</li>
<li>monotone DTs are learnable under the uniform distribution
[<a href="http://www.cs.columbia.edu/%7Erocco/papers/ccc06os.html" rel="nofollow noreferrer">O'Donnell, Servedio '06</a>]</li>
<li>a smoothed analysis for learning DTs under the uniform distribution
[<a href="https://arxiv.org/abs/0812.0933" rel="nofollow noreferrer">Kalai, Teng '08</a>]</li>
</ul>
</blockquote>
<p>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.</p>
<p>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 &quot;Open Problems on the Frontiers of TCS.&quot;</p>
<p><em>Note there are other results I did not go into on the <a href="http://www.almaden.ibm.com/cs/people/vitaly/allpapers.html#ABFKP04_ProperHardness" rel="nofollow noreferrer">hardness of proper learning</a> DTs, on the ability to <a href="http://www.cs.technion.ac.il/%7Ebshouty/COLT/LECTUR-NOTES/Monotone-Theory/mt.pdf" rel="nofollow noreferrer">learn DTs with queries</a>, and on the hardness of learning <a href="https://web.archive.org/web/20210506174010/http://www.levreyzin.com/papers/AngluinEKR10.pdf" rel="nofollow noreferrer">even random DTs</a> with SQs.</em></p>

CC BY-SA 4.0
2010-09-08T23:12:31.307Z
2022-07-09T11:00:32.423Z
2022-07-09T11:00:32.423Z
Lev Reyzin
<p>Some PCP open problems:</p>

<ul>
<li><strong>The Sliding Scale Conjecture.</strong> In PCP we want the error of the verifier to be as small as possible. <a href="http://portal.acm.org/citation.cfm?id=195467">BGLR</a> 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.</li>
</ul>

<p>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$. </p>

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

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

<p>See <a href="http://www.wisdom.weizmann.ac.il/~dinuri/mypapers/D08.pdf">Irit Dinur's survey</a> for more details.</p>

<ul>
<li><strong>Linear length PCP.</strong> There are high distance error correcting codes with linear length. Is there a PCP with linear length? </li>
</ul>

<p>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. </p>

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

CC BY-SA 2.5
2010-11-10T23:15:31.480Z
2010-11-15T16:41:29.097Z
2010-11-15T16:41:29.097Z
Dana Moshkovitz
<p>OPEN:</p>

<p>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"). </p>

<p>KNOWN:</p>

<ol>
<li><p>lower bounds higher than log|Q| for an implicit problem (see <a href="http://www.daimi.au.dk/~bromille/Papers/survey3.ps">Miltersen's survey</a>)</p></li>
<li><p>lower bounds higher than log|Q| with extreme space restrictions (e.g. Succinct lower bounds)</p></li>
<li><p>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)</p></li>
<li><p>Lower bounds in restricted models, such as pointer machines, comparison model, etc </p></li>
<li><p>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.</p></li>
</ol>

CC BY-SA 2.5
2010-09-07T17:34:30.627Z
Perhaps I'm misunderstanding the question, but how is this known? "Lower bounds higher than log|Q| for dynamic problems (reference?)"
Mihai
CC BY-SA 2.5
2010-09-13T00:37:58.150Z
added the appropriate reference, and clarified.
Elad
CC BY-SA 2.5
2010-09-07T03:39:36.963Z
2010-09-13T00:37:05.580Z
2010-09-13T00:37:05.580Z
Elad
<p>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.)</p>
<h2>Open</h2>
<blockquote>
<p>Prove superpolynomial proof size lowerbounds for the proof system <span class="math-container">$AC^0[2]$</span>-Frege.</p>
</blockquote>
<p><span class="math-container">$AC^0[2]$</span>-Frege (a.k.a. d-Frege+<span class="math-container">$CG_2$</span>) is the proposition proof system that only allows <span class="math-container">$AC^0[2]$</span> (<span class="math-container">$AC^0$</span> with <span class="math-container">$\bmod 2$</span> gates) circuits.</p>
<h2>Known</h2>
<blockquote>
<ol>
<li><p>There are exponential proof size lowerbound for <span class="math-container">$AC^0$</span>-Frege (a.k.a. constant depth Frege, d-Frege) for <span class="math-container">$PHP^{n+1}_{n}$</span> (propositional formulation of the Pigeon-Hole Principle with <span class="math-container">$n+1$</span> pigeons and <span class="math-container">$n$</span> holes). There are also exponential lowerbounds for <span class="math-container">$AC^0$</span>-Frege + <span class="math-container">$CA_p$</span> (constant depth Frege with counting <span class="math-container">$\bmod p$</span> axioms). It is also known that <span class="math-container">$AC^0$</span>-Frege + <span class="math-container">$CA_m$</span> are not polynomially bounded.</p>
</li>
<li><p>There are exponential circuit size lowerbounds for the corresponding circuit class namely <span class="math-container">$AC^0[2]$</span>.</p>
</li>
</ol>
</blockquote>
<hr />
<p>References:</p>
<ul>
<li>Nathan Segerlind, &quot;The Complexity of Propositional Proofs&quot;, Bulletin of Symbolic Logic 13(4), 2007</li>
</ul>

CC BY-SA 2.5
2010-11-11T02:25:41.110Z
2010-11-11T02:25:41.110Z
2020-06-17T09:38:08.363Z
Kaveh
<p>A <em><span class="math-container">$(q,\delta,\epsilon)$</span>-locally decodable code (LDC)</em> is a map <span class="math-container">$C: \mathbb{F}^m \to \mathbb{F}^n$</span> such that there is an algorithm <span class="math-container">$A$</span>, called the local decoder, which, given as input an integer <span class="math-container">$i \in [m]$</span> and a received word <span class="math-container">$y \in \mathbb{F}^n$</span> that differs from <span class="math-container">$C(x)$</span> for some <span class="math-container">$x \in \mathbb{F}^m$</span> on at most <span class="math-container">$\delta$</span> fraction of positions, looks up at most <span class="math-container">$q$</span> coordinates of <span class="math-container">$y$</span> and outputs <span class="math-container">$x_i$</span> with probability at least <span class="math-container">$1/|\mathbb{F}| + \epsilon$</span>.  The LDC is said to be <em>linear</em> if <span class="math-container">$\mathbb{F}$</span> is a field and <span class="math-container">$C$</span> is <span class="math-container">$\mathbb{F}$</span>-linear. LDC's have many applications in complexity theory and privacy, among others.</p>
<p>For <span class="math-container">$q=2$</span> and constant <span class="math-container">$\delta,\epsilon$</span>, the situation is completely resolved.  The Hadamard code is a linear <span class="math-container">$2$</span>-query LDC with <span class="math-container">$n = \exp(m)$</span>, and this is known to be essentially optimal, even for non-linear LDC's.  But here, <span class="math-container">$q=2$</span> is the frontier!  As soon as we make <span class="math-container">$q=3$</span>, there is a huge gap between known upper and lower bounds.  The current best upper bound is a linear <span class="math-container">$3$</span>-query LDC over any finite field (and even the reals and complexes) with query complexity <span class="math-container">$n=\exp(\exp(\sqrt{\log m \log \log m})) = 2^{m^{o(1)}}$</span> [<a href="https://web.archive.org/web/20090625185826/http://www.wisdom.weizmann.ac.il/~klime/Klim_files/LDC_new.pdf" rel="nofollow noreferrer">Efremenko '09</a>, <a href="https://www.microsoft.com/en-us/research/people/yekhanin/?from=http://research.microsoft.com/en-us/um/people/yekhanin/papers/mv_codes.pdf" rel="nofollow noreferrer">Dvir-Gopalan-Yekhanin '10</a>].  The best lower bounds is <span class="math-container">$\Omega(m^2)$</span> for linear <span class="math-container">$3$</span>-query LDC's over any field and <span class="math-container">$\Omega(m^2/\log m)$</span> for general <span class="math-container">$3$</span>-query LDC's [<a href="https://web.archive.org/web/20110107060714/http://www.almaden.ibm.com/cs/people/dpwoodru/w10b.pdf" rel="nofollow noreferrer">Woodruff '10</a>].  The situation for larger numbers of queries is even more dire.</p>

CC BY-SA 4.0
2010-09-13T19:56:39.343Z
2022-07-09T11:01:00.990Z
2022-07-09T11:01:00.990Z
arnab
<p>What is the largest possible gap between deterministic and (2-sided bounded-error) quantum <a href="http://en.wikipedia.org/wiki/Decision_tree_model">query complexities</a> for total functions?</p>

<h2>Open:</h2>

<blockquote>
  <p><strike>Does there exist a total function whose quantum query complexity is T, and deterministic query complexity is &omega;(T<sup>2</sup>)?</strike></p>
  
  <p>Does there exist a total function whose quantum query complexity is T, and deterministic query complexity is &omega;(T<sup>4</sup>)?</p>
  
  <p>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?</p>
</blockquote>

<h2>Known:</h2>

<blockquote>
  <p>If the quantum query complexity of a total function is T, its deterministic query complexity is $O(T^6)$. <a href="http://doi.acm.org/10.1145/502090.502097">(Reference)</a></p>
  
  <p><strike>The largest known gap is achieved by the OR function, which achieves a quadratic gap.</strike> </p>
  
  <p><b>Update (June 21, 2015)</b>: We now know a function that achieves a quartic (4th power) separation. See <a href="http://arxiv.org/abs/1506.04719">http://arxiv.org/abs/1506.04719</a>.</p>
</blockquote>

<p><strike>It is conjectured that the OR function achieves the maximum possible gap.</strike></p>

<hr>

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

<h2>Open:</h2>

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

<h2>Known:</h2>

<blockquote>
  <p>If the exact quantum query complexity of a total function is T, its deterministic query complexity is $O(T^3)$. <a href="http://arxiv.org/abs/quant-ph/0403168">(Reference)</a></p>
  
  <p><strike>The best known gap is a factor of 2.</strike> </p>
  
  <p><b>Update (Nov 5, 2012)</b>: This has been improved in <a href="http://arxiv.org/abs/1211.0721">Superlinear advantage for exact quantum algorithms by Andris Ambainis</a>. 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."</p>
</blockquote>

CC BY-SA 2.5
2010-09-13T08:04:57.523Z
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
CC BY-SA 3.0
2010-09-08T04:37:46.380Z
2015-06-21T20:11:26.973Z
2015-06-21T20:11:26.973Z
Robin Kothari
<p>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. </p>

CC BY-SA 2.5
2010-09-12T03:26:28.390Z
What's the smallest class for which we do have superlinear circuit lower bounds?
Robin Kothari
CC BY-SA 2.5
2010-09-13T02:44:31.183Z
@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
CC BY-SA 2.5
2010-09-06T07:30:53.517Z
2010-09-06T07:30:53.517Z
Ryan Williams
<h2>Open:</h2>

<blockquote>
  <p>Show an oracle separation between QIP(2) and AM. That is, show a problem in QIP(2)<sup>A</sup> that is not in AM<sup>A</sup>.</p>
</blockquote>

<p>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. </p>

<h2>Known:</h2>

<blockquote>
  <p>The best known separation is between BQP and MA, which comes from <a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2000.892141">this paper by John Watrous</a>. For complexity classes that are not decision problem classes, see <a href="http://www.scottaaronson.com/papers/bqpph.pdf">these results by Scott Aaronson</a>.</p>
</blockquote>

CC BY-SA 2.5
2010-09-08T20:30:13.133Z
2010-09-08T20:30:13.133Z
Robin Kothari
<p>I'm not sure if this belongs to the class of <em>frontier</em> open problems or <em>major</em> open problems, so comments are welcomed.</p>

<h2>Open:</h2>

<blockquote>
  <p>Show that whether $\mathsf{NP} = \mathsf{UP}$ implies $\mathsf{PH}$ collapses or not.</p>
</blockquote>

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

<ul>
<li>there is at most one accepting computation path on any input.</li>
</ul>

<p>This problem has been stated in <a href="http://blog.computationalcomplexity.org/2003/12/does-npup.html" rel="nofollow noreferrer">the complexity blog</a> in 2003.</p>

<h2>Known:</h2>

<blockquote>
  <p>A <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.32.8999&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">result</a> by Hemaspaandra, Naik, Ogiwara and Selman shows that if 
  the following statement holds,
  then the polynomial hierarchy collapses to the second level.</p>
  
  <ul>
  <li>There is an $\mathsf{NP}$ language $L$ such that for each formula $\phi$ in SAT, there is a <em>unique</em> satisfying assignment $x$ with $(\phi,x)$ in $L$.</li>
  </ul>
</blockquote>

<h2>Unknown:</h2>

<blockquote>
  <p>Any unlikely collapses or separations.</p>
</blockquote>

<p>Related post: <a href="https://cstheory.stackexchange.com/q/3887/1800">More on syntactic vs semantic classes, and UP vs NP</a>.</p>

CC BY-SA 2.5
2010-12-29T22:28:29.830Z
Are any weaker statements also open? For example, does MA = UP imply a collapse? or AM = UP?
Robin Kothari
CC BY-SA 2.5
2010-12-31T01:20:31.660Z
@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 張顯之
CC BY-SA 4.0
2020-06-04T05:49:35.080Z
It is even open to construct an oracle relative to which NP=UP but PH doesn't collapse to the 2nd level (this is one of my favorite open oracle questions).
Joshua Grochow
CC BY-SA 2.5
2010-12-29T02:43:13.173Z
2010-12-29T02:43:13.173Z
2017-04-13T12:32:28.077Z
Hsien-Chih Chang 張顯之
<p>In the thread <a href="https://cstheory.stackexchange.com/questions/174/major-unsolved-problems-in-theoretical-computer-science">Major unsolved problems in theoretical computer science?</a>, Iddo Tzameret made the following excellent comment:</p>

<blockquote>
  <p>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.</p>
</blockquote>

<p>Since Iddo did not start the thread, I thought I'll start this thread.</p>

<p>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<sup>0</sup> 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<sup>1.801</sup>.</p>

<p>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:</p>

<ol>
<li>Will often not be the big open problems of the field, but will be a big breakthrough if solved. </li>
<li>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. </li>
<li>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.</li>
<li>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.</li>
<li>Often these problems are the easiest problems that are still open. For example we don't have exponential lower bounds for AC<sup>1</sup> 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.</li>
</ol>

<p>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.</p>

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

CC BY-SA 2.5
2010-09-06T05:15:59.017Z
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
CC BY-SA 2.5
2010-09-06T05:40:31.003Z
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
CC BY-SA 2.5
2010-09-08T16:34:37.043Z
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
CC BY-SA 2.5
2010-09-08T20:08:09.220Z
Good idea. I'm also curious to know what happens if you award a bounty to a CW answer.
Robin Kothari
CC BY-SA 2.5
2010-09-14T21:51:07.073Z
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
CC BY-SA 2.5
2011-02-04T22:07:05.653Z
A good theory of average case complexity may be seen as an open problem on the frontier of TCS. However, it is different in kind than many of the problems listed already. What about problems of this sort?
Ross Snider
<big-list><open-problem>
Open problems on the frontiers of TCS
Robin Kothari
# Open problems on the frontiers of TCS

(Asked by: username_0 on 2010-09-06)

In the thread [Major unsolved problems in theoretical computer science?](https://cstheory.stackexchange.com/questions/174/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.

**Tags:** big-list, open-problem
> **Comments:**
> **username_1**: 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)  
> **username_0**: 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.  
> **username_2**: 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. :)  
> **username_0**: Good idea. I'm also curious to know what happens if you award a bounty to a CW answer.  
> **username_2**: 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.)  
> **username_3**: A good theory of average case complexity may be seen as an open problem on the frontier of TCS. However, it is different in kind than many of the problems listed already. What about problems of this sort?  

---

## 13 answers

### Answer by username_4 on 2010-09-06. Score: 31

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 by username_5 on 2010-09-06. Score: 22

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](http://www.cs.cmu.edu/~ryanw/acc-lbs.pdf) by [Ryan Williams](http://www.cs.cmu.edu/~ryanw/) 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](http://www.cs.mcgill.ca/~achatt3/singleLayer2G.pdf), FOCS 2009
* Ryan Williams. [Non-Uniform ACC Circuit Lower Bounds](http://www.cs.cmu.edu/~ryanw/acc-lbs.pdf), 2010, draft (submitted?).

> **Comments:**
> **username_0**: Is NP the largest class not known to strictly include $AC^0$[6]?  
> **username_5**: No, improved it based on Ryan O'Donnell answer on MO: http://mathoverflow.net/questions/35422/most-obvious-open-problems-in-complexity-theory/35480#35480  
> **username_0**: 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.  
> **username_6**: 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\}$.  
> **username_7**: 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.  
> **username_8**: Now this one is settled by Ryan: http://www.cs.cmu.edu/~ryanw/acc-lbs.pdf. Congratulations!!!  
> **username_9**: @Kaveh: nice time machine you have there.  
> **username_5**: @András Salamon: typo :). Thanks to @Iddo for fixing it.  

---

### Answer by username_7 on 2010-09-13. Score: 21

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](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.137.8758)).

Related to the Exponential Time Hypothesis (that 3SAT is not in subexponential time), there is also a ["Strong Exponential Time Hypothesis"](http://faculty.cs.tamu.edu/chen/iwpec2009/images/52.pdf) 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](http://www.cs.cmu.edu/~ryanw/cnf-sat-feasible.pdf), 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 by username_8 on 2010-11-10. Score: 19

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]](http://eccc.uni-trier.de/eccc-reports/1997/TR97-014/)
> * 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]](http://www.cs.rutgers.edu/pub/allender/matching.pdf)
> * **Reachability** on 3-page graphs is complete for $\mathsf{NL}$. [[PTV10]](http://cse.unl.edu/~rtewari/unamb.pdf)
> * **Reachability** on 2-page graphs is solvable for $\mathsf{UL}$. [[BTV09]](http://www.cse.unl.edu/~rtewari/DPRinUL.pdf)
> * If $\mathsf{NL} = \mathsf{UL}$, then $\mathsf{FNL} \subseteq \mathsf{\sharp L}$. [[AJ93]](http://portal.acm.org/citation.cfm?id=155687)

## **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.

> **Comments:**
> **username_5**: you may want to add NL=coNL, it is a classic result but it is related.  
> **username_8**: @Kaveh: Do you mean that whether UL is closed under complement?  
> **username_8**: Got it! Sorry for the misunderstanding... I put it in the UNKNOWN part instead, for emphasizing as a property of UL.  

---

### Answer by username_10 on 2010-09-08. Score: 19

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](https://dl.acm.org/doi/10.1145/195058.195147)]
> * random DTs are learnable under the uniform distribution [[Jackson, Servedio
>   '05](http://www.cs.columbia.edu/%7Erocco/papers/colt03rt.html)]
> * monotone DTs are learnable under the uniform distribution
>   [[O'Donnell, Servedio '06](http://www.cs.columbia.edu/%7Erocco/papers/ccc06os.html)]
> * a smoothed analysis for learning DTs under the uniform distribution
>   [[Kalai, Teng '08](https://arxiv.org/abs/0812.0933)]

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](http://www.almaden.ibm.com/cs/people/vitaly/allpapers.html#ABFKP04_ProperHardness) DTs, on the ability to [learn DTs with queries](http://www.cs.technion.ac.il/%7Ebshouty/COLT/LECTUR-NOTES/Monotone-Theory/mt.pdf), and on the hardness of learning [even random DTs](https://web.archive.org/web/20210506174010/http://www.levreyzin.com/papers/AngluinEKR10.pdf) with SQs.*


---

### Answer by username_11 on 2010-11-10. Score: 17

Some PCP open problems:

* **The Sliding Scale Conjecture.** In PCP we want the error of the verifier to be as small as possible. [BGLR](http://portal.acm.org/citation.cfm?id=195467) 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](http://www.wisdom.weizmann.ac.il/~dinuri/mypapers/D08.pdf) 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 by username_12 on 2010-09-07. Score: 16

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](http://www.daimi.au.dk/~bromille/Papers/survey3.ps))
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.

> **Comments:**
> **username_13**: Perhaps I'm misunderstanding the question, but how is this known? "Lower bounds higher than log|Q| for dynamic problems (reference?)"  
> **username_12**: added the appropriate reference, and clarified.  

---

### Answer by username_7 on 2010-09-06. Score: 15

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.

> **Comments:**
> **username_0**: What's the smallest class for which we do have superlinear circuit lower bounds?  
> **username_7**: @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)}$.)  

---

### Answer by username_5 on 2010-11-11. Score: 14

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 by username_14 on 2010-09-13. Score: 14

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](https://web.archive.org/web/20090625185826/http://www.wisdom.weizmann.ac.il/~klime/Klim_files/LDC_new.pdf), [Dvir-Gopalan-Yekhanin '10](https://www.microsoft.com/en-us/research/people/yekhanin/?from=http://research.microsoft.com/en-us/um/people/yekhanin/papers/mv_codes.pdf)]. 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](https://web.archive.org/web/20110107060714/http://www.almaden.ibm.com/cs/people/dpwoodru/w10b.pdf)]. The situation for larger numbers of queries is even more dire.


---

### Answer by username_0 on 2010-09-08. Score: 13

What is the largest possible gap between deterministic and (2-sided bounded-error) quantum [query complexities](http://en.wikipedia.org/wiki/Decision_tree_model) 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)](http://doi.acm.org/10.1145/502090.502097)
>
> 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)](http://arxiv.org/abs/quant-ph/0403168)
>
> 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](http://arxiv.org/abs/1211.0721). 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."

> **Comments:**
> **username_15**: 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.  

---

### Answer by username_0 on 2010-09-08. Score: 9

## 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](http://doi.ieeecomputersociety.org/10.1109/SFCS.2000.892141). For complexity classes that are not decision problem classes, see [these results by Scott Aaronson](http://www.scottaaronson.com/papers/bqpph.pdf).


---

### Answer by username_8 on 2010-12-29. Score: 4

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](http://blog.computationalcomplexity.org/2003/12/does-npup.html) in 2003.

## Known:

> A [result](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.32.8999&rep=rep1&type=pdf) 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](https://cstheory.stackexchange.com/q/3887/1800).

> **Comments:**
> **username_0**: Are any weaker statements also open? For example, does MA = UP imply a collapse? or AM = UP?  
> **username_8**: @Robin: In my knowledge, no. But I'm new to this area, and still surveying results within. Maybe something relevant will come up!  
> **username_16**: It is even open to construct an oracle relative to which NP=UP but PH doesn't collapse to the 2nd level (this is one of my favorite open oracle questions).  

---

