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?




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.


Comments

Popular posts from this blog

Extension Complexity Part II - Classifying Nonnegative Rank by Randomized Communication

Derandomization of BPP Using Hitting Set Generators

Number-on-the-Forehead Communication Complexity