Deterministically counting satisfying assignments for constant-depth circuits with parity gates, with implications for lower bounds
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 tha...
| Main Authors: | , , |
|---|---|
| Format: | Conference item |
| Published: |
Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH
2018
|