Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Jan Bydzovsky:

TR19-077 | 30th May 2019
Jan Bydzovsky, Igor Carboni Oliveira, Jan Krajicek

Consistency of circuit lower bounds with bounded theories

Proving that there are problems in $P^{NP}$ that require boolean circuits of super-linear size is a major frontier in complexity theory. While such lower bounds are known for larger complexity classes, existing results only show that the corresponding problems are hard on infinitely many input lengths. For instance, proving almost-everywhere ... more >>>

ISSN 1433-8092 | Imprint