Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > DNF RESOLUTION:
Reports tagged with DNF Resolution:
TR21-158 | 12th November 2021
Noah Fleming, Toniann Pitassi, Robert Robere

Extremely Deep Proofs

Revisions: 1

We further the study of supercritical tradeoffs in proof and circuit complexity, which is a type of tradeoff between complexity parameters where restricting one complexity parameter forces another to exceed its worst-case upper bound. In particular, we prove a new family of supercritical tradeoffs between depth and size for Resolution, ... more >>>




ISSN 1433-8092 | Imprint