More Like this

1. Lifting with Sunflowers

   Lovett, Shachar; Meka, Raghu; Mertz, Ian; Pitassi, Toniann; Zhang, Jiapeng (January 2022, Leibniz international proceedings in informatics)

   Query-to-communication lifting theorems translate lower bounds on query complexity to lower bounds for the corresponding communication model. In this paper, we give a simplified proof of deterministic lifting (in both the tree-like and dag-like settings). Our proof uses elementary counting together with a novel connection to the sunflower lemma. In addition to a simplified proof, our approach opens up a new avenue of attack towards proving lifting theorems with improved gadget size - one of the main challenges in the area. Focusing on one of the most widely used gadgets - the index gadget - existing lifting techniques are known to require at least a quadratic gadget size. Our new approach combined with robust sunflower lemmas allows us to reduce the gadget size to near linear. We conjecture that it can be further improved to polylogarithmic, similar to the known bounds for the corresponding robust sunflower lemmas. 

   more » « less
2. Note on sunflowers

   https://doi.org/10.1016/j.disc.2021.112367  

   Bell, Tolson; Chueluecha, Suchakree; Warnke, Lutz (July 2021, Discrete Mathematics)

   null (Ed.)
3. Lifting with Sunflowers

   https://doi.org/10.4230/LIPIcs.ITCS.2022.104  

   Lovett, Shachar and (April 2022, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022))
4. Near-sunflowers and focal families

   https://doi.org/10.1007/S11856-023-2500-1  

   Alon, Noga; Holzman, Ron (September 2023, Israel Journal of Mathematics)

   We present some problems and results about variants of sunflowers in families of sets. In particular, we improve an upper bound of the first author, Körner and Monti on the maximum number of binary vectors of length n so that every four of them are split into two pairs by some coordinate. We also propose a weaker version of the Erdős-Rado sunflower conjecture. 

   more » « less
5. Sunflowers in Set Systems of Bounded Dimension

   https://doi.org/10.1007/s00493-023-00012-z  

   Fox, Jacob; Pach, János; Suk, Andrew (January 2023, Combinatorica)