Conference item icon

Conference item

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 i...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed

Actions


Access Document


Publisher copy:
10.4230/LIPIcs.CCC.2016.1

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Author
More from this funder
Name:
Seventh Framework Programme
Grant:
615075
Publisher:
31st Conference on Computational Complexity
Host title:
Conference on Computational Complexity
Journal:
Conference on Computational Complexity More from this journal
Publication date:
2016-06-01
Acceptance date:
2016-02-06
DOI:
Keywords:
Pubs id:
pubs:610631
UUID:
uuid:6edee8b9-0af8-4c3b-ac2f-74a2391fe8b2
Local pid:
pubs:610631
Source identifiers:
610631
Deposit date:
2016-03-17

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP