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

Popular posts from this blog

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

Derandomization of BPP Using Hitting Set Generators

In 1999, Goldreich, Vadhan, and Wigderson wrote a beautiful and simple paper that the derandomization of RP through hitting set generators also derandomizes BPP. In the following  write up , I survey basic results on RP and BPP, as well as the results of this paper. If you are too lazy to read, feel free to watch a recorded lecture  I made on the topic while quarantined at my grandfather's house! If you are wondering why I look like I am in a witness protection program in the recording, it is cause my DIY whiteboard fails with any internal lighting.
Read more

Extension Complexity

 Last week I gave an introductory lecture on extension complexity for my communication complexity reading group. It is a fascinating topic, discussing if a polytope with exponentially many facets might be described as a linear projection from a higher dimensional polytope with polynomially many facets. Specifically, the extension complexity is defined as xc(P) := min{# facets of Q : Q projects to P}.  A classical example of this would be the permutohedron  with dimension N; it has 2^N - 2 facets, but there is a polytope in dimension N^2 + N with O(N^2) facets which projects to the permutohedron. I covered this example, as well as Yannakakis' theorem, which shows an equivalence between extension complexity and nonnegative rank of a certain matrix. I also highlight a connection with communication complexity, which will be expanded upon in the upcoming semester. I hope to give more in-depth lectures, with the intent of covering Rothvoss' 2017 result on exponential lower bounds for
Read more