### 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

## Post a Comment