AC0-MOD2 lower bounds for the Boolean Inner Product

AC0-MOD2 lower bounds for the Boolean Inner Product. Cheraghchi, M., Grigorescu, E., Juba, B., Wimmer, K., & Xie, N. Journal of Computer and System Sciences, 97:45–59, 2018. Preliminary version in Proceedings of ICALP 2016.

Link

Paper doi abstract bibtex

AC0-MOD2 circuits are AC0 circuits augmented with a layer of parity gates just above the input layer. We study AC0-MOD2 circuit lower bounds for computing the Boolean Inner Product functions. Recent works by Servedio and Viola (ECCC TR12-144) and Akavia et al. (ITCS 2014) have highlighted this problem as a frontier problem in circuit complexity that arose both as a first step towards solving natural special cases of the matrix rigidity problem and as a candidate for constructing pseudorandom generators of minimal complexity. We give the first superlinear lower bound for the Boolean Inner Product function against AC0-MOD2 of depth four or greater. Specifically, we prove a superlinear lower bound for circuits of arbitrary constant depth, and an $Ω̃(n^2)}$ lower bound for the special case of depth-4 AC0-MOD2.

@ARTICLE{ref:CGJWX18,
  author =	 {Mahdi Cheraghchi and Elena Grigorescu and Brendan
                  Juba and Karl Wimmer and Ning Xie},
  title =	 {{AC0-MOD2} lower bounds for the {Boolean} Inner
                  Product},
  journal =	 {Journal of Computer and System Sciences},
  volume =	 97,
  pages =	 "45--59",
  year =	 2018,
  doi =		 "10.1016/j.jcss.2018.04.006",
  url_Link =
                  "http://www.sciencedirect.com/science/article/pii/S002200001830518X",
  keywords =	 "Boolean analysis, Circuit complexity, Lower bounds",
  abstract =	 "AC0-MOD2 circuits are AC0 circuits augmented with a
                  layer of parity gates just above the input layer. We
                  study AC0-MOD2 circuit lower bounds for computing
                  the Boolean Inner Product functions. Recent works by
                  Servedio and Viola (ECCC TR12-144) and Akavia et
                  al. (ITCS 2014) have highlighted this problem as a
                  frontier problem in circuit complexity that arose
                  both as a first step towards solving natural special
                  cases of the matrix rigidity problem and as a
                  candidate for constructing pseudorandom generators
                  of minimal complexity. We give the first superlinear
                  lower bound for the Boolean Inner Product function
                  against AC0-MOD2 of depth four or
                  greater. Specifically, we prove a superlinear lower
                  bound for circuits of arbitrary constant depth, and
                  an $\tilde{\Omega(n^2)}$ lower bound for the special
                  case of depth-4 AC0-MOD2.",
  note =	 {Preliminary version in Proceedings of {ICALP 2016.}},
  url_Paper =	 {https://eccc.weizmann.ac.il//report/2015/030/}
}

Downloads: 0