Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with AC^0[p]-Frege:
TR14-052 | 14th April 2014
Joshua Grochow, Toniann Pitassi

Circuit complexity, proof complexity, and polynomial identity testing

We introduce a new and very natural algebraic proof system, which has tight connections to (algebraic) circuit complexity. In particular, we show that any super-polynomial lower bound on any Boolean tautology in our proof system implies that the permanent does not have polynomial-size algebraic circuits ($VNP \neq VP$). As a ... more >>>

ISSN 1433-8092 | Imprint