Conference item icon

Conference item

Deterministically counting satisfying assignments for constant-depth circuits with parity gates, with implications for lower bounds

Abstract:

We give a deterministic algorithm for counting the number of satisfying assignments of any AC0[] circuit C of size s and depth d over n variables in time 2n-f (n;s;d), where f (n; s; d) = n=O(log(s))d-1, whenever s = 2o(n1=d ). As a consequence, we get that for each d, there is a language in ENP that does not have AC0[] circuits of size 2o(n1=(d+1)). This is the first lower bound in ENP against AC0[] circuits that beats the lower bound of 2 (n1=2(d-1)) due to Razborov and Smolensky for large ...

Expand abstract
Publication status:
Accepted
Peer review status:
Reviewed (other)
Version:
Publisher's Version

Actions


Access Document


Files:
Publisher copy:
10.4230/LIPIcs.MFCS.2018.78

Authors


More by this author
Institution:
University of Oxford
Oxford college:
Magdalen College
Role:
Author
More by this author
Institution:
University of Oxford
Division:
Maths, Physical & Life Sciences
Department:
Computer Science
Oxford college:
Magdalen College
Role:
Author
Publisher:
Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Publisher's website
Publication date:
2018-08-13
Acceptance date:
2018-08-13
DOI:
Pubs id:
pubs:908932
URN:
uri:98b7b047-54b1-40d8-ba47-55467c3de7e4
UUID:
uuid:98b7b047-54b1-40d8-ba47-55467c3de7e4
Local pid:
pubs:908932

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