
Clique Is Hard on Average for Regular Resolution
We prove that for k ≪√(n) regular resolution requires length n^Ω(k) to e...
read it

KRW Composition Theorems via Lifting
One of the major open problems in complexity theory is proving superlog...
read it

Nullstellensatz SizeDegree Tradeoffs from Reversible Pebbling
We establish an exactly tight relation between reversible pebblings of g...
read it

Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity
We significantly strengthen and generalize the theorem lifting Nullstell...
read it

Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs
We show exponential lower bounds on resolution proof length for pigeonho...
read it
Susanna F. de Rezende
is this you? claim profile