Kewen Wu, an undergraduate student from PKU School of EECS' Turing Class (Class of 2016), recently had two papers featured at the 52nd Annual ACM Symposium on Theory of Computing (STOC 2020): "Improved bounds for the sunflower lemma"and "Decision list compression by mild random restrictions". The former one won the Best Paper Award of STOC 2020.

A sunflower with r petals is a collection of r sets so that the intersection of each pair is equal to the intersection of all. Erdős and Rado proved the sunflower lemma: for any fixed r, any family of sets of size w, with at least about w^w sets, must contain a sunflower. The famous sunflower conjecture is that the bound on the number of sets can be improved to c^w for some constant c. In this paper, we improve the bound to about (logw)^w. In fact, we prove the result for a robust notion of sunflowers, for which the bound we obtain is tight up to lower order terms.

Paper: https://dl.acm.org/doi/10.1145/3357713.3384234

A decision list is an ordered list of rules. Each rule is specified by a term, which is a conjunction of literals, and a value. Given an input, the output of a decision list is the value corresponding to the first rule whose term is satisfied by the input. Decision lists generalize both CNFs and DNFs, and have been studied both in complexity theory and in learning theory. The size of a decision list is the number of rules, and its width is the maximal number of variables in a term. We prove that decision lists of small width can always be approximated by decision lists of small size, where we obtain sharp bounds. This in particular resolves a conjecture of Gopalan, Meka and Reingold (Computational Complexity, 2013) on DNF sparsification. An ingredient in our proof is a new random restriction lemma, which allows to analyze how DNFs (and more generally, decision lists) simplify if a small fraction of the variables are fixed. This is in contrast to the more commonly used switching lemma, which requires most of the variables to be fixed.

Paper: https://dl.acm.org/doi/10.1145/3357713.3384241

Kewen Wu is an undergraduate at Peking University. He majors in CS, doubles in Math, and is expected to graduate in 2020. He has broad interests in theoretical computer science.

The Annual ACM Symposium on Theory of Computing (STOC), is the flagship conference of SIGACT, the Special Interest Group on Algorithms and Computation Theory, a special interest group of the Association for Computing Machinery (ACM). It has been held annually since 1969. STOC covers all areas of research within Algorithms and Computation Theory. Topics of interest include, but are not limited to: algorithms and data structures, computational complexity, randomness in computing, algorithmic graph theory and combinatorics, approximation algorithms, cryptography, computational learning theory, economics and computation, parallel and distributed algorithms, quantum computing, algorithmic coding theory, computational geometry, computational applications of logic, optimization, algebraic algorithms. STOC 2020 will be held online Monday, June 22 – Friday, June 26, 2020.