Sunflower Theorems in Monotone Circuit Complexity

• Bruno Pasqualotto Cavalar USP
• Yoshiharu Kohayakawa USP

DOI: https://doi.org/10.5753/ctd.2021.15761

Resumo

Alexander Razborov (1985) developed the approximation method to obtain lower bounds on the size of monotone circuits deciding if a graph contains a clique. Given a "small" circuit, this technique consists in finding a monotone Boolean function which approximates the circuit in a distribution of interest, but makes computation errors in that same distribution. To prove that such a function is indeed a good approximation, Razborov used the sunflower lemma of Erd\H{o}s and Rado (1960). This technique was improved by Alon and Boppana (1987) to show lower bounds for a larger class of monotone computational problems. In that same work, the authors also improved the result of Razborov for the clique problem, using a relaxed variant of sunflowers. More recently, Rossman (2010) developed another variant of sunflowers, now called "robust sunflowers", to obtain lower bounds for the clique problem in random graphs. In the following years, the concept of robust sunflowers found applications in many areas of computational complexity, such as DNF sparsification, randomness extractors and lifting theorems. Even more recent was the breakthrough result of Alweiss, Lovett, Wu and Zhang (2020), which improved Rossman's bound on the size of hypergraphs without robust sunflowers. This result was employed to obtain a significant progress on the sunflower conjecture. In this work, we will show how the recent progress in sunflower theorems can be applied to improve monotone circuit lower bounds. In particular, we will show the best monotone circuit lower bound obtained up to now, breaking a 20-year old record of Harnik and Raz (2000). We will also improve the lower bound of Alon and Boppana for the clique function in a slightly more restricted range of clique sizes. Our exposition is self-contained. These results were obtained in a collaboration with Benjamin Rossman and Mrinal Kumar.

Palavras-chave: computational complexity, circuit complexity, combinatorics

Referências

Alon, N. and Boppana, R. B. (1987). The monotone circuit complexity of Boolean functions. Combinatorica, 7(1):1–22.

Alweiss, R., Lovett, S., Wu, K., and Zhang, J. (2020). Improved bounds for the sunflower lemma. In Proceedings of STOC, pages 624–630, New York, NY, USA.

Andreev, A. (1987). A method for obtaining efficient lower bounds for monotone complexity. Algebra and Logic, 26(1):1–18.

Andreev, A. E. (1985). A method for obtaining lower bounds on the complexity of individual monotone functions. Dokl. Akad. Nauk SSSR, 282(5):1033–1037.

Arora, S. and Barak, B. (2009). Computational complexity. Cambridge University Press, Cambridge. A modern approach.

Arunachalam, S., Grilo, A. B., Gur, T., Oliveira, I. C., and Sundaram, A. (2020). Quantum learning algorithms imply circuit lower bounds. arXiv:2012.01920 [quant-ph].

Bloniarz, P. A. (1980). The complexity of monotone boolean functions and an algorithm for finding shortest paths on a graph. Technical report, USA. Ph.D. Thesis.

Cavalar, B. P., Kumar, M., and Rossman, B. (2020). Monotone Circuit Lower Bounds from Robust Sunflowers. In LATIN 2020: Theoretical Informatics, pages 311–322, Cham. Springer.

Erdos, P. and Rado, R. (1960). Intersection theorems for systems of sets. J. London Math. Soc., 35:85–90.

Gopalan, P., Meka, R., and Reingold, O. (2013). DNF sparsification and a faster deterministic counting algorithm. Computational Complexity, 22(2):275–310.

Goos, M., Jain, R., and Watson, T. (2018). Extension Complexity of Independent Set Polytopes. SIAM Journal on Computing, 47(1):241–269.

Harnik, D. and Raz, R. (2000). Higher lower bounds on monotone size. In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, pages 378–387. ACM, New York.

Jukna, S. (2012). Boolean function complexity, volume 27 of Algorithms and Combinatorics. Springer, Heidelberg. Advances and frontiers.

Karchmer, M. and Wigderson, A. (1988). Monotone Circuits for Connectivity Require Super-logarithmic Depth. In Proceedings of STOC, pages 539–550, New York, NY, USA. ACM.

Krajicek, J. and Oliveira, I. C. (2018). On monotone circuits with local oracles and clique ˇ lower bounds. Chic. J. Theoret. Comput. Sci., pages Art. 1, 18.

Krajicek, J. (1997). Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic. The Journal of Symbolic Logic, 62(2):457–486.

Kushilevitz, E., Ostrovsky, R., and Rosen, A. (1996). Characterizing linear size circuits in terms of privacy. In Proceedings of the twenty-eighth annual ACM symposium on Theory of Computing, STOC ’96, pages 541–550, New York, NY, USA.

Li, X., Lovett, S., and Zhang, J. (2018). Sunflowers and quasi-sunflowers from randomness extractors. In APPROX-RANDOM, volume 116 of LIPIcs, pages 51:1–13.

Lovett, S., Meka, R., Mertz, I., Pitassi, T., and Zhang, J. (2020). Lifting with Sunflowers. Technical Report 111.

Oliveira, I. C. and Santhanam, R. (2017). Conspiracies between learning algorithms, circuit lower bounds, and pseudorandomness. In Proceedings of the 32nd Computational Complexity Conference, CCC ’17, pages 1–49, Dagstuhl, DEU.

Rao, A. (2020). Coding for sunflowers. Discrete Anal., pages Paper No. 2, 8.

Raz, R. and Wigderson, A. (1992). Monotone circuits for matching require linear depth. Journal of the ACM, 39(3):736–744.

Razborov, A. A. (1985). Lower bounds on the monotone complexity of some Boolean functions. Dokl. Akad. Nauk SSSR, 281(4):798–801.

Rossman, B. (2014). The monotone complexity of k-clique on random graphs. SIAM J. Comput., 43(1):256–279.

Tao, T. (2020). The sunflower lemma via shannon entropy. Blogpost.

Tiekenheinrich, J. (1984). A 4n-lower bound on the mononotone network complexity of a oneoutput boolean function. Information Processing Letters, 18:201–201.