Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with sunflower lemma:
TR17-040 | 4th March 2017
Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao

Non-Adaptive Data Structure Lower Bounds for Median and Predecessor Search from Sunflowers

Revisions: 2

We prove new cell-probe lower bounds for data structures that maintain a subset of $\{1,2,...,n\}$, and compute the median of the set. The data structure is said to handle insertions non-adaptively if the locations of memory accessed depend only on the element being inserted, and not on the contents of ... more >>>

TR19-056 | 11th April 2019
Tom Gur, Oded Lachish

A Lower Bound for Relaxed Locally Decodable Codes

Revisions: 1

A locally decodable code (LDC) C:{0,1}^k -> {0,1}^n is an error correcting code wherein individual bits of the message can be recovered by only querying a few bits of a noisy codeword. LDCs found a myriad of applications both in theory and in practice, ranging from probabilistically checkable proofs to ... more >>>

TR19-110 | 23rd August 2019
Ryan Alweiss, Shachar Lovett, Kewen Wu, Jiapeng Zhang

Improved bounds for the sunflower lemma

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\H{o}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 ... more >>>

TR20-048 | 16th April 2020
Shachar Lovett, Raghu Meka, Jiapeng Zhang

Improved lifting theorems via robust sunflowers

Lifting theorems are a generic way to lift lower bounds in query complexity to lower bounds in communication complexity, with applications in diverse areas, such as combinatorial optimization, proof complexity, game theory. Lifting theorems rely on a gadget, where smaller gadgets give stronger lower bounds. However, existing proof techniques are ... more >>>

ISSN 1433-8092 | Imprint