The Sign-Rank of AC^0

DOI10.1137/080744037MaRDI QIDQ3053151zbMATH OpenOpenAlexFDO

Authors Alexander Razborov, Alexander A. Sherstov

Publication date 4 November 2010

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/080744037

zbMATH Keywords

complexity classescommunication complexity\(\mathsf{AC}^0\)\(\mathsf{UPP}^{cc}\)\(\Sigma_2^{cc}\Pi_2^{cc}\)constant-depth AND/OR/NOT circuitssign-rankthreshold-of-majority circuits

Mathematics Subject Classification ID

Computational learning theory (68Q32) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Improved bounds on the sign-rank of \(\mathrm{AC}^0\)
• Near-optimal lower bounds on the threshold degree and sign-rank of \(\mathrm{AC}^0\)
• Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC^0
• scientific article; zbMATH DE number 810046
• Sign rank versus Vapnik-Chervonenkis dimension
• scientific article; zbMATH DE number 772541
• A note on minimum rank and maximum nullity of sign patterns
• Alternating sign matrices of finite multiplicative order
• scientific article; zbMATH DE number 16663
• Rank conditions for sign patterns that allow diagonalizability

Cited in

(38)

• Communication complexity with small advantage
• The hardest halfspace
• Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\)
• Algorithmic Polynomials
• Size, Depth and Energy of Threshold Circuits Computing Parity Function.
• On the power of statistical zero knowledge
• Linear algebraic methods in communication complexity
• Rank conditions for sign patterns that allow diagonalizability
• Sign-rank can increase under intersection
• The power of asymmetry in constant-depth circuits
• Rectangles are nonnegative juntas
• Essential sign change numbers of full sign pattern matrices
• Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC^0
• A short list of equalities induces large sign-rank
• The large-error approximate degree of \(\mathrm{AC}^0\)
• The landscape of communication complexity classes
• Sign rank versus Vapnik-Chervonenkis dimension
• Sign-rank can increase under intersection
• Sign-rank vs. discrepancy
• A nearly optimal lower bound on the approximate degree of \(\mathrm{AC}^0\)
• Query-to-communication lifting for BPP
• The large-error approximate degree of \(\mathrm{AC}^0\)
• Sign rank vs discrepancy
• The polynomial method strikes back: tight quantum query bounds via dual polynomials
• Minimum ranks of sign patterns and zero-nonzero patterns and point-hyperplane configurations
• Breaking the Minsky--Papert Barrier for Constant-Depth Circuits
• Rational realization of the minimum ranks of nonnegative sign pattern matrices.
• Minimum (maximum) rank of sign pattern tensors and sign nonsingular tensors
• Polynomial threshold functions and Boolean threshold circuits
• Improved bounds on the sign-rank of \(\mathrm{AC}^0\)
• A Borsuk-Ulam lower bound for sign-rank and its applications
• Depth-\(d\) threshold circuits vs. depth-\((d+1)\) and-or trees
• Near-optimal lower bounds on the threshold degree and sign-rank of \(\mathrm{AC}^0\)
• Approximate Degree in Classical and Quantum Computing
• Revealed preference dimension via matrix sign rank
• Range avoidance for low-depth circuits and connections to pseudorandomness
• The approximate degree of DNF and CNF formulas
• Sign patterns with minimum rank 2 and upper bounds on minimum ranks

This page was built for publication: The Sign-Rank of AC$^0$

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3053151)