On the public citation graph
The Sign-Rank of AC$^0$
0 signed · 123 inferred · view as graph
Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.
Is this your work? Sign in with ORCID and put your name on the
claims that are yours.
Reference health. See whether every reference in this work resolves to a
known work and none has been retracted — and get a dated CiteStamped
badge you can embed.
What this work says
Outgoing claims: the papers this work cites, builds on, or argues with.
inferredcites →https://doi.org/10.1006/jcss.2001.1786openalex-snapshot
Spectral Methods for Matrix Rigidity with Applications to Size–Depth Trade-offs and Communication Complexity
inferredcites →https://doi.org/10.1007/3-540-44581-1_25openalex-snapshot
Limitations of Learning via Embeddings in Euclidean Half-Spaces
inferredcites →https://doi.org/10.1007/3-540-45294-x_15openalex-snapshot
Relations Between Communication Complexity, Linear Arrangements, and Computational Complexity
inferredcites →https://doi.org/10.1007/978-3-540-72927-3_30openalex-snapshot
A Lower Bound for Agnostically Learning Disjunctions
inferredcites →https://doi.org/10.1007/bf01200426openalex-snapshot
Majority gates vs. general weighted threshold gates
inferredcites →https://doi.org/10.1007/bf01263419openalex-snapshot
On the degree of boolean functions as real polynomials
inferredcites →https://doi.org/10.1007/bf02579325openalex-snapshot
Strong communication complexity or generating quasi-random sequences from two communicating semi-random sources
inferredcites →https://doi.org/10.1007/pl00013833openalex-snapshot
A Polynomial-Time Algorithm for Learning Noisy Linear Threshold Functions
inferredcites →https://doi.org/10.1007/s00493-007-2160-5openalex-snapshot
Complexity measures of sign matrices
inferredcites →https://doi.org/10.1007/s00493-011-2580-0openalex-snapshot
The Unbounded-Error Communication Complexity of Symmetric Functions
inferredcites →https://doi.org/10.1007/s10994-007-5010-1openalex-snapshot
Unconditional lower bounds for learning intersections of halfspaces
inferredcites →https://doi.org/10.1016/0020-0190(91)90157-dopenalex-snapshot
Private vs. common random bits in communication complexity
inferredcites →https://doi.org/10.1016/0020-0190(96)00077-4openalex-snapshot
A subexponential exact learning algorithm for DNF using equivalence queries
inferredcites →https://doi.org/10.1016/0022-0000(86)90046-2openalex-snapshot
Probabilistic communication complexity
inferredcites →https://doi.org/10.1016/0022-0000(93)90001-dopenalex-snapshot
Threshold circuits of bounded depth
inferredcites →https://doi.org/10.1016/0304-3975(92)90260-mopenalex-snapshot
On the distributional complexity of disjointness
inferredcites →https://doi.org/10.1016/j.ipl.2006.11.003openalex-snapshot
Powering requires threshold depth 3
inferredcites →https://doi.org/10.1016/j.jcss.2003.07.007openalex-snapshot
Learning DNF in time 2Õ(n1/3)
inferredcites →https://doi.org/10.1016/j.jcss.2008.07.008openalex-snapshot
Cryptographic hardness for learning intersections of halfspaces
inferredcites →https://doi.org/10.1016/j.tcs.2005.10.015openalex-snapshot
On the smallest possible dimension and the largest possible margin of linear arrangements representing given concept classes
inferredcites →https://doi.org/10.1016/s0022-0000(02)00019-3openalex-snapshot
A linear lower bound on the unbounded error probabilistic communication complexity
inferredcites →https://doi.org/10.1016/s0304-3975(96)00019-9openalex-snapshot
On the computational power of depth-2 circuits with threshold and modulo gates
inferredcites →https://doi.org/10.1037/h0042519openalex-snapshot
The perceptron: A probabilistic model for information storage and organization in the brain.
inferredcites →https://doi.org/10.1080/00401706.1970.10488686openalex-snapshot
An Introduction to the Approximation of Functions
inferredcites →https://doi.org/10.1109/ccc.1999.766279openalex-snapshot
Learning DNF by approximating inclusion-exclusion formulae
inferredcites →https://doi.org/10.1109/ccc.2007.18openalex-snapshot
On Computation and Communication with Small Bias
inferredcites →https://doi.org/10.1109/focs.2004.36openalex-snapshot
Learnability and Automatizability
inferredcites →https://doi.org/10.1109/focs.2006.24openalex-snapshot
Cryptographic Hardness for Learning Intersections of Halfspaces
inferredcites →https://doi.org/10.1109/focs.2006.51openalex-snapshot
New Results for Learning Noisy Parities and Halfspaces
inferredcites →https://doi.org/10.1109/sfcs.1985.30openalex-snapshot
Geometrical realization of set systems and probabilistic communication complexity
inferredcites →https://doi.org/10.1109/sfcs.1986.15openalex-snapshot
Complexity classes in communication complexity theory
inferredcites →https://doi.org/10.1109/sfcs.1996.548492openalex-snapshot
A polynomial-time algorithm for learning noisy linear threshold functions
inferredcites →https://doi.org/10.1137/0217015openalex-snapshot
Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
inferredcites →https://doi.org/10.1137/0405044openalex-snapshot
The Probabilistic Communication Complexity of Set Intersection
inferredcites →https://doi.org/10.1137/08071421xopenalex-snapshot
Separating ${AC}^0$ from Depth-2 Majority Circuits
inferredcites →https://doi.org/10.1137/s0097539702405620openalex-snapshot
Lower Bounds for Quantum Communication Complexity
inferredcites →https://doi.org/10.1145/1008731.1008735openalex-snapshot
Quantum lower bounds for the collision and the element distinctness problems
inferredcites →https://doi.org/10.1145/1250790.1250834openalex-snapshot
Separating AC 0 from depth-2 majority circuits
inferredcites →https://doi.org/10.1145/1374376.1374392openalex-snapshot
The pattern matrix method for lower bounds on quantum communication
inferredcites →https://doi.org/10.1145/167088.167197openalex-snapshot
Cryptographic hardness of distribution-specific learning
inferredcites →https://doi.org/10.1145/174644.174647openalex-snapshot
Cryptographic Limitations on Learning Boolean Formulae and Finite Automata
inferredcites →https://doi.org/10.1145/293347.293351openalex-snapshot
Efficient noise-tolerant learning from statistical queries
inferredcites →https://doi.org/10.1145/780542.780592openalex-snapshot
New degree bounds for polynomial threshold functions
inferredcites →https://doi.org/10.1145/792538.792543openalex-snapshot
Noise-tolerant learning, the parity problem, and the statistical query model
inferredcites →https://doi.org/10.7551/mitpress/3897.001.0001openalex-snapshot
An Introduction to Computational Learning Theory
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1007/978-3-030-04612-5_5openalex-snapshot
Revealed Preference Dimension via Matrix Sign Rank
inferred← citeshttps://doi.org/10.1007/978-3-642-24508-4openalex-snapshot
Boolean Function Complexity: Advances and Frontiers
inferred← citeshttps://doi.org/10.1007/978-3-642-40313-2_46openalex-snapshot
Polynomial Threshold Functions and Boolean Threshold Circuits
inferred← citeshttps://doi.org/10.1007/978-3-662-44522-8_3openalex-snapshot
Communication Complexity Theory: Thirty-Five Years of Set Disjointness
inferred← citeshttps://doi.org/10.1007/s00037-010-0296-yopenalex-snapshot
Lower Bounds for Agnostic Learning via Approximate Rank
inferred← citeshttps://doi.org/10.1007/s00037-018-0166-6openalex-snapshot
The Landscape of Communication Complexity Classes
inferred← citeshttps://doi.org/10.1007/s00037-018-0175-5openalex-snapshot
Query-to-Communication Lifting for PNP
inferred← citeshttps://doi.org/10.1007/s00037-020-00192-wopenalex-snapshot
Communication Complexity with Small Advantage
inferred← citeshttps://doi.org/10.1007/s00493-013-2759-7openalex-snapshot
Optimal bounds for sign-representing the intersection of two halfspaces by polynomials
inferred← citeshttps://doi.org/10.1007/s10587-016-0299-1openalex-snapshot
Rational realization of the minimum ranks of nonnegative sign pattern matrices
inferred← citeshttps://doi.org/10.1016/j.disc.2019.111798openalex-snapshot
Rank conditions for sign patterns that allow diagonalizability
inferred← citeshttps://doi.org/10.1016/j.ic.2014.09.008openalex-snapshot
Polynomial threshold functions and Boolean threshold circuits
inferred← citeshttps://doi.org/10.1016/j.laa.2011.07.008openalex-snapshot
Linear algebraic methods in communication complexity
inferred← citeshttps://doi.org/10.1016/j.laa.2015.05.026openalex-snapshot
Minimum (maximum) rank of sign pattern tensors and sign nonsingular tensors
inferred← citeshttps://doi.org/10.1016/j.laa.2018.08.019openalex-snapshot
Minimum ranks of sign patterns and zero–nonzero patterns and point–hyperplane configurations
inferred← citeshttps://doi.org/10.1017/fms.2014.2openalex-snapshot
IMPROVED RANK BOUNDS FOR DESIGN MATRICES AND A NEW PROOF OF KELLY’S THEOREM
inferred← citeshttps://doi.org/10.1070/sm8780openalex-snapshot
Sign rank versus Vapnik-Chervonenkis dimension
inferred← citeshttps://doi.org/10.1080/03081087.2012.716431openalex-snapshot
Sign patterns with minimum rank 2 and upper bounds on minimum ranks
inferred← citeshttps://doi.org/10.1109/ccc.2011.33openalex-snapshot
On Arthur Merlin Games in Communication Complexity
inferred← citeshttps://doi.org/10.1109/focs.2009.18openalex-snapshot
The Intersection of Two Halfspaces Has High Threshold Degree
inferred← citeshttps://doi.org/10.1109/focs.2015.34openalex-snapshot
The Power of Asymmetry in Constant-Depth Circuits
inferred← citeshttps://doi.org/10.1109/focs.2017.10openalex-snapshot
A Nearly Optimal Lower Bound on the Approximate Degree of AC^0
inferred← citeshttps://doi.org/10.1109/focs.2017.21openalex-snapshot
Query-to-Communication Lifting for BPP
inferred← citeshttps://doi.org/10.1109/focs.2017.71openalex-snapshot
On the Power of Statistical Zero Knowledge
inferred← citeshttps://doi.org/10.1109/focs.2017.73openalex-snapshot
A Time-Space Lower Bound for a Large Class of Learning Problems
inferred← citeshttps://doi.org/10.1109/focs.2018.00014openalex-snapshot
A Short List of Equalities Induces Large Sign Rank
inferred← citeshttps://doi.org/10.1109/focs52979.2021.00098openalex-snapshot
Feature Purification: How Adversarial Training Performs Robust Deep Learning
inferred← citeshttps://doi.org/10.1109/focs57990.2023.00047openalex-snapshot
Fourier Growth of Communication Protocols for XOR Functions
inferred← citeshttps://doi.org/10.1137/100785260openalex-snapshot
The Intersection of Two Halfspaces Has High Threshold Degree
inferred← citeshttps://doi.org/10.1137/15m1015704openalex-snapshot
Breaking the Minsky--Papert Barrier for Constant-Depth Circuits
inferred← citeshttps://doi.org/10.1137/16m1064477openalex-snapshot
The Power of Asymmetry in Constant-Depth Circuits
inferred← citeshttps://doi.org/10.1137/17m1161737openalex-snapshot
A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$
inferred← citeshttps://doi.org/10.1137/19m1271348openalex-snapshot
A Short List of Equalities Induces Large Sign-Rank
inferred← citeshttps://doi.org/10.1137/20m1312459openalex-snapshot
Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$
inferred← citeshttps://doi.org/10.1137/23m1557593openalex-snapshot
The Approximate Degree of DNF and CNF Formulas
inferred← citeshttps://doi.org/10.1145/1993636.1993705openalex-snapshot
Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes
inferred← citeshttps://doi.org/10.1145/2213977.2214044openalex-snapshot
Making polynomials robust to noise
inferred← citeshttps://doi.org/10.1145/2488608.2488694openalex-snapshot
The approximate rank of a matrix and its algorithmic applications
inferred← citeshttps://doi.org/10.1145/2591796.2591858openalex-snapshot
New algorithms and lower bounds for circuits with linear threshold gates
inferred← citeshttps://doi.org/10.1145/2591796.2591871openalex-snapshot
Breaking the minsky-papert barrier for constant-depth circuits
inferred← citeshttps://doi.org/10.1145/2746539.2746596openalex-snapshot
Rectangles Are Nonnegative Juntas
inferred← citeshttps://doi.org/10.1145/3055399.3055484openalex-snapshot
Probabilistic rank and matrix rigidity
inferred← citeshttps://doi.org/10.1145/3470863openalex-snapshot
Sign-rank Can Increase under Intersection
inferred← citeshttps://doi.org/10.1145/3519935.3520000openalex-snapshot
The approximate degree of DNF and CNF formulas
inferred← citeshttps://doi.org/10.1145/3564246.3585210openalex-snapshot
A Borsuk-Ulam Lower Bound for Sign-Rank and Its Applications
inferred← citeshttps://doi.org/10.1145/3564246.3585216openalex-snapshot
Depth-𝑑 Threshold Circuits vs. Depth-(𝑑+1) AND-OR Trees
inferred← citeshttps://doi.org/10.1145/3718745openalex-snapshot
Range Avoidance for Low-Depth Circuits and Connections to Pseudorandomness
inferred← citeshttps://doi.org/10.1162/neco_a_01683openalex-snapshot
Trade-Offs Between Energy and Depth of Neural Networks
inferred← citeshttps://doi.org/10.13001/1081-3810.3077openalex-snapshot
Minimum ranks of sign patterns via sign vectors and duality
inferred← citeshttps://doi.org/10.1561/9781601982599openalex-snapshot
Lower Bounds in Communication Complexity
inferred← citeshttps://doi.org/10.22331/q-2021-09-16-543openalex-snapshot
Quantum algorithms and approximating polynomials for composed functions with shared inputs
inferred← citeshttps://doi.org/10.4213/sm8780openalex-snapshot
Знаковый ранг и размерность Вапника-Червоненкиса
inferred← citeshttps://doi.org/10.4230/lipics.icalp.2019.30openalex-snapshot
Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC^0
inferred← citeshttps://doi.org/10.4230/lipics.itcs.2022.67openalex-snapshot
Small Circuits Imply Efficient Arthur-Merlin Protocols
inferred← citeshttps://doi.org/10.48550/arxiv.1312.6162openalex-snapshot
Sign patterns with minimum rank 3 and point-line configurations
inferred← citeshttps://doi.org/10.48550/arxiv.1503.04486openalex-snapshot
The complexity of computing the minimum rank of a sign pattern matrix
inferred← citeshttps://doi.org/10.48550/arxiv.1903.00544openalex-snapshot
Sign-Rank Can Increase Under Intersection
inferred← citeshttps://doi.org/10.48550/arxiv.2003.04180openalex-snapshot
Approximate is Good Enough: Probabilistic Variants of Dimensional and Margin Complexity
inferred← citeshttps://doi.org/10.57709/8841456openalex-snapshot
Minimum Ranks and Refined Inertias of Sign Pattern Matrices
Editorial review for independent work. ICSAC — the Institute for Complexity
Science and Advanced Computing — runs a structured editorial panel for researchers
publishing outside journals, and publishes on CiteStamp rails. Submission is free
and goes through ORCID: icsacinstitute.org/submit.