2026-07-23T03:26:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9660 2024-03-06T10:44:39Z ddc:004 open_access

Deterministically Counting Satisfying Assignments for Constant-Depth Circuits with Parity Gates, with Implications for Lower Bounds Rajgopal, Ninad Santhanam, Rahul Srinivasan, Srikanth circuit satisfiability circuit lower bounds polynomial method derandomization We give a deterministic algorithm for counting the number of satisfying assignments of any AC^0[oplus] circuit C of size s and depth d over n variables in time 2^(n-f(n,s,d)), where f(n,s,d) = n/O(log(s))^(d-1), whenever s = 2^o(n^(1/d)). As a consequence, we get that for each d, there is a language in E^{NP} that does not have AC^0[oplus] circuits of size 2^o(n^(1/(d+1))). This is the first lower bound in E^{NP} against AC^0[oplus] circuits that beats the lower bound of 2^Omega(n^(1/2(d-1))) due to Razborov and Smolensky for large d. Both our algorithm and our lower bounds extend to AC^0[p] circuits for any prime p. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ninad Rajgopal and Rahul Santhanam and Srikanth Srinivasan 2018 Is Part Of LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2018.78 urn:nbn:de:0030-drops-96607 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.78 eng https://creativecommons.org/licenses/by/3.0/legalcode