AC0-MOD2 lower bounds for the Boolean Inner Product. Cheraghchi, M., Grigorescu, E., Juba, B., Wimmer, K., & Xie, N. In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), volume 55, of Leibniz International Proceedings in Informatics (LIPIcs), pages 35:1–35:14, 2016. Extended version in Journal of Computer and System Sciences
AC0-MOD2 lower bounds for the Boolean Inner Product [link]Link  AC0-MOD2 lower bounds for the Boolean Inner Product [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.
@INPROCEEDINGS{ref:conf:CGJWX16,
  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},
  booktitle =	 {Proceedings of the 43rd {International Colloquium on
                  Automata, Languages, and Programming (ICALP 2016)}},
  pages =	 {35:1--35:14},
  series =	 {Leibniz International Proceedings in Informatics
                  (LIPIcs)},
  year =	 2016,
  volume =	 55,
  url_Link =	 {http://drops.dagstuhl.de/opus/volltexte/2016/6315},
  doi =		 {10.4230/LIPIcs.ICALP.2016.35},
  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 =	 {Extended version in {Journal of Computer and System
                  Sciences}},
  url_Paper =	 {https://eccc.weizmann.ac.il//report/2015/030/}
}

Downloads: 0