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, and some are very open-ended.
Communication Complexity
1. Are there lifting theorems for NOF multiparty communication complexity, even just for 3 players?
Proof Complexity
1. What are some additional consequences of having/not having an optimal proof system?
[Update: July 22, 2025] Two great papers on this broad question have been published this year! (See [3] and [4])
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.
8. Give conditional lower bounds for Fermat's Little Theorem in full bounded arithmetic ($\textbf{S}_2$). Currently, we know that Fermat's Little Theorem is not provable in $\textbf{S}^1_2$ unless factoring is easy.
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}$).
3. Show that for RAMs, $\textbf{DTIME}(n) \subsetneq \textbf{NTIME}(n)$
Computational Geometry
1. Can every convex polyhedron be unfolded onto the plane without any faces overlapping? See [2] for more details.
References
[1] 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.
[2] Uehara, Ryuhei. Introduction to Computational Origami. Springer Singapore, 2020.
[3] Ilango, Rahul. Godel in Cryptography: Effectively Zero-Knowledge Proofs for NP with No Interaction, No Setup, and Perfect Soundness. https://eccc.weizmann.ac.il/report/2025/095/
[4] Egidy, Fabian, and Christian Glaßer. Optimal Proof Systems for Complex Sets are Hard to Find. https://arxiv.org/abs/2408.07408
Comments
Post a Comment