文章基本信息

标题：Succinct Hitting Sets and Barriers to Proving Lower Bounds for Algebraic Circuits
本地全文：下载
作者：Michael A. Forbes ; Amir Shpilka ; Ben Lee Volk 等
期刊名称：Theory of Computing
印刷版ISSN：1557-2862
电子版ISSN：1557-2862
出版年度：2018
卷号：14
页码：1-45
DOI：10.4086/toc.2018.v014a018
出版社：University of Chicago
摘要：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.
关键词：algebraic circuits; lower bounds; derandomization; polynomial identity testing;; barriers