research-article

Open access

Near-optimal lower bounds on the threshold degree and sign-rank of AC⁰

Authors:

Alexander A. Sherstov,

Pei WuAuthors Info & Claims

STOC 2019: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing

Pages 401 - 412

https://doi.org/10.1145/3313276.3316408

Published: 23 June 2019 Publication History

Abstract

The threshold degree of a Boolean function f∶{0,1}ⁿ→{0,1} is the minimum degree of a real polynomial p that represents f in sign: sgn p(x)=(−1)^f(x). A related notion is sign-rank, defined for a Boolean matrix F=[F_ij] as the minimum rank of a real matrix M with sgn M_ij=(−1)^F_ij. Determining the maximum threshold degree and sign-rank achievable by constant-depth circuits (AC⁰) is a well-known and extensively studied open problem, with complexity-theoretic and algorithmic applications.

We give an essentially optimal solution to this problem. For any є>0, we construct an AC⁰ circuit in n variables that has threshold degree Ω(n^1−є) and sign-rank exp(Ω(n^1−є)), improving on the previous best lower bounds of Ω(√n) and exp(Ω(√n)), respectively. Our results subsume all previous lower bounds on the threshold degree and sign-rank of AC⁰ circuits of any given depth, with a strict improvement starting at depth 4. As a corollary, we also obtain near-optimal bounds on the discrepancy, threshold weight, and threshold density of AC⁰, strictly subsuming previous work on these quantities. Our work gives some of the strongest lower bounds to date on the communication complexity of AC⁰.

References

[1]

Scott Aaronson and Yaoyun Shi. 2004. Quantum lower bounds for the collision and the element distinctness problems. J. ACM 51, 4 (2004), 595–605.

Digital Library

[2]

Andris Ambainis, Andrew M. Childs, Ben Reichardt, Robert Špalek, and Shengyu Zhang. 2010. Any AND-OR Formula of Size N can be Evaluated in time N 1 /2 +o(1) on a Quantum Computer. SIAM J. Comput. 39, 6 (2010), 2513–2530.

Digital Library

[3]

James Aspnes, Richard Beigel, Merrick L. Furst, and Steven Rudich. 1994. The Expressive Power of Voting Polynomials. Combinatorica 14, 2 (1994), 135–148.

[4]

László Babai, Peter Frankl, and Janos Simon. 1986. Complexity classes in communication complexity theory. In FOCS. 337–347.

Digital Library

[5]

Paul Beame and Trinh Huynh. 2012.

[6]

Multiparty Communication Complexity and Threshold Circuit Size of AC 0. SIAM J. Comput. 41, 3 (2012), 484–518.

[7]

Harry Buhrman, Nikolai K. Vereshchagin, and R. de Wolf. 2007. On computation and communication with small bias. In CCC. 24–32.

Digital Library

[8]

Mark Bun, Robin Kothari, and Justin Thaler. 2018. The polynomial method strikes back: Tight quantum query bounds via dual polynomials. In STOC. 297–310.

[9]

Mark Bun and Justin Thaler. 2015. Hardness Amplification and the Approximate Degree of Constant-Depth Circuits. In ICALP. 268–280.

[10]

Mark Bun and Justin Thaler. 2016.

[11]

Approximate Degree and the Complexity of Depth Three Circuits. In Electronic Colloquium on Computational Complexity (ECCC). Report TR16-121.

[12]

Mark Bun and Justin Thaler. 2016. Improved Bounds on the Sign-Rank of AC 0. In ICALP. 37:1–37:14.

[13]

Mark Bun and Justin Thaler. 2017.

[14]

A Nearly Optimal Lower Bound on the Approximate Degree of AC 0. In FOCS. 1–12.

[15]

Mark Bun and Justin Thaler. 2018. The Large-Error Approximate Degree of AC 0. In Electronic Colloquium on Computational Complexity (ECCC). Report TR18-143.

[16]

Arkadev Chattopadhyay. 2007. Discrepancy and the power of bottom fan-in in depth-three circuits. In FOCS. 449–458.

[17]

Jürgen Forster. 2002. A linear lower bound on the unbounded error probabilistic communication complexity. J. Comput. Syst. Sci. 65, 4 (2002), 612–625.

Digital Library

[18]

Jürgen Forster, Matthias Krause, Satyanarayana V. Lokam, Rustam Mubarakzjanov, Niels Schmitt, and Hans-Ulrich Simon. 2001. Relations between communication complexity, linear arrangements, and computational complexity. In Proc. of the 21st Conf. on Foundations of Software Technology and Theoretical Computer Science (FST TCS). 171–182.

Digital Library

[19]

Adam R. Klivans and Rocco A. Servedio. 2004. Learning DNF in time 2 ˜ O(n1/3). J. Comput. Syst. Sci. 68, 2 (2004), 303–318.

Digital Library

[20]

Adam R. Klivans and Rocco A. Servedio. 2006. Toward Attribute Efficient Learning of Decision Lists and Parities. J. Machine Learning Research 7 (2006), 587–602.

Digital Library

[21]

Matthias Krause and Pavel Pudlák. 1997. On the Computational Power of Depth- 2 Circuits with Threshold and Modulo Gates. Theor. Comput. Sci. 174, 1–2 (1997), 137–156.

Digital Library

[22]

Eyal Kushilevitz and Noam Nisan. 1997.

[23]

Communication complexity. Cambridge University Press.

[24]

Troy Lee. 2009.

[25]

A note on the sign degree of formulas. Available at http: //arxiv.org/abs/0909.4607.

[26]

Marvin L. Minsky and Seymour A. Papert. 1969.

[27]

Perceptrons: An Introduction to Computational Geometry. MIT Press, Cambridge, Mass.

Digital Library

[28]

Noam Nisan and Mario Szegedy. 1994. On the degree of Boolean functions as real polynomials. Computational Complexity 4 (1994), 301–313.

Digital Library

[29]

Ryan O’Donnell and Rocco A. Servedio. 2010. New degree bounds for polynomial threshold functions. Combinatorica 30, 3 (2010), 327–358.

Digital Library

[30]

Ramamohan Paturi. 1992. On the degree of polynomials that approximate symmetric Boolean functions. In STOC. 468–474.

Digital Library

[31]

Ramamohan Paturi and Janos Simon. 1986. Probabilistic communication complexity. J. Comput. Syst. Sci. 33, 1 (1986), 106–123.

Digital Library

[32]

Alexander A. Razborov and Alexander A. Sherstov. 2010. The sign-rank of AC 0. SIAM J. Comput. 39, 5 (2010), 1833–1855. Preliminary version in FOCS, 2008.

Digital Library

[33]

Alexander A. Sherstov. 2008. Halfspace matrices. Computational Complexity 17, 2 (2008), 149–178. Preliminary version in CCC, 2007.

Digital Library

[34]

Alexander A. Sherstov. 2009.

[35]

Separating AC 0 from depth- 2 majority circuits. SIAM J. Comput. 38, 6 (2009), 2113–2129. Preliminary version in STOC, 2007.

Digital Library

[36]

Alexander A. Sherstov. 2010. Communication Complexity Under Product and Nonproduct Distributions. Computational Complexity 19, 1 (2010), 135–150. Preliminary version in CCC, 2008.

Digital Library

[37]

Alexander A. Sherstov. 2011. The pattern matrix method. SIAM J. Comput. 40, 6 (2011), 1969–2000.

Digital Library

[38]

Preliminary version in STOC, 2008.

[39]

Alexander A. Sherstov. 2012.

[40]

Strong Direct Product Theorems for Quantum Communication and Query Complexity. SIAM J. Comput. 41, 5 (2012), 1122–1165.

[41]

Preliminary version in STOC, 2011.

[42]

Alexander A. Sherstov. 2013. The intersection of two halfspaces has high threshold degree. SIAM J. Comput. 42, 6 (2013), 2329–2374. Preliminary version in FOCS, 2009.

Digital Library

[43]

Alexander A. Sherstov. 2013.

[44]

Making polynomials robust to noise. Theory of Computing 9 (2013), 593–615. Preliminary version in STOC, 2012.

[45]

Alexander A. Sherstov. 2013. Optimal bounds for sign-representing the intersection of two halfspaces by polynomials. Combinatorica 33, 1 (2013), 73–96. Preliminary version in STOC, 2010.

Digital Library

[46]

Alexander A. Sherstov. 2014. Breaking the Minsky–Papert barrier for constantdepth circuits. In STOC. 223–232. Full version available as ECCC Report TR14-009, January 2014.

[47]

Alexander A. Sherstov. 2014. Communication lower bounds using directional derivatives. J. ACM 61, 6 (2014), 1–71. Preliminary version in STOC, 2013.

Digital Library

[48]

Alexander A. Sherstov. 2015.

[49]

The Power of Asymmetry in Constant-Depth Circuits. In FOCS. 431–450.

[50]

Alexander A. Sherstov. 2016. The multiparty communication complexity of set disjointness. SIAM J. Comput. 45, 4 (2016), 1450–1489. Preliminary version in STOC, 2009.

Digital Library

[51]

Alexander A. Sherstov and Pei Wu. 2019.

[52]

Near-optimal lower bounds on the threshold degree and sign-rank of AC 0. In Electronic Colloquium on Computational Complexity (ECCC). Report TR19-003.

[53]

Justin Thaler. 2016.

Cited By

Diakonikolas IKane DKontonis VLiu SZarifis NMohar BShinkar IO'Donnell R(2024)Super Non-singular Decompositions of Polynomials and Their Application to Robustly Learning Low-Degree PTFsProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649776(152-159)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649776
Hatami HHosseini KMeng XSaha BServedio R(2023)A Borsuk-Ulam Lower Bound for Sign-Rank and Its ApplicationsProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585210(463-471)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585210
Sherstov ALeonardi SGupta A(2022)The approximate degree of DNF and CNF formulasProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3519935.3520000(1194-1207)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519935.3520000
Show More Cited By

Index Terms

Near-optimal lower bounds on the threshold degree and sign-rank of AC⁰
1. Theory of computation
  1. Computational complexity and cryptography

Recommendations

The approximate degree of DNF and CNF formulas
STOC 2022: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing

The approximate degree of a Boolean function f∶{0,1}ⁿ→{0,1} is the minimum degree of a real polynomial p that approximates f pointwise: |f(x)−p(x)|≤1/3 for all x∈{0,1}ⁿ. For any δ>0, we construct DNF and CNF formulas of polynomial size with approximate ...
Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$

The threshold degree of a Boolean function $f\colon{{\{0,1\}}^n}\to{\{0,1\}}$ is the minimum degree of a real polynomial $p$ that represents $f$ in sign: ${sgn}\,p(x)=(-1)^{f(x)}.$ A related notion is sign-rank, defined for a Boolean matrix $F=[F_{ij}]$ as ...
The Sign-Rank of AC$^0$

The sign-rank of a matrix $A=[A_{ij}]$ with $\pm1$ entries is the least rank of a real matrix $B=[B_{ij}]$ with $A_{ij}B_{ij}>0$ for all $i,j$. We obtain the first exponential lower bound on the sign-rank of a function in $\mathsf{AC}^0$. Namely, let $f(...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC 2019: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing

June 2019

1258 pages

ISBN:9781450367059

DOI:10.1145/3313276

General Chair:
Moses Charikar
Stanford University
,
Program Chair:
Edith Cohen
Google, USA / Tel Aviv University, Israel

Copyright © 2019 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 June 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

STOC '19

Sponsor:

SIGACT

STOC '19: 51st Annual ACM SIGACT Symposium on the Theory of Computing

June 23 - 26, 2019

AZ, Phoenix, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
274
Total Downloads

Downloads (Last 12 months)61
Downloads (Last 6 weeks)12

Reflects downloads up to 19 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Diakonikolas IKane DKontonis VLiu SZarifis NMohar BShinkar IO'Donnell R(2024)Super Non-singular Decompositions of Polynomials and Their Application to Robustly Learning Low-Degree PTFsProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649776(152-159)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649776
Hatami HHosseini KMeng XSaha BServedio R(2023)A Borsuk-Ulam Lower Bound for Sign-Rank and Its ApplicationsProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585210(463-471)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585210
Sherstov ALeonardi SGupta A(2022)The approximate degree of DNF and CNF formulasProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3519935.3520000(1194-1207)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519935.3520000
Karp SWinston ELi YSingh ARanzato MBeygelzimer ADauphin YLiang PVaughan J(2021)Local signal adaptivityProceedings of the 35th International Conference on Neural Information Processing Systems10.5555/3540261.3542167(24883-24897)Online publication date: 6-Dec-2021
https://dl.acm.org/doi/10.5555/3540261.3542167
Bun MThaler J(2021)Guest ColumnACM SIGACT News10.1145/3444815.344482551:4(48-72)Online publication date: 14-Jan-2021
https://dl.acm.org/doi/10.1145/3444815.3444825
Kretschmer W(2021)Lower Bounding the AND-OR Tree via SymmetrizationACM Transactions on Computation Theory10.1145/343438513:1(1-11)Online publication date: 21-Jan-2021
https://dl.acm.org/doi/10.1145/3434385

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents