Circuit Lower Bounds for MCSP from Local Pseudorandom Generators

Circuit Lower Bounds for MCSP from Local Pseudorandom Generators. Cheraghchi, M., Kabanets, V., Lu, Z., & Myrisiotis, D. In Proceedings of the 46th International Colloquium on Automata, Languages and Programming (ICALP), volume 132, of Leibniz International Proceedings in Informatics (LIPIcs), pages 39:1–39:14, 2019. Extended version to appear in ACM Transactions on Computation Theory (ToCT).

Link

Paper doi abstract bibtex

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 $θ$, for a given parameter $θ$. 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: 1) $N^{3-o(1)}$-size de Morgan formulas, improving the recent $N^{2-o(1)}$ lower bound by Hirahara and Santhanam (CCC 2017), 2) $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 3) $2^{Ω(N^{1/(d+1.01)})}$-size depth-$d$ $\mathrm{AC}^0$ circuits, improving the (implicit, in their work) exponential size lower bound by Allender et al. (SICOMP 2006). The $\mathrm{AC}^0$ lower bound stated above matches the best-known $\mathrm{AC}^0$ lower bound (for \tt 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 optimal lower bound of $2^Ω(N)$ for MCSP.

@INPROCEEDINGS{ref:conf:CKLM19,
  author =	 {Mahdi Cheraghchi and Valentine Kabanets and Zhenjian
                  Lu and Dimitrios Myrisiotis},
  title =	 {Circuit Lower Bounds for {MCSP} from Local
                  Pseudorandom Generators},
  year =	 2019,
  booktitle =	 {Proceedings of the 46th {International Colloquium on
                  Automata, Languages and Programming (ICALP)}},
  pages =	 {39:1--39:14},
  series =	 {Leibniz International Proceedings in Informatics
                  (LIPIcs)},
  volume =	 132,
  note =	 {Extended version to appear in {ACM Transactions on
                  Computation Theory (ToCT)}.},
  doi =		 {10.4230/LIPIcs.ICALP.2019.39},
  url_Link =
                  {https://drops.dagstuhl.de/opus/frontdoor.php?source_opus=10615},
  url_Paper =	 {https://eccc.weizmann.ac.il/report/2019/022},
  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 \textit{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: 1) $N^{3-o(1)}$-size
                  de Morgan formulas, improving the recent
                  $N^{2-o(1)}$ lower bound by Hirahara and Santhanam
                  (CCC 2017), 2) $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 3)
                  $2^{\Omega(N^{1/(d+1.01)})}$-size depth-$d$
                  $\mathrm{AC}^0$ circuits, improving the (implicit,
                  in their work) exponential size lower bound by
                  Allender et al. (SICOMP 2006).  The $\mathrm{AC}^0$
                  lower bound stated above matches the best-known
                  $\mathrm{AC}^0$ lower bound (for {\tt PARITY}) up to
                  a small \textit{additive} constant in the
                  depth. Also, for the special case of depth-$2$
                  circuits (i.e., CNFs or DNFs), we get an optimal
                  lower bound of \(2^{{\Omega}(N)}\) for MCSP.  },
  keywords =	 {minimum circuit size problem (MCSP), circuit lower
                  bounds, pseudorandom generators (PRGs), local PRGs,
                  de Morgan formulas, branching programs, constant
                  depth circuits}
}

Downloads: 0