Circuit Lower Bounds for MCSP from Local Pseudorandom Generators. Cheraghchi, M., Kabanets, V., Lu, Z., & Myrisiotis, D. ACM Transactions on Computation Theory (ToCT), 2020. Preliminary version in Proceedings of ICALP 2019.
Circuit Lower Bounds for MCSP from Local Pseudorandom Generators [link]Paper  Circuit Lower Bounds for MCSP from Local Pseudorandom Generators [link]Link  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.
@ARTICLE{ref:CKLM20,
  title =	 {Circuit Lower Bounds for {MCSP} from Local
                  Pseudorandom Generators},
  author =	 {Mahdi Cheraghchi and Valentine Kabanets and Zhenjian
                  Lu and Dimitrios Myrisiotis},
  year =	 2020,
  journal =	 {{ACM Transactions on Computation Theory (ToCT)}},
  volume =	 12,
  number =	 3,
  articleno =	 21,
  note =	 {Preliminary version in {Proceedings of ICALP 2019}.},
  url_Paper =	 {https://eccc.weizmann.ac.il/report/2019/022},
  url_Link =	 {https://dl.acm.org/doi/abs/10.1145/3404860},
  doi =		 {10.1145/3404860},
  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),
                  constant-depth circuits, branching programs, local
                  PRGs, de Morgan formulas}
}

Downloads: 0