Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with succinct hitting sets:
TR17-007 | 19th January 2017
Michael Forbes, Amir Shpilka, Ben Lee Volk

Succinct Hitting Sets and Barriers to Proving Algebraic Circuits Lower Bounds

Revisions: 1

We formalize a framework of algebraically natural lower bounds for algebraic circuits. Just as with the natural proofs notion of Razborov and Rudich for boolean circuit lower bounds, our notion of algebraically natural lower bounds captures nearly all lower bound techniques known. However, unlike the boolean setting, there has been ... more >>>

TR17-009 | 19th January 2017
Joshua Grochow, Mrinal Kumar, Michael Saks, Shubhangi Saraf

Towards an algebraic natural proofs barrier via polynomial identity testing

We observe that a certain kind of algebraic proof - which covers essentially all known algebraic circuit lower bounds to date - cannot be used to prove lower bounds against VP if and only if what we call succinct hitting sets exist for VP. This is analogous to the Razborov-Rudich ... more >>>

ISSN 1433-8092 | Imprint