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 some additional consequences of having an optimal proof system?

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}$).

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 [4] for more details.

References

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

Comments

Post a Comment

Popular posts from this blog

Learning Bounded Arithmetic -- A Guide from a Novice

Bounded Arithmetic is a field of mathematical logic which, very roughly, studies subtheories of Peano Arithmetic that "correspond" with reasoning associated with computational complexity classes or propositional proof systems. Correspond here can mean multiple things, but the two most common interpretations would be the prized Witnessing Theorems or Paris-Wilkies Propositional Translations. At the Simons Institute program for Meta Complexity this winter, many attendants (including myself) wished to learn bounded arithmetic due to its increasing appearances and connections with other areas of complexity. Marco Carmosino, Oliver Korten, and Jan Pich organized a bounded arithmetic reading group to go through many elementary and recent works in bounded arithmetic, with a preference towards those results relating to meta complexity. However, with the creation of the reading group, a running joke was spawned: " I won't define this bounded arithmetic theory " Every we...
Read more

Extension Complexity Part II - Classifying Nonnegative Rank by Randomized Communication

A classical result from Yannakakis states that $$\text{xc}(P) = \text{rank}_+(S),$$ where \(P\) is a polytope with slack matrix \(S\). Yannakakis further showed that with nondeterministic communication complexity, one can give a lower bound for the nonnegative rank. This lower bound is sufficient to prove that some polytopes, like the correlation polytope, have exponential extension complexity. However, it fails for many other examples.  In a 2013 paper, "Extended formulations, nonnegative factorizations, and randomized communication protocols," by Faenza, Fiorini, Grappe, and Tiwary, they show that a model of randomized communication complexity can not only lower bound nonnegative rank, but exactly characterize it.  In my communication complexity reading group, I gave a talk presenting this paper and its results. The proofs are extremely elegant and simple, making for a very enjoyable read.  For those interested, here is a link to my lecture notes! 
Read more

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

In this post, I thought I'd overview the work of  my first paper , which has just recently been accepted to SIDMA.  In order theory, a linear extension of a partially ordered set P is a totally ordered set L which respects the original ordering P. Many famous problems can be converted into counting the number of linear extensions. For example, the number of standard Young tableaux of a given shape is equivalent to the number of linear extensions of a poset with the same shape. Unfortunately, it is #P-complete in general to count linear extensions (even for posets of height 2!). However, there are famous classes of posets like Young diagrams (or more generally, d-complete posets), which have efficient computation. In our paper, we presented a new class of posets called mobiles that have determinant formulas for counting linear extensions and generalize d-complete posets and ribbon posets. Since this past summer converted me into a shut-in, I decided to spend some of that extra ...
Read more