Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Sunflowers:
TR11-067 | 25th April 2011
Noga Alon, Amir Shpilka, Chris Umans

On Sunflowers and Matrix Multiplication

Comments: 1

We present several variants of the sunflower conjecture of Erd\H{o}s and Rado and discuss the relations among them.

We then show that two of these conjectures (if true) imply negative answers to questions of Coppersmith and Winograd and Cohn et al. regarding possible approaches for obtaining fast matrix multiplication algorithms. ... more >>>

TR20-111 | 24th July 2020
Ian Mertz, Toniann Pitassi

Lifting: As Easy As 1,2,3

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). Whereas previous proofs used sophisticated Fourier analytic techniques, our proof uses elementary counting together with ... more >>>

ISSN 1433-8092 | Imprint