2026-07-23T16:48:30Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10642 2024-03-06T10:46:21Z ddc:004 open_access

AC^0[p] Lower Bounds Against MCSP via the Coin Problem Golovnev, Alexander Ilango, Rahul Impagliazzo, Russell Kabanets, Valentine Kolokolova, Antonina Tal, Avishay Minimum Circuit Size Problem (MCSP) circuit lower bounds AC0[p] coin problem hybrid argument MKTP biased random boolean functions Minimum Circuit Size Problem (MCSP) asks to decide if a given truth table of an n-variate boolean function has circuit complexity less than a given parameter s. We prove that MCSP is hard for constant-depth circuits with mod p gates, for any prime p >= 2 (the circuit class AC^0[p]). Namely, we show that MCSP requires d-depth AC^0[p] circuits of size at least exp(N^{0.49/d}), where N=2^n is the size of an input truth table of an n-variate boolean function. Our circuit lower bound proof shows that MCSP can solve the coin problem: distinguish uniformly random N-bit strings from those generated using independent samples from a biased random coin which is 1 with probability 1/2+N^{-0.49}, and 0 otherwise. Solving the coin problem with such parameters is known to require exponentially large AC^0[p] circuits. Moreover, this also implies that MAJORITY is computable by a non-uniform AC^0 circuit of polynomial size that also has MCSP-oracle gates. The latter has a few other consequences for the complexity of MCSP, e.g., we get that any boolean function in NC^1 (i.e., computable by a polynomial-size formula) can also be computed by a non-uniform polynomial-size AC^0 circuit with MCSP-oracle gates. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Alexander Golovnev and Rahul Ilango and Russell Impagliazzo and Valentine Kabanets and Antonina Kolokolova and Avishay Tal 2019 Is Part Of LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2019.66 urn:nbn:de:0030-drops-106422 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.66 eng https://creativecommons.org/licenses/by/3.0/legalcode