The Sign-Rank of AC^0
DOI10.1137/080744037zbMATH Open1211.68213OpenAlexW2117822564MaRDI QIDQ3053151FDOQ3053151
Alexander A. Sherstov, Alexander Razborov
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
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
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
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)
Cited In (35)
- A Short List of Equalities Induces Large Sign-Rank
- The hardest halfspace
- Title not available (Why is that?)
- Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\)
- Algorithmic Polynomials
- Title not available (Why is that?)
- Title not available (Why is that?)
- A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$
- Size, Depth and Energy of Threshold Circuits Computing Parity Function.
- Title not available (Why is that?)
- Query-to-Communication Lifting for BPP
- Linear algebraic methods in communication complexity
- Rank conditions for sign patterns that allow diagonalizability
- Rectangles are nonnegative juntas
- Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$
- New algorithms and lower bounds for circuits with linear threshold gates
- Essential sign change numbers of full sign pattern matrices
- Sign rank versus Vapnik-Chervonenkis dimension
- The landscape of communication complexity classes
- Sign rank vs discrepancy
- Title not available (Why is that?)
- Breaking the Minsky--Papert Barrier for Constant-Depth Circuits
- Minimum ranks of sign patterns and zero-nonzero patterns and point-hyperplane configurations
- The Power of Asymmetry in Constant-Depth Circuits
- On the Power of Statistical Zero Knowledge
- Minimum (maximum) rank of sign pattern tensors and sign nonsingular tensors
- Optimal bounds for sign-representing the intersection of two halfspaces by polynomials
- A Borsuk-Ulam lower bound for sign-rank and its applications
- Depth-\(d\) threshold circuits vs. depth-\((d+1)\) and-or trees
- Polynomial threshold functions and Boolean threshold circuits
- Approximate Degree in Classical and Quantum Computing
- Revealed preference dimension via matrix sign rank
- Rational realization of the minimum ranks of nonnegative sign pattern matrices
- Sign patterns with minimum rank 2 and upper bounds on minimum ranks
- Communication complexity with small advantage
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)
