research
∙
02/17/2022
Proofs, Circuits, and Communication
We survey lower-bound results in complexity theory that have been obtain...
share
research
∙
12/17/2020
Clique Is Hard on Average for Regular Resolution
We prove that for k ≪√(n) regular resolution requires length n^Ω(k) to e...
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
∙
12/02/2019