Open Problems

 Here's a (semi)organized list of open problems that have tickled my fancy.


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. Is there a "combinatorial" measure for the complexity of cutting planes proofs? For Resolution, we have a well-known width-size trade off controlled by the resolution width. Namely, $$S_{\text{Res}}(F) \geq 2^{(w_{\text{Res}}(F) - w(F))^2 / 16n},$$

from [3]. Is there something comparable for Cutting Planes?


Computational Complexity

1. Does TFNP have complete problems?


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

Popular posts from this blog

The Catalan Grenade is Accepting Papers!

Extension Complexity Part II - Classifying Nonnegative Rank by Randomized Communication

Number-on-the-Forehead Communication Complexity