research
∙
06/01/2023
Toward Better Depth Lower Bounds: A KRW-like theorem for Strong Composition
One of the major open problems in complexity theory is proving super-log...
share
research
∙
12/03/2020
Shrinkage under Random Projections, and Cubic Formula Lower Bounds for 𝐀𝐂^0
Håstad showed that any De Morgan formula (composed of AND, OR and NOT ga...
research
∙
07/06/2020
KRW Composition Theorems via Lifting
One of the major open problems in complexity theory is proving super-log...
research
∙
01/08/2020
Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling
We establish an exactly tight relation between reversible pebblings of g...
research
∙
01/07/2020
Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity
We significantly strengthen and generalize the theorem lifting Nullstell...
research
∙
04/30/2019
Query-to-Communication Lifting Using Low-Discrepancy Gadgets
Lifting theorems are theorems that relate the query complexity of a func...
research
∙
04/30/2019