Addition is exponentially harder than counting for shallow monotone circuits. Chen, X., Oliveira, I. C., & Servedio, R. A. Electronic Colloquium on Computational Complexity (ECCC), 22:123, 2015.
Addition is exponentially harder than counting for shallow monotone circuits. [link]Link  Addition is exponentially harder than counting for shallow monotone circuits. [link]Paper  bibtex   
@article{journals/eccc/ChenOS15,
  added-at = {2015-08-19T00:00:00.000+0200},
  author = {Chen, Xi and Oliveira, Igor Carboni and Servedio, Rocco A.},
  biburl = {http://www.bibsonomy.org/bibtex/2b5e341a9be67de1fdc09e0ac8486df80/dblp},
  ee = {http://eccc.hpi-web.de/report/2015/123},
  interhash = {5cc1f00c93bc2e852f663698526b2f80},
  intrahash = {b5e341a9be67de1fdc09e0ac8486df80},
  journal = {Electronic Colloquium on Computational Complexity (ECCC)},
  keywords = {dblp},
  pages = 123,
  timestamp = {2015-08-20T11:32:44.000+0200},
  title = {Addition is exponentially harder than counting for shallow monotone circuits.},
  url = {http://dblp.uni-trier.de/db/journals/eccc/eccc22.html#ChenOS15},
  volume = 22,
  year = 2015
}

Downloads: 0