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

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

### Access Document

Files:
• (pdf, 583.7KB)
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
Keywords: