Cheraghchi, Mahdi ;
Kabanets, Valentine ;
Lu, Zhenjian ;
Myrisiotis, Dimitrios
Circuit Lower Bounds for MCSP from Local Pseudorandom Generators
Abstract
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 bestknown lower bounds against several circuit models. Specifically, we show that computing MCSP, on functions with a truth table of length N, requires
 N^{3o(1)}size de Morgan formulas, improving the recent N^{2o(1)} lower bound by Hirahara and Santhanam (CCC, 2017),
 N^{2o(1)}size formulas over an arbitrary basis or general branching programs (no nontrivial lower bound was known for MCSP against these models), and
 2^{Omega (N^{1/(d+2.01)})}size depthd AC^0 circuits, improving the superpolynomial lower bound by Allender et al. (SICOMP, 2006).
The AC^0 lower bound stated above matches the bestknown AC^0 lower bound (for PARITY) up to a small additive constant in the depth. Also, for the special case of depth2 circuits (i.e., CNFs or DNFs), we get an almost optimal lower bound of 2^{N^{1o(1)}} for MCSP.
BibTeX  Entry
@InProceedings{cheraghchi_et_al:LIPIcs:2019:10615,
author = {Mahdi Cheraghchi and Valentine Kabanets and Zhenjian Lu and Dimitrios Myrisiotis},
title = {{Circuit Lower Bounds for MCSP from Local Pseudorandom Generators}},
booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
pages = {39:139:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771092},
ISSN = {18688969},
year = {2019},
volume = {132},
editor = {Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10615},
URN = {urn:nbn:de:0030drops106156},
doi = {10.4230/LIPIcs.ICALP.2019.39},
annote = {Keywords: minimum circuit size problem (MCSP), circuit lower bounds, pseudorandom generators (PRGs), local PRGs, de Morgan formulas, branching programs, consta}
}
04.07.2019
Keywords: 

minimum circuit size problem (MCSP), circuit lower bounds, pseudorandom generators (PRGs), local PRGs, de Morgan formulas, branching programs, consta 
Seminar: 

46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Issue date: 

2019 
Date of publication: 

04.07.2019 