Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with sunflower lemmas:
TR20-154 | 10th October 2020
Marcel Dall'Agnol, Tom Gur, Oded Lachish

A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Privacy

We prove a general structural theorem for a wide family of local algorithms, which includes property testers, local decoders, and PCPs of proximity. Namely, we show that the structure of every algorithm that makes $q$ adaptive queries and satisfies a natural robustness condition admits a sample-based algorithm with $n^{1- 1/O(q^2 ... more >>>

TR20-181 | 4th December 2020
Bruno Pasqualotto Cavalar, Mrinal Kumar, Benjamin Rossman

Monotone Circuit Lower Bounds from Robust Sunflowers

Revisions: 2

Robust sunflowers are a generalization of combinatorial sunflowers that have applications in monotone circuit complexity, DNF sparsification, randomness extractors, and recent advances on the Erd\H{o}s-Rado sunflower conjecture. The recent breakthrough of Alweiss, Lovett, Wu and Zhang gives an improved bound on the maximum size of a $w$-set system that excludes ... more >>>

ISSN 1433-8092 | Imprint