License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2019.39
URN: urn:nbn:de:0030-drops-106156
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10615/
Go to the corresponding LIPIcs Volume Portal

Cheraghchi, Mahdi ; Kabanets, Valentine ; Lu, Zhenjian ; Myrisiotis, Dimitrios

Circuit Lower Bounds for MCSP from Local Pseudorandom Generators

pdf-format:
LIPIcs-ICALP-2019-39.pdf (0.6 MB)

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 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.

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:1--39:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10615},
  URN =		{urn:nbn:de:0030-drops-106156},
  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}
}

Keywords: minimum circuit size problem (MCSP), circuit lower bounds, pseudorandom generators (PRGs), local PRGs, de Morgan formulas, branching programs, consta
Collection: 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Issue Date: 2019
Date of publication: 04.07.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI