Open Problems

 Here's a (semi)organized list of open problems that have tickled my fancy. Some are probably doable, and some are definitely not.

Communication Complexity

1. Number-on-Forehead lifting

    Are there lifting theorems for NOF multiparty communication complexity, even just for 3 players? 

Graph Theory

1. How many bicliques are necessary to cover every edge of $K_n$ between 1 and 2 times? The best bounds are $\sqrt{n-1} \leq \text{bp}_2(n) \leq 2\sqrt{n} - 2$ from [1, 2]. 

Proof Complexity

1. What are the consequences of having an optimal proof system?

2. Can you show the unprovability of a $ \forall \Sigma_1^b $ sentence in $S_2^1$ or $PV$?

3. Can you modify Ajtai's model theoretic approach to $\text{AC}^0$-Frege lower bounds to drop the switching lemma?

4. Achieve size lower bounds for the Lovasz-Schrijver proof system.

5. Separate $\text{PLS}^{dt}$ from the $\textbf{TFNP}^{dt}$ class associated with unary Sum-of-Squares.

6. Characterize Extended Frege in $\textbf{TFNP}^{dt}$.

7. Give black-box separations of $\textbf{TFNP}$ classes $\text{PLC}$ and $\text{UPLC}$. As well, show that Ramsey is not contained in the Turing closure of PPP. 

Computational Complexity

1. Disprove the nondeterministic strong exponential time hypothesis.

2. Assuming $\textbf{P} \neq \textbf{NP}$, show that there is an injective worst case one way function in $\textbf{NC}^1$. (It is known that this is not possible for a worst case one way permutation unless $\textbf{NP} = \textbf{coNP}$).

Computational Geometry

1. Can every convex polyhedron be unfolded onto the plane without any faces overlapping? See [4] for more details.


[1] N. Alon, Neighborly families of boxes and bipartite coverings, The Mathematics of Paul Erd¨os, R.L. Graham and J. Nesteril, Springer Verlag, Vol. 2, Berlin, pp. 27 – 31, 1997.

[2] Huang, Hao, and Benny Sudakov. "A counterexample to the Alon-Saks-Seymour conjecture and related problems." Combinatorica 32.2 (2012): 205-219.

[3] Ben-Sasson, Eli, and Avi Wigderson. "Short proofs are narrow—resolution made simple." Proceedings of the thirty-first annual ACM symposium on Theory of computing. 1999.

[4] Uehara, Ryuhei. Introduction to Computational Origami. Springer Singapore, 2020.


Popular posts from this blog

Extension Complexity Part II - Classifying Nonnegative Rank by Randomized Communication

The Catalan Grenade is Accepting Papers!

Google Summer of Code 2020: D-Complete and Mobile Posets