AC0∘MOD2 lower bounds for the Boolean Inner Product

作者：

Highlights：

• The computational power of small-depth circuits with linear processing is considered.

• It is shown that the Boolean inner product cannot be computed by depth four circuits of nearly quadratic size.

• Furthermore, Boolean inner product required superlinear size for any constant depth.

摘要

•The computational power of small-depth circuits with linear processing is considered.•It is shown that the Boolean inner product cannot be computed by depth four circuits of nearly quadratic size.•Furthermore, Boolean inner product required superlinear size for any constant depth.

论文关键词：Boolean analysis,Circuit complexity,Lower bounds

论文评审过程：Received 23 September 2016, Revised 21 November 2017, Accepted 23 April 2018, Available online 31 May 2018, Version of Record 13 August 2018.

论文官网地址：https://doi.org/10.1016/j.jcss.2018.04.006