On the public citation graph
Applications of matrix methods to the theory of lower bounds in computational complexity
0 signed · 119 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/bf02122563openalex-snapshot
The gap between monotone and non-monotone circuit complexity is exponential
inferredcites →https://doi.org/10.1007/bf02579196openalex-snapshot
The monotone circuit complexity of boolean functions
inferredcites →https://doi.org/10.1016/0020-0190(83)90011-xopenalex-snapshot
Relating monotone formula size and monotone depth of boolean functions
inferredcites →https://doi.org/10.1016/s0019-9958(82)90766-5openalex-snapshot
Fast parallel matrix and GCD computations
inferredcites →https://doi.org/10.1090/s0002-9939-1967-0207568-xopenalex-snapshot
A combinatorial problem in the 𝑘-adic number system
inferredcites →https://doi.org/10.1109/sfcs.1986.15openalex-snapshot
Complexity classes in communication complexity theory
inferredcites →https://doi.org/10.1137/0403021openalex-snapshot
Monotone Circuits for Connectivity Require Super-Logarithmic Depth
inferredcites →https://doi.org/10.1145/62212.62226openalex-snapshot
On different modes of communication
inferredcites →https://doi.org/10.1145/62212.62265openalex-snapshot
Monotone circuits for connectivity require super-logarithmic depth
inferredcites →https://doi.org/10.1145/800061.808742openalex-snapshot
On notions of information transfer in VLSI circuits
inferredcites →https://doi.org/10.1145/800070.802208openalex-snapshot
Las Vegas Is better than Determinism in VLSI and Distributed Computing
inferredcites →https://doi.org/10.1145/800135.804414openalex-snapshot
Some complexity questions related to distributive computing(Preliminary Report)
inferredcites →https://doi.org/10.2307/2035248openalex-snapshot
A Combinatorial Problem in the k-Adic Number System
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1002/9783527670468.ch05openalex-snapshot
Computational Complexity of Graphs
inferred← citeshttps://doi.org/10.1007/11523468_87openalex-snapshot
Tight Lower Bounds for Query Processing on Streaming and External Memory Data
inferred← citeshttps://doi.org/10.1007/11537311_1openalex-snapshot
The Complexity of Querying External Memory and Streaming Data
inferred← citeshttps://doi.org/10.1007/11537311_4openalex-snapshot
On the Incompressibility of Monotone DNFs
inferred← citeshttps://doi.org/10.1007/3-540-58715-2_130openalex-snapshot
My favorite ten complexity theorems of the past decade
inferred← citeshttps://doi.org/10.1007/978-1-4612-2566-9_12openalex-snapshot
Bounded Arithmetic and Lower Bounds in Boolean Complexity
inferred← citeshttps://doi.org/10.1007/978-3-030-26951-7_1openalex-snapshot
The Communication Complexity of Threshold Private Set Intersection
inferred← citeshttps://doi.org/10.1007/978-3-030-64381-2_10openalex-snapshot
Zero-Communication Reductions
inferred← citeshttps://doi.org/10.1007/978-3-540-24676-3_1openalex-snapshot
Efficient Private Matching and Set Intersection
inferred← citeshttps://doi.org/10.1007/978-3-540-49382-2_29openalex-snapshot
Remarks on Graph Complexity
inferred← citeshttps://doi.org/10.1007/978-3-540-70918-3_13openalex-snapshot
A New Rank Technique for Formula Size Lower Bounds
inferred← citeshttps://doi.org/10.1007/978-3-642-01877-0_3openalex-snapshot
Binary Covering Arrays and Existentially Closed Graphs
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-662-44522-8_3openalex-snapshot
Communication Complexity Theory: Thirty-Five Years of Set Disjointness
inferred← citeshttps://doi.org/10.1007/bf01204724openalex-snapshot
A combinatorial approach to complexity
inferred← citeshttps://doi.org/10.1007/bf01206317openalex-snapshot
Super-logarithmic depth lower bounds via the direct sum in communication complexity
inferred← citeshttps://doi.org/10.1007/bf01261326openalex-snapshot
Orthogonal representations over finite fields and the chromatic number of graphs
inferred← citeshttps://doi.org/10.1007/s00037-006-0212-7openalex-snapshot
THE QUANTUM ADVERSARY METHOD AND CLASSICAL FORMULA SIZE LOWER BOUNDS
inferred← citeshttps://doi.org/10.1007/s00037-017-0159-xopenalex-snapshot
Toward the KRW Composition Conjecture: Cubic Formula Lower Bounds via Communication Complexity
inferred← citeshttps://doi.org/10.1007/s00037-019-00177-4openalex-snapshot
Prediction from Partial Information and Hindsight, with Application to Circuit Lower Bounds
inferred← citeshttps://doi.org/10.1007/s00037-019-00188-1openalex-snapshot
On Derandomized Composition of Boolean Functions
inferred← citeshttps://doi.org/10.1007/s00037-024-00250-7openalex-snapshot
KRW Composition Theorems via Lifting
inferred← citeshttps://doi.org/10.1007/s000370100001openalex-snapshot
A characterization of span program size and improved lower bounds for monotone span programs
inferred← citeshttps://doi.org/10.1007/s00145-014-9190-0openalex-snapshot
Efficient Set Intersection with Simulation-Based Security
inferred← citeshttps://doi.org/10.1007/s00145-021-09410-2openalex-snapshot
On Abelian and Homomorphic Secret Sharing Schemes
inferred← citeshttps://doi.org/10.1007/s00224-002-1068-0openalex-snapshot
Graph Complexity and Slice Functions
inferred← citeshttps://doi.org/10.1007/s00224-007-2013-zopenalex-snapshot
On the Incompressibility of Monotone DNFs
inferred← citeshttps://doi.org/10.1007/s10623-018-0529-7openalex-snapshot
Local bounds for the optimal information ratio of secret sharing schemes
inferred← citeshttps://doi.org/10.1007/s11047-021-09857-zopenalex-snapshot
Communication complexity meets cellular automata: Necessary conditions for intrinsic universality
inferred← citeshttps://doi.org/10.1016/0012-365x(94)00115-yopenalex-snapshot
Some combinatorial-algebraic problems from complexity theory
inferred← citeshttps://doi.org/10.1016/0893-6080(96)00130-xopenalex-snapshot
On the Circuit Complexity of Sigmoid Feedforward Neural Networks
inferred← citeshttps://doi.org/10.1016/b978-0-444-88071-0.50019-9openalex-snapshot
The Complexity of Finite Functions
inferred← citeshttps://doi.org/10.1016/j.disc.2008.09.036openalex-snapshot
On covering graphs by complete bipartite subgraphs
inferred← citeshttps://doi.org/10.1016/j.disc.2010.06.042openalex-snapshot
Subspace intersection graphs
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.01.014openalex-snapshot
The communication complexity of the Hamming distance problem
inferred← citeshttps://doi.org/10.1016/j.ipl.2012.02.009openalex-snapshot
On the nonnegative rank of distance matrices
inferred← citeshttps://doi.org/10.1016/j.jcss.2018.04.005openalex-snapshot
On the limits of gate elimination
inferred← citeshttps://doi.org/10.1016/j.jcss.2024.103615openalex-snapshot
Relating description complexity to entropy
inferred← citeshttps://doi.org/10.1016/j.tcs.2007.02.062openalex-snapshot
Tight lower bounds for query processing on streaming and external memory data
inferred← citeshttps://doi.org/10.1016/j.tcs.2010.02.004openalex-snapshot
On convex complexity measures
inferred← citeshttps://doi.org/10.1016/j.tcs.2012.02.005openalex-snapshot
A stronger LP bound for formula size lower bounds via clique constraints
inferred← citeshttps://doi.org/10.1016/s0020-0190(03)00334-xopenalex-snapshot
A note on monotone complexity and the rank of matrices
inferred← citeshttps://doi.org/10.1016/s0065-2458(08)60342-3openalex-snapshot
Communication Complexity
inferred← citeshttps://doi.org/10.1017/s0960129523000415openalex-snapshot
Game characterizations for the number of quantifiers
inferred← citeshttps://doi.org/10.1017/s0963548314000704openalex-snapshot
Query Complexity of Sampling and Small Geometric Partitions
inferred← citeshttps://doi.org/10.1070/rm2003v058n05abeh000667openalex-snapshot
Monotone Boolean functions
inferred← citeshttps://doi.org/10.1080/11663081.2016.1144016openalex-snapshot
The succinctness of the cover modality
inferred← citeshttps://doi.org/10.1093/jigpal/jzaa068openalex-snapshot
Frame-validity Games and Lower Bounds on the Complexity of Modal Axioms
inferred← citeshttps://doi.org/10.1093/jigpal/jzac044openalex-snapshot
On semantically labelled syntax trees and the non-existence of certain Sahlqvist formulae
inferred← citeshttps://doi.org/10.1093/logcom/exz025openalex-snapshot
Formula size games for modal logic and μ-calculus
inferred← citeshttps://doi.org/10.1109/ccc.2005.29openalex-snapshot
The Quantum Adversary Method and Classical Formula Size Lower Bounds
inferred← citeshttps://doi.org/10.1109/focs.2009.15openalex-snapshot
The Communication Complexity of Set-Disjointness with Small Sets and 0-1 Intersection
inferred← citeshttps://doi.org/10.1109/focs.2016.51openalex-snapshot
Exponential Lower Bounds for Monotone Span Programs
inferred← citeshttps://doi.org/10.1109/focs.2016.67openalex-snapshot
Extension Complexity of Independent Set Polytopes
inferred← citeshttps://doi.org/10.1109/focs.2019.00054openalex-snapshot
More Barriers for Rank Methods, via a "numeric to Symbolic" Transfer
inferred← citeshttps://doi.org/10.1109/focs46700.2020.00011openalex-snapshot
Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity
inferred← citeshttps://doi.org/10.1109/focs46700.2020.00013openalex-snapshot
KRW Composition Theorems via Lifting
inferred← citeshttps://doi.org/10.1109/focs57990.2023.00064openalex-snapshot
Toward Better Depth Lower Bounds: A KRW-like theorem for Strong Composition
inferred← citeshttps://doi.org/10.1109/sct.1991.160273openalex-snapshot
Super-logarithmic depth lower bounds via direct sum in communication complexity
inferred← citeshttps://doi.org/10.1109/sct.1992.215401openalex-snapshot
Fractional covers and communication complexity
inferred← citeshttps://doi.org/10.1109/sfcs.1989.63535openalex-snapshot
Probabilistic communication complexity of Boolean relations
inferred← citeshttps://doi.org/10.1109/sfcs.1994.365685openalex-snapshot
A lower bound for the monotone depth of connectivity
inferred← citeshttps://doi.org/10.1109/sfcs.2003.1238216openalex-snapshot
Separating the power of monotone span programs over different fields
inferred← citeshttps://doi.org/10.1134/s1990478915040146openalex-snapshot
Sufficient conditions for the local repetition-freeness of minimal π-schemes realizing linear Boolean functions
inferred← citeshttps://doi.org/10.1134/s1990478918030146openalex-snapshot
Complexity of the Realization of a Linear Boolean Function in the Class of π-Schemes
inferred← citeshttps://doi.org/10.1134/s1990478919040148openalex-snapshot
On the Perfectness of Minimal Regular Partitions of the Edge Set of the n-Dimensional Cube
inferred← citeshttps://doi.org/10.1134/s1990478922040160openalex-snapshot
Representations of Normalized Formulas
inferred← citeshttps://doi.org/10.1137/15m1018319openalex-snapshot
Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation
inferred← citeshttps://doi.org/10.1137/23m158615xopenalex-snapshot
Toward Better Depth Lower Bounds: A KRW-like Theorem For Strong Composition
inferred← citeshttps://doi.org/10.1137/s0097539704444038openalex-snapshot
Separating the Power of Monotone Span Programs over Different Fields
inferred← citeshttps://doi.org/10.1137/s0097539792235864openalex-snapshot
Amortized Communication Complexity
inferred← citeshttps://doi.org/10.1137/s0097539794261556openalex-snapshot
The Shrinkage Exponent of de Morgan Formulas is 2
inferred← citeshttps://doi.org/10.1145/129712.129732openalex-snapshot
Randomized versus nondeterministic communication complexity
inferred← citeshttps://doi.org/10.1145/129712.129771openalex-snapshot
The history and status of the P versus NP question
inferred← citeshttps://doi.org/10.1145/167088.167230openalex-snapshot
Characterizing non-deterministic circuit size
inferred← citeshttps://doi.org/10.1145/2591796.2591856openalex-snapshot
Toward better formula lower bounds
inferred← citeshttps://doi.org/10.1145/276698.276855openalex-snapshot
A characterization of span program size and improved lower bounds for monotone span programs
inferred← citeshttps://doi.org/10.1145/3055399.3055478openalex-snapshot
Strongly exponential lower bounds for monotone computation
inferred← citeshttps://doi.org/10.1145/3188745.3188914openalex-snapshot
Lifting Nullstellensatz to monotone span programs over any field
inferred← citeshttps://doi.org/10.1145/3305274openalex-snapshot
Characterization and Lower Bounds for Branching Program Size using Projective Dimension
inferred← citeshttps://doi.org/10.1145/3661814.3662125openalex-snapshot
From Quantifier Depth to Quantifier Number: Separating Structures with k Variables
inferred← citeshttps://doi.org/10.1145/3717823.3718229openalex-snapshot
Supercritical Tradeoffs for Monotone Circuits
inferred← citeshttps://doi.org/10.1145/3717823.3718271openalex-snapshot
Truly Supercritical Trade-Offs for Resolution, Cutting Planes, Monotone Circuits, and Weisfeiler–Leman
inferred← citeshttps://doi.org/10.1561/0400000011openalex-snapshot
Complexity Lower Bounds using Linear Algebra
inferred← citeshttps://doi.org/10.21236/ada461119openalex-snapshot
Private and Threshold Set-Intersection
inferred← citeshttps://doi.org/10.33048/daio.2019.26.662openalex-snapshot
On the perfectness of minimal regular partitions of the edge set of the $n$-dimensional cube
inferred← citeshttps://doi.org/10.4171/jca/66openalex-snapshot
Polystability in positive characteristic and degree lower bounds for invariant rings
inferred← citeshttps://doi.org/10.4204/eptcs.346.17openalex-snapshot
Games for Succinctness of Regular Expressions
inferred← citeshttps://doi.org/10.48550/arxiv.1211.0328openalex-snapshot
Some lower bounds for the $L$-intersection number of graphs
inferred← citeshttps://doi.org/10.48550/arxiv.1708.03770openalex-snapshot
Succinctness in subsystems of the spatial mu-calculus
inferred← citeshttps://doi.org/10.48550/arxiv.1710.09502openalex-snapshot
Barriers for Rank Methods in Arithmetic Complexity
inferred← citeshttps://doi.org/10.5555/982792.982797openalex-snapshot
The Bloomier filter: an efficient data structure for static support lookup tables
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.