On the public citation graph
Spectral Methods for Matrix Rigidity with Applications to Size–Depth Trade-offs and Communication Complexity
0 signed · 110 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.1007/3-540-08353-7_135openalex-snapshot
Graph-theoretic arguments in low-level complexity
inferredcites →https://doi.org/10.1007/978-3-662-03338-8openalex-snapshot
Algebraic Complexity Theory
inferredcites →https://doi.org/10.1007/bf01200057openalex-snapshot
Arithmetization: A new method in structural complexity theory
inferredcites →https://doi.org/10.1007/bf01200404openalex-snapshot
On lower bounds for read-k-times branching programs
inferredcites →https://doi.org/10.1007/bf01215351openalex-snapshot
Communication in bounded depth circuits
inferredcites →https://doi.org/10.1007/bf02311250openalex-snapshot
Improved lower bounds on the rigidity of Hadamard matrices
inferredcites →https://doi.org/10.1007/bfb0020802openalex-snapshot
Randomized polynomials, threshold circuits, and the polynomial hierarchy
inferredcites →https://doi.org/10.1016/0012-365x(94)00115-yopenalex-snapshot
Some combinatorial-algebraic problems from complexity theory
inferredcites →https://doi.org/10.1016/0022-0000(86)90046-2openalex-snapshot
Probabilistic communication complexity
inferredcites →https://doi.org/10.1016/0022-0000(88)90028-1openalex-snapshot
Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
inferredcites →https://doi.org/10.1016/0022-0000(90)90027-iopenalex-snapshot
Relations between communication complexity classes
inferredcites →https://doi.org/10.1016/0304-3975(93)90214-eopenalex-snapshot
Probabilistic polynomials, AC0 functions and the polynomial-time hierarchy
inferredcites →https://doi.org/10.1016/s0020-0190(00)00058-2openalex-snapshot
A note on the use of determinant for proving lower bounds on the size of linear circuits
inferredcites →https://doi.org/10.1016/s0020-0190(97)00190-7openalex-snapshot
A remark on matrix rigidity
inferredcites →https://doi.org/10.1016/s0304-3975(00)00008-6openalex-snapshot
On the rigidity of Vandermonde matrices
inferredcites →https://doi.org/10.1109/fscs.1990.89583openalex-snapshot
ON ACC and threshold circuits
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.1991.185394openalex-snapshot
Lower bounds for polynomial evaluation and interpolation problems
inferredcites →https://doi.org/10.1109/sfcs.1991.185448openalex-snapshot
Variation ranks of communication matrices and lower bounds for depth two circuits having symmetric gates with unbounded fan-in
inferredcites →https://doi.org/10.1109/sfcs.1994.365725openalex-snapshot
A spectral approach to lower bounds
inferredcites →https://doi.org/10.1109/sfcs.1995.492457openalex-snapshot
Spectral methods for matrix rigidity with applications to size-depth tradeoffs and communication complexity
inferredcites →https://doi.org/10.1109/sfcs.1997.646148openalex-snapshot
Tight bounds for depth-two superconcentrators
inferredcites →https://doi.org/10.1137/0218012openalex-snapshot
The Knowledge Complexity of Interactive Proof Systems
inferredcites →https://doi.org/10.1137/0220053openalex-snapshot
PP is as Hard as the Polynomial-Time Hierarchy
inferredcites →https://doi.org/10.1137/s0097539794264809openalex-snapshot
Boolean Circuits, Tensor Ranks, and Communication Complexity
inferredcites →https://doi.org/10.1145/146585.146605openalex-snapshot
Algebraic methods for interactive proof systems
inferredcites →https://doi.org/10.1145/22145.22192openalex-snapshot
Trading group theory for randomness
inferredcites →https://doi.org/10.1145/225058.225290openalex-snapshot
On the complexity of bilinear forms
inferredcites →https://doi.org/10.1145/321752.321761openalex-snapshot
Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform
inferredcites →https://doi.org/10.1145/800135.804414openalex-snapshot
Some complexity questions related to distributive computing(Preliminary Report)
inferredcites →https://doi.org/10.1145/952980.808620openalex-snapshot
ACM doctoral dissertation award
inferredcites →https://doi.org/10.1215/s0012-7094-53-02004-3openalex-snapshot
The variation of the spectrum of a normal matrix
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1006/jcss.1998.1608openalex-snapshot
The Computational Complexity of Some Problems of Linear Algebra
inferred← citeshttps://doi.org/10.1007/11786986_7openalex-snapshot
Lower Bounds on Matrix Rigidity Via a Quantum Argument
inferred← citeshttps://doi.org/10.1007/3-540-48686-0_12openalex-snapshot
On Covering and Rank Problems for Boolean Matrices and Their Applications
inferred← citeshttps://doi.org/10.1007/978-3-540-72927-3_30openalex-snapshot
A Lower Bound for Agnostically Learning Disjunctions
inferred← citeshttps://doi.org/10.1007/978-3-540-74510-5_28openalex-snapshot
On the Complexity of Matrix Rank and Rigidity
inferred← citeshttps://doi.org/10.1007/978-3-642-03685-9_26openalex-snapshot
Deterministic Approximation Algorithms for the Nearest Codeword Problem
inferred← citeshttps://doi.org/10.1007/978-3-642-28914-9_25openalex-snapshot
On Black-Box Reductions between Predicate Encryption Schemes
inferred← citeshttps://doi.org/10.1007/pl00001612openalex-snapshot
The “log rank” conjecture for modular communication complexity
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-011-0029-xopenalex-snapshot
More on Average Case vs Approximation Complexity
inferred← citeshttps://doi.org/10.1007/s00037-013-0061-0openalex-snapshot
Using Elimination Theory to Construct Rigid Matrices
inferred← citeshttps://doi.org/10.1007/s00037-016-0129-8openalex-snapshot
Kolmogorov Width of Discrete Linear Spaces: an Approach to Matrix Rigidity
inferred← citeshttps://doi.org/10.1007/s00037-018-0166-6openalex-snapshot
The Landscape of Communication Complexity Classes
inferred← citeshttps://doi.org/10.1007/s00037-026-00286-xopenalex-snapshot
On Approximate Symmetric Polynomials and Tightness of Homogenization Results
inferred← citeshttps://doi.org/10.1007/s00145-021-09376-1openalex-snapshot
Placing Conditional Disclosure of Secrets in the Communication Complexity Universe
inferred← citeshttps://doi.org/10.1007/s00224-008-9136-8openalex-snapshot
On the Complexity of Matrix Rank and Rigidity
inferred← citeshttps://doi.org/10.1007/s00453-015-0104-9openalex-snapshot
Zero-Information Protocols and Unambiguity in Arthur–Merlin Communication
inferred← citeshttps://doi.org/10.1007/s00493-007-2160-5openalex-snapshot
Complexity measures of sign matrices
inferred← citeshttps://doi.org/10.1007/s00493-011-2580-0openalex-snapshot
The Unbounded-Error Communication Complexity of Symmetric Functions
inferred← citeshttps://doi.org/10.1007/s10208-015-9258-8openalex-snapshot
Complexity of Linear Circuits and Geometry
inferred← citeshttps://doi.org/10.1007/s11750-013-0283-yopenalex-snapshot
A variational approach of the rank function
inferred← citeshttps://doi.org/10.1016/j.aim.2008.03.023openalex-snapshot
Shadows and intersections: Stability and new proofs
inferred← citeshttps://doi.org/10.1016/j.ic.2026.105416openalex-snapshot
A hierarchy of constant communication complexity
inferred← citeshttps://doi.org/10.1016/j.ipl.2006.10.011openalex-snapshot
On approximation by ⊕-OBDDs
inferred← citeshttps://doi.org/10.1016/j.ipl.2008.02.010openalex-snapshot
Rigidity of a simple extended lower triangular matrix
inferred← citeshttps://doi.org/10.1016/j.jcss.2003.07.007openalex-snapshot
Learning DNF in time 2Õ(n1/3)
inferred← citeshttps://doi.org/10.1016/j.jcss.2009.09.003openalex-snapshot
Min-rank conjecture for log-depth circuits
inferred← citeshttps://doi.org/10.1016/s0304-3975(00)00008-6openalex-snapshot
On the rigidity of Vandermonde matrices
inferred← citeshttps://doi.org/10.1090/s0273-0979-06-01126-8openalex-snapshot
Expander graphs and their applications
inferred← citeshttps://doi.org/10.1103/physreva.110.052204openalex-snapshot
Constructive nonlocal games with very small classical values
inferred← citeshttps://doi.org/10.1109/ccc.2007.18openalex-snapshot
On Computation and Communication with Small Bias
inferred← citeshttps://doi.org/10.1109/ccc.2011.38openalex-snapshot
Noisy Interpolation of Sparse Polynomials, and Applications
inferred← citeshttps://doi.org/10.1109/ccc.2013.28openalex-snapshot
On Rigid Matrices and U-polynomials
inferred← citeshttps://doi.org/10.1109/focs.2017.71openalex-snapshot
On the Power of Statistical Zero Knowledge
inferred← citeshttps://doi.org/10.1109/focs.2019.00067openalex-snapshot
Efficient Construction of Rigid Matrices Using an NP Oracle
inferred← citeshttps://doi.org/10.1109/sfcs.2002.1181991openalex-snapshot
Lower bounds on the bounded coefficient complexity of bilinear maps
inferred← citeshttps://doi.org/10.1109/sfcs.2003.1238204openalex-snapshot
More on average case vs approximation complexity
inferred← citeshttps://doi.org/10.1137/1.9781611975482.1openalex-snapshot
Fine-grained Complexity Meets IP = PSPACE
inferred← citeshttps://doi.org/10.1137/1.9781611977554.ch160openalex-snapshot
Smaller Low-Depth Circuits for Kronecker Powers
inferred← citeshttps://doi.org/10.1137/17m112289xopenalex-snapshot
Verifiable Stream Computation and Arthur--Merlin Communication
inferred← citeshttps://doi.org/10.1137/20m1322297openalex-snapshot
Efficient Construction of Rigid Matrices Using an NP Oracle
inferred← citeshttps://doi.org/10.1137/21m1443339openalex-snapshot
Kronecker Products, Low-Depth Circuits, and Matrix Rigidity
inferred← citeshttps://doi.org/10.1145/1374376.1374479openalex-snapshot
Elusive functions and lower bounds for arithmetic circuits
inferred← citeshttps://doi.org/10.1145/2688073.2688074openalex-snapshot
Zero-Information Protocols and Unambiguity in Arthur-Merlin Communication
inferred← citeshttps://doi.org/10.1145/3055399.3055484openalex-snapshot
Probabilistic rank and matrix rigidity
inferred← citeshttps://doi.org/10.1145/3406325.3451008openalex-snapshot
Kronecker products, low-depth circuits, and matrix rigidity
inferred← citeshttps://doi.org/10.1145/3625226openalex-snapshot
Fast, Algebraic Multivariate Multipoint Evaluation in Small Characteristic and Applications
inferred← citeshttps://doi.org/10.1145/3717823.3718287openalex-snapshot
Low Rank Matrix Rigidity: Tight Lower Bounds and Hardness Amplification
inferred← citeshttps://doi.org/10.1145/990308.990311openalex-snapshot
Lower bounds on the bounded coefficient complexity of bilinear maps
inferred← citeshttps://doi.org/10.1561/0400000011openalex-snapshot
Complexity Lower Bounds using Linear Algebra
inferred← citeshttps://doi.org/10.32657/10356/66033openalex-snapshot
Contributions to the study of probabilistic communication complexity classes
inferred← citeshttps://doi.org/10.4213/mzm1314openalex-snapshot
Новые нижние оценки устойчивости матриц Адамара
inferred← citeshttps://doi.org/10.48550/arxiv.0910.3376openalex-snapshot
Quantum Proofs for Classical Theorems
inferred← citeshttps://doi.org/10.48550/arxiv.1205.0903openalex-snapshot
A note on a problem in communication complexity
inferred← citeshttps://doi.org/10.48550/arxiv.1310.1362openalex-snapshot
Complexity of linear circuits and geometry
inferred← citeshttps://doi.org/10.48550/arxiv.1611.05558openalex-snapshot
Probabilistic Rank and Matrix Rigidity
inferred← citeshttps://doi.org/10.48550/arxiv.2011.09093openalex-snapshot
Block Rigidity: Strong Multiplayer Parallel Repetition implies Super-Linear Lower Bounds for Turing Machines
inferred← citeshttps://doi.org/10.48550/arxiv.cs/0301016openalex-snapshot
Lower Bounds on the Bounded Coefficient Complexity of Bilinear Maps
inferred← citeshttps://doi.org/10.48550/arxiv.cs/0506081openalex-snapshot
Three lines proof of the lower bound for the matrix rigidity
inferred← citeshttps://doi.org/10.53846/goediss-2588openalex-snapshot
Obere und untere Schranken für eingeschränkte Parity-Branchingprogramme
inferred← citeshttps://doi.org/10.62056/avl86cy6bopenalex-snapshot
Lower bounds on the performance of hardware circuits computing the Möbius transform
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.