Addition is exponentially harder than counting for shallow monotone circuits

DOI10.1145/3055399.3055425zbMath1370.94608arXiv1508.03061OpenAlexW2963276484MaRDI QIDQ4978062

Igor C. Oliveira, Xi Chen, Rocco A. Servedio

Publication date: 17 August 2017

Published in: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1508.03061

zbMATH Keywords

circuit complexitymonotone circuitunweighted threshold gateweighted threshold function

Mathematics Subject Classification ID

Related Items (2)

A Short List of Equalities Induces Large Sign-Rank ⋮ Unnamed Item

This page was built for publication: Addition is exponentially harder than counting for shallow monotone circuits