Conference item icon

Conference item

An average-case lower bound against ACC$^0$

Abstract:

In a seminal work, Williams [22] showed that NEXP (nondeterministic exponential time) does not have polynomial-size ACC0 circuits. Williams’ technique inherently gives a worst-case lower bound, and until now, no average-case version of his result was known. We show that there is a language L in NEXP and a function ε(n)=1/ log(n) ω(1) such that no sequence of polynomial size ACC0 circuits solves L on more than a 1/2+ε(n) fraction of inputs of length n for all large enough n. Complementing this...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed
Version:
Accepted Manuscript

Actions


Access Document


Files:
Publisher copy:
10.1007/978-3-319-77404-6_24

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS Division
Department:
Computer Science
Role:
Author
More by this author
Institution:
University of Oxford
Division:
MPLS Division
Department:
Computer Science
Role:
Author
More by this author
Institution:
University of Oxford
Division:
MPLS Division
Department:
Computer Science
Oxford college:
Magdalen College; Magdalen College
Role:
Author
More from this funder
Grant:
Seventh Framework Programme (FP7/2007-2014)/ERC Grant Agrement no. 615075
Publisher:
Springer, Cham Publisher's website
Volume:
10807
Pages:
317-330
Series:
Lecture Notes in Computer Science
Publication date:
2018-03-13
Acceptance date:
2017-12-05
DOI:
ISSN:
0302-9743
Pubs id:
pubs:844629
URN:
uri:fe1978e4-a087-4456-91ef-17670960891b
UUID:
uuid:fe1978e4-a087-4456-91ef-17670960891b
Local pid:
pubs:844629
ISBN:
9783319774039

Terms of use


Metrics


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