The Sign-Rank of AC$^0$
From MaRDI portal
Publication:3053151
DOI10.1137/080744037zbMath1211.68213OpenAlexW2117822564MaRDI QIDQ3053151
Alexander A. Sherstov, Alexander A. 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
communication complexitycomplexity classes\(\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)
Related Items
Essential sign change numbers of full sign pattern matrices ⋮ Approximate Degree in Classical and Quantum Computing ⋮ Breaking the Minsky--Papert Barrier for Constant-Depth Circuits ⋮ The landscape of communication complexity classes ⋮ The Power of Asymmetry in Constant-Depth Circuits ⋮ A Short List of Equalities Induces Large Sign-Rank ⋮ Communication complexity with small advantage ⋮ Revealed preference dimension via matrix sign rank ⋮ Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\) ⋮ Linear algebraic methods in communication complexity ⋮ Unnamed Item ⋮ Query-to-Communication Lifting for BPP ⋮ A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$ ⋮ On the Power of Statistical Zero Knowledge ⋮ Sign rank versus Vapnik-Chervonenkis dimension ⋮ Algorithmic Polynomials ⋮ New algorithms and lower bounds for circuits with linear threshold gates ⋮ Minimum (maximum) rank of sign pattern tensors and sign nonsingular tensors ⋮ The hardest halfspace ⋮ Size, Depth and Energy of Threshold Circuits Computing Parity Function. ⋮ Optimal bounds for sign-representing the intersection of two halfspaces by polynomials ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Minimum ranks of sign patterns and zero-nonzero patterns and point-hyperplane configurations ⋮ Rectangles Are Nonnegative Juntas ⋮ Polynomial threshold functions and Boolean threshold circuits ⋮ Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$ ⋮ Rank conditions for sign patterns that allow diagonalizability ⋮ Sign rank vs discrepancy ⋮ Rational realization of the minimum ranks of nonnegative sign pattern matrices ⋮ Unnamed Item ⋮ Sign patterns with minimum rank 2 and upper bounds on minimum ranks ⋮ Unnamed Item
