CaltechAUTHORS
  A Caltech Library Service

Succinct Hitting Sets and Barriers to Proving Lower Bounds for Algebraic Circuits

Forbes, Michael A. and Shpilka, Amir and Volk, Ben Lee (2018) Succinct Hitting Sets and Barriers to Proving Lower Bounds for Algebraic Circuits. Theory of Computing, 14 . Art. No. 18. ISSN 1557-2862. https://resolver.caltech.edu/CaltechAUTHORS:20190104-094927988

[img] PDF - Published Version
Creative Commons Attribution.

430Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20190104-094927988

Abstract

We formalize a framework of algebraically natural lower bounds for algebraic circuits. Just as with the natural proofs notion of Razborov and Rudich (1997) for Boolean circuit lower bounds, our notion of algebraically natural lower bounds captures nearly all lower bound techniques known. However, unlike in the Boolean setting, there has been no concrete evidence demonstrating that this is a barrier to obtaining super-polynomial lower bounds for general algebraic circuits, as there is little understanding whether algebraic circuits are expressive enough to support “cryptography” secure against algebraic circuits. Following a similar result of Williams (2016) in the Boolean setting, we show that the existence of an algebraic natural proofs barrier is equivalent to the existence of succinct derandomization of the polynomial identity testing problem, that is, to the existence of a hitting set for the class of poly(N)-degree poly(N)-size circuits which consists of coefficient vectors of polynomials of polylog(N) degree with polylog(N)-size circuits. Further, we give an explicit universal construction showing that if such a succinct hitting set exists, then our universal construction suffices. Further, we assess the existing literature constructing hitting sets for restricted classes of algebraic circuits and observe that none of them are succinct as given. Yet, we show how to modify some of these constructions to obtain succinct hitting sets. This constitutes the first evidence supporting the existence of an algebraic natural proofs barrier. Our framework is similar to the Geometric Complexity Theory (GCT) program of Mulmuley and Sohoni (2001), except that here we emphasize constructiveness of the proofs while the GCT program emphasizes symmetry. Nevertheless, our succinct hitting sets have relevance to the GCT program as they imply lower bounds for the complexity of the defining equations of polynomials computed by small circuits. A conference version of this paper appeared in the Proceedings of the 49th Annual ACM Symposium on Theory of Computing (STOC 2017).


Item Type:Article
Related URLs:
URLURL TypeDescription
https://doi.org/10.4086/toc.2018.v014a018DOIArticle
https://doi.org/10.1145/3055399.3055496DOIConference Paper
https://arxiv.org/abs/1701.05328arXivDiscussion Paper
Additional Information:© 2018 Michael A. Forbes, Amir Shpilka, and Ben Lee Volk. Creative Commons License Creative Commons License Attribution Licensed under a Creative Commons Attribution License (CC-BY). Received: July 16, 2017. Revised: July 26, 2018. Published: December 18, 2018. We thank Scott Aaronson, Andy Drucker, Josh Grochow, Mrinal Kumar, Shubhangi Saraf and Dor Minzer for useful conversations regarding this work. We also thank the anonymous reviewers for their careful reading of this paper and for many useful comments.
Classification Code:ACM Classification: F.1.3. AMS Classification: 68Q15, 68Q17.
Record Number:CaltechAUTHORS:20190104-094927988
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20190104-094927988
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:92088
Collection:CaltechAUTHORS
Deposited By: George Porter
Deposited On:04 Jan 2019 18:00
Last Modified:03 Oct 2019 20:40

Repository Staff Only: item control page