2026-07-21T23:49:09Z https://drops.dagstuhl.de/oai

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

Circuit Lower Bounds for MCSP from Local Pseudorandom Generators Cheraghchi, Mahdi Kabanets, Valentine Lu, Zhenjian Myrisiotis, Dimitrios minimum circuit size problem (MCSP) circuit lower bounds pseudorandom generators (PRGs) local PRGs de Morgan formulas branching programs constant depth circuits The Minimum Circuit Size Problem (MCSP) asks if a given truth table of a Boolean function f can be computed by a Boolean circuit of size at most theta, for a given parameter theta. We improve several circuit lower bounds for MCSP, using pseudorandom generators (PRGs) that are local; a PRG is called local if its output bit strings, when viewed as the truth table of a Boolean function, can be computed by a Boolean circuit of small size. We get new and improved lower bounds for MCSP that almost match the best-known lower bounds against several circuit models. Specifically, we show that computing MCSP, on functions with a truth table of length N, requires - N^{3-o(1)}-size de Morgan formulas, improving the recent N^{2-o(1)} lower bound by Hirahara and Santhanam (CCC, 2017), - N^{2-o(1)}-size formulas over an arbitrary basis or general branching programs (no non-trivial lower bound was known for MCSP against these models), and - 2^{Omega (N^{1/(d+2.01)})}-size depth-d AC^0 circuits, improving the superpolynomial lower bound by Allender et al. (SICOMP, 2006). The AC^0 lower bound stated above matches the best-known AC^0 lower bound (for PARITY) up to a small additive constant in the depth. Also, for the special case of depth-2 circuits (i.e., CNFs or DNFs), we get an almost optimal lower bound of 2^{N^{1-o(1)}} for MCSP. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mahdi Cheraghchi and Valentine Kabanets and Zhenjian Lu and Dimitrios Myrisiotis 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.39 urn:nbn:de:0030-drops-106156 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.39 eng https://creativecommons.org/licenses/by/3.0/legalcode