Unanswered Questions
91
votes
1answer
7k views
Super Mario Galaxy problem
Suppose Mario is walking on the surface of a planet. If he starts walking from a known location, in a fixed direction, for a predetermined distance, how quickly can we determine where he will stop?
...
46
votes
0answers
2k views
more on PH in PP?
A recent question by Huck Bennet asking whether the class PH was contained in the class PP, received somewhat contradictory answers (all true, it seems). On one hand, several oracle results were ...
38
votes
0answers
1k views
Is there a gap amplification type of result for the Graph Isomorphism Problem?
Suppose $G_1$ and $G_2$ are two undirected graphs on vertex set $\{1, \dotsc, n\}$. The graphs are isomorphic if and only if there is a permutation $\Pi$ such that $G_1 = \Pi(G_2)$, or more formally, ...
36
votes
0answers
799 views
A combinatorial version for the polynomial Hirsch conjecture
Consider $t$ disjoint families of subsets of {1,2,…,n}, ${\cal F}_1,{\cal F_2},\dots {\cal F_t}$ .
Suppose that
(*)
For every $i \lt j \lt k$
and every $R \in {\cal F}_i$, and $T \in {\cal F}_k$, ...
32
votes
0answers
515 views
Monotone complexity of s-t connectivity
In the problem CONN, we obtain a directed $n$-vertex graph (encoded as a boolean string of $n^2$ bits, one for each potential edge), and want to decide
whether there is a path between all $n^2$ pairs ...
31
votes
0answers
751 views
Efficiently computable function as a counter-example to Sarnak's Mobius conjecture
Recently Gil Kalai and Dick Lipton both wrote a nice article on an interesting conjecture proposed by Peter Sarnak, an expert in number theory and Riemann Hypothesis.
Conjecture. Let $\mu(k)$ be ...
29
votes
0answers
840 views
Can one amplify P=NP beyond P=PH?
In Descriptive Complexity, Immerman has
Corollary 7.23. The following conditions are equivalent:
1. P = NP.
2. Over finite, ordered structures, FO(LFP) = SO.
This can be thought of as ...
27
votes
0answers
436 views
Problem unsolvable in $2^{o(n)}$ on inputs with $n$ bits, assuming ETH?
If we assume the Exponential-Time Hypothesis, then there is no $2^{o(n)}$ algorithm for $n$-variable 3-SAT, and many other natural problems, such as 3-COLORING on graphs with $n$ vertices. Notice ...
27
votes
0answers
487 views
What are the consequences of $\mathsf{L}^2 \subseteq \mathsf{P}$?
We know that $\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{P}$ and that $\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{L}^2 \subseteq $ $\mathsf{polyL}$, where $\mathsf{L}^2 = ...
25
votes
0answers
544 views
Does $EXP\neq ZPP$ imply sub-exponential simulation of BPP or NP?
By simulation I mean in the Impaglazzio-Widgerson [IW98] sense, i.e. sub-exponential deterministic simulation which appears correct i.o to every efficient adversary.
I think this is a proof: if ...
23
votes
0answers
319 views
Good codes decodable by linear-sized circuits?
I'm looking for error-correcting codes of the following type:
binary codes with constant rate,
decodable from some constant fraction of errors, by a decoder implementable as a Boolean circuit of ...
21
votes
0answers
564 views
Combinatorics of Bellman-Ford or how to make cyclic graphs acyclic?
Roughly speaking, my question is:
How costly is to make a cyclic graph
acyclic while preserving all simple $s$-$t$ paths?
Let $K_n$ be a complete undirected graph on vertices $\{0,1,\ldots,n+1\}$.
...
21
votes
0answers
308 views
Interesting algorithms in the formalization of the Feit-Thompson theorem?
It looks like George Gonthier and his collaborators have finished formalizing the Odd Order Theorem.
In his earlier work on the Four Color Theorem, Gonthier invented a bunch of new algorithms ...
20
votes
1answer
293 views
Deciding whether an NC${}^0_3$ circuit computes a permutation or not
I would like to ask about a special case of the question “Deciding if a given NC0 circuit computes a permutation” by QiCheng that has been left unanswered.
A Boolean circuit is called an NC0k circuit ...
20
votes
0answers
325 views
Approximately sampling from convex polyhedrons with quantum computers
Quantum computers are very good for sampling distributions that we dont know how to sample using classical computers. For example if f is a Boolean function (from $\{-1,1\}^n$ to ${-1,1}$) that can be ...
