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ö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 the most significant progress on the sunflower conjecture since its inception in 1960.
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.
1. Introduction 1.1. Computational complexity 1.2. Monotone circuits 1.3. The approximation method and sunflowers 1.4. Our contribution 2. Definitions and Preliminaries 2.1. Basic notation 2.2. Combinatorics and probability 2.3. Computational complexity 3. Sunflower theorems 3.1. The standard sunflower lemma of Erdos and Rado 3.2. The lopsided sunflower of Alon and Boppana 3.3. The robust sunflower of Rossman 3.4. The slice sunflower of Rao 3.5. Other notions and open questions 4. A breakthrough in sunflower theorems 4.1. Warm-up: an even weaker "sunflower" 4.2. Counting with codes 4.3. Further questions 5. Sunflowers and the approximation method 5.1. Introduction 5.2. Test distributions 5.3. Approximators 5.4. A general construction of legitimate models 5.6. Bounding the number of minterms with abstract sunflowers 5.7. Applying the general construction 6. An improved monotone circuit lower bound for a problem in NP 6.1. Introduction 6.2. The Boolean function of Harnik and Raz 6.3. Test distributions 6.4. Applying the approximation method 6.6. Generalized Harnik-Raz function 6.7. Further questions 7. Better bounds for clique 7.1. Introduction 7.2. Clique sunflowers 7.3. Test distributions 7.4. Applying the approximation method 7.6. Proof of Lemma 7.2.2 7.7. Further questions 8. References
Number of pages: 65
