Average-case lower bounds and satisfiability algorithms for small threshold circuitsReport as inadecuate




Average-case lower bounds and satisfiability algorithms for small threshold circuits - Download this document for free, or read online. Document in PDF available to download.

Reference: Santhanam, R, Chen, R and Srinivasan, S, (2016). Average-case lower bounds and satisfiability algorithms for small threshold circuits.Citable link to this page:

 

Average-case lower bounds and satisfiability algorithms for small threshold circuits

Abstract: 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 εd > 0 such that Parity has correlation at most 1/n Ω(1) with depth-d threshold circuits which have at most n^1+εd wires, and the Generalized Andreev Function has correlation at most 1/2^nΩ(1) with depth-d threshold circuits which have at most n^1+εd wires. Previously, only worst-case lower bounds in this setting were known.We use our ideas to make progress on several related questions. We give satisfiability algorithms beating brute force search for depth-d threshold circuits with a superlinear number of wires. These are the first such algorithms for depth greater than 2. We also show that Parity cannot be computed by polynomial-size AC^0 circuits with n^o(1) general threshold gates. Previously no lower bound for Parity in this setting could handle more than log(n) gates. This result also implies subexponential-time learning algorithms for AC^0 with n^o(1) threshold gates under the uniform distribution. In addition, we give almost optimal bounds for the number of gates in a depth-d threshold circuit computing Parity on average, and show average-case lower bounds for threshold formulas of any depth.Our techniques include adaptive random restrictions, anti-concentration and the structural theory of linear threshold functions, and bounded-read Chernoff bounds.

Peer Review status:Peer reviewedPublication status:PublishedVersion:Published version Funder: Seventh Framework Programme   Conference Details: Conference on Computational ComplexityNotes:© Ruiwen Chen, Rahul Santhanam, and Srikanth Srinivasan; licensed under Creative Commons License CC-BY

Bibliographic Details

Publisher: 31st Conference on Computational Complexity

Publisher Website: http://computationalcomplexity.org/

Host: Conference on Computational Complexitysee more from them

Publication Website: http://www.al.ics.saitama-u.ac.jp/elc/ccc/

Issue Date: 2016-06Identifiers

Urn: uuid:6edee8b9-0af8-4c3b-ac2f-74a2391fe8b2

Source identifier: 610631

Doi: https://doi.org/10.4230/LIPIcs.CCC.2016.1 Item Description

Type: Conference;

Version: Published versionKeywords: threshold circuit satisfiability algorithm circuit lower bound Tiny URL: pubs:610631

Relationships





Author: Santhanam, R - institutionUniversity of Oxford Oxford, MPLS, Computer Science - - - Chen, R - - - Srinivasan, S - - - - Bibliogra

Source: https://ora.ox.ac.uk/objects/uuid:6edee8b9-0af8-4c3b-ac2f-74a2391fe8b2



DOWNLOAD PDF




Related documents