文章基本信息

标题：Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits
本地全文：下载
作者：Ruiwen Chen ; Rahul Santhanam ; Srikanth Srinivasan 等
期刊名称：Theory of Computing
印刷版ISSN：1557-2862
电子版ISSN：1557-2862
出版年度：2018
卷号：14
页码：1-55
DOI：10.4086/toc.2018.v014a009
出版社：University of Chicago
摘要：We show average-case lower bounds for explicit Boolean functions against bounded-depth threshold circuits with a superlinear number of wires. We show that for each integer d > 1, there is a constant εd > 0 such that the Parity function on n bits has correlation at most n −εd with depth-d threshold circuits which have at most n 1+εd wires, and the Generalized Andreev function on n bits has correlation at most exp(−n εd ) with depth-d threshold circuits which have at most n 1+εd wires. Previously, only worst-case lower bounds in this setting were known (Impagliazzo, Paturi, and Saks (SICOMP 1997)).
关键词：complexity theory; circuit complexity; correlation bounds; threshold functions;; random restrictions; learning; SAT