Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > SYZYGIES:
Reports tagged with syzygies:
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