On the public citation graph
The Pattern Matrix Method
0 signed · 172 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.1002/rsa.20232openalex-snapshot
Lower bounds in communication complexity based on factorization norms
inferredcites →https://doi.org/10.1006/inco.1995.1136openalex-snapshot
Boosting a Weak Learning Algorithm by Majority
inferredcites →https://doi.org/10.1007/3-540-45841-7_24openalex-snapshot
Improved Quantum Communication Complexity Bounds for Disjointness and Equality
inferredcites →https://doi.org/10.1007/978-3-540-27819-1_16openalex-snapshot
Toward Attribute Efficient Learning of Decision Lists and Parities
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/978-3-540-74510-5_33openalex-snapshot
Perceptrons of Large Weight
inferredcites →https://doi.org/10.1007/978-3-540-79709-8_27openalex-snapshot
A Uniform Lower Bound on Weights of Perceptrons
inferredcites →https://doi.org/10.1007/978-3-540-85363-3_30openalex-snapshot
Improved Separations between Nondeterministic and Randomized Multiparty Communication
inferredcites →https://doi.org/10.1007/bf00993468openalex-snapshot
Toward efficient agnostic learning
inferredcites →https://doi.org/10.1007/bf01200426openalex-snapshot
Majority gates vs. general weighted threshold gates
inferredcites →https://doi.org/10.1007/bf01206318openalex-snapshot
Fourier analysis for probabilistic communication complexity
inferredcites →https://doi.org/10.1007/bf01215346openalex-snapshot
The expressive power of voting polynomials
inferredcites →https://doi.org/10.1007/bf01263419openalex-snapshot
On the degree of boolean functions as real polynomials
inferredcites →https://doi.org/10.1007/bf01263422openalex-snapshot
Perceptrons, PP, and the polynomial hierarchy
inferredcites →https://doi.org/10.1007/bf01271266openalex-snapshot
Inclusion-exclusion: Exact and approximate
inferredcites →https://doi.org/10.1007/s00037-009-0274-4openalex-snapshot
Approximate Inclusion-Exclusion for Arbitrary Symmetric Functions
inferredcites →https://doi.org/10.1007/s00037-009-0276-2openalex-snapshot
Disjointness is Hard in the Multiparty Number-on-the-Forehead Model
inferredcites →https://doi.org/10.1007/s000370050015openalex-snapshot
Computing Boolean functions by polynomials and threshold circuits
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/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.jcss.2003.07.007openalex-snapshot
Learning DNF in time 2Õ(n1/3)
inferredcites →https://doi.org/10.1016/j.jcss.2003.11.002openalex-snapshot
Learning intersections and thresholds of halfspaces
inferredcites →https://doi.org/10.1016/s0304-3975(01)00144-xopenalex-snapshot
Complexity measures and decision tree complexity: a survey
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.1017/s0963548308009656openalex-snapshot
Learning Complexity vs Communication Complexity
inferredcites →https://doi.org/10.1070/im2003v067n01abeh000422openalex-snapshot
Quantum communication complexity of symmetric predicates
inferredcites →https://doi.org/10.1070/rm1968v023n06abeh001251openalex-snapshot
DUALITY OF CONVEX FUNCTIONS AND EXTREMUM PROBLEMS
inferredcites →https://doi.org/10.1109/ccc.2001.933879openalex-snapshot
Communication complexity lower bounds by polynomials
inferredcites →https://doi.org/10.1109/ccc.2007.18openalex-snapshot
On Computation and Communication with Small Bias
inferredcites →https://doi.org/10.1109/ccc.2008.28openalex-snapshot
Learning Complexity vs. Communication Complexity
inferredcites →https://doi.org/10.1109/ccc.2008.29openalex-snapshot
Disjointness Is Hard in the Multi-party Number-on-the-Forehead Model
inferredcites →https://doi.org/10.1109/istcs.1995.377047openalex-snapshot
Lower bounds for perceptrons solving some separation problems and oracle separation of AM from PP
inferredcites →https://doi.org/10.1109/sfcs.2001.959901openalex-snapshot
Informational complexity and the direct sum problem for simultaneous message complexity
inferredcites →https://doi.org/10.1109/sffcs.1999.814607openalex-snapshot
Bounds for small-error and zero-error quantum algorithms
inferredcites →https://doi.org/10.1109/tec.1961.5219204openalex-snapshot
On the Size of Weights Required for Linear-Input Switching Functions
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.1137/s009753979935476openalex-snapshot
The Quantum Communication Complexity of Sampling
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.1250866openalex-snapshot
Exponential separations for one-way quantum communication complexity, with applications to cryptography
inferredcites →https://doi.org/10.1145/1250790.1250892openalex-snapshot
Lower bounds in communication complexity based on factorization norms
inferredcites →https://doi.org/10.1145/1806689.1806711openalex-snapshot
BQP and the polynomial hierarchy
inferredcites →https://doi.org/10.1145/276698.276713openalex-snapshot
Quantum vs. classical communication and computation
inferredcites →https://doi.org/10.1145/380752.380786openalex-snapshot
Interaction in quantum communication and the complexity of set disjointness
inferredcites →https://doi.org/10.1145/502090.502097openalex-snapshot
Quantum lower bounds by polynomials
inferredcites →https://doi.org/10.1145/780542.780592openalex-snapshot
New degree bounds for polynomial threshold functions
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.2307/253980openalex-snapshot
Theory of Linear and Integer Programming
inferredcites →https://doi.org/10.26421/qic8.10-4openalex-snapshot
A note on quantum algorithms and the minimal degree of epsilon-error polynomials for symmetric functions
inferredcites →https://doi.org/10.26421/qic9.5-6-7openalex-snapshot
Quantum communication complexity of block-composed functions
inferredcites →https://doi.org/10.48550/arxiv.0801.3624openalex-snapshot
Multiparty Communication Complexity of Disjointness
inferredcites →https://doi.org/10.48550/arxiv.0802.3860openalex-snapshot
Separating NOF communication complexity classes RP and NP
inferredcites →https://doi.org/10.48550/arxiv.0805.2135openalex-snapshot
Communication Lower Bounds Using Dual Polynomials
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-031-20624-5_39openalex-snapshot
Bounds on Oblivious Multiparty Quantum Communication Complexity
inferred← citeshttps://doi.org/10.1007/978-3-319-63688-7_24openalex-snapshot
Conditional Disclosure of Secrets: Amplification, Closure, Amortization, Lower-Bounds, and Separations
inferred← citeshttps://doi.org/10.1007/978-3-642-14165-2_41openalex-snapshot
Composition Theorems in Communication Complexity
inferred← citeshttps://doi.org/10.1007/978-3-642-31594-7_68openalex-snapshot
Faster Algorithms for Privately Releasing Marginals
inferred← citeshttps://doi.org/10.1007/978-3-642-32512-0_29openalex-snapshot
Spectral Norm of Symmetric Functions
inferred← citeshttps://doi.org/10.1007/978-3-642-39206-1_26openalex-snapshot
Dual Lower Bounds for Approximate Degree and Markov-Bernstein Inequalities
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/978-3-662-47672-7_22openalex-snapshot
Hardness Amplification and the Approximate Degree of Constant-Depth Circuits
inferred← citeshttps://doi.org/10.1007/978-3-662-47672-7_78openalex-snapshot
Amplification of One-Way Information Complexity via Codes and Noise Sensitivity
inferred← citeshttps://doi.org/10.1007/978-3-662-53015-3_21openalex-snapshot
Bounded Indistinguishability and the Complexity of Recovering Secrets
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-019-00188-1openalex-snapshot
On Derandomized Composition of Boolean Functions
inferred← citeshttps://doi.org/10.1007/s00037-019-00190-7openalex-snapshot
Simulation Theorems via Pseudo-random Properties
inferred← citeshttps://doi.org/10.1007/s00037-024-00250-7openalex-snapshot
KRW Composition Theorems via Lifting
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/s00493-013-2759-7openalex-snapshot
Optimal bounds for sign-representing the intersection of two halfspaces by polynomials
inferred← citeshttps://doi.org/10.1007/s11856-022-2365-8openalex-snapshot
Dimension-free bounds and structural results in communication complexity
inferred← citeshttps://doi.org/10.1007/s11856-023-2517-5openalex-snapshot
Around the log-rank conjecture
inferred← citeshttps://doi.org/10.1016/j.ic.2014.12.003openalex-snapshot
Dual lower bounds for approximate degree and Markov–Bernstein inequalities
inferred← citeshttps://doi.org/10.1016/j.jcss.2016.03.005openalex-snapshot
Hellinger volume and number-on-the-forehead communication complexity
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.2015.70openalex-snapshot
Deterministic Communication vs. Partition Number
inferred← citeshttps://doi.org/10.1109/focs.2016.38openalex-snapshot
Structure of Protocols for XOR Functions
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.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.2018.00014openalex-snapshot
A Short List of Equalities Induces Large Sign Rank
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/focs57990.2023.00047openalex-snapshot
Fourier Growth of Communication Protocols for XOR Functions
inferred← citeshttps://doi.org/10.1109/focs61266.2024.00035openalex-snapshot
The Communication Complexity of Approximating Matrix Rank
inferred← citeshttps://doi.org/10.1109/tit.2025.3534920openalex-snapshot
Quantum and Classical Communication Complexity of Permutation-Invariant Functions
inferred← citeshttps://doi.org/10.1137/100785260openalex-snapshot
The Intersection of Two Halfspaces Has High Threshold Degree
inferred← citeshttps://doi.org/10.1137/110842661openalex-snapshot
Strong Direct Product Theorems for Quantum Communication and Query Complexity
inferred← citeshttps://doi.org/10.1137/120861072openalex-snapshot
An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance
inferred← citeshttps://doi.org/10.1137/120891587openalex-snapshot
The Multiparty Communication Complexity of Set Disjointness
inferred← citeshttps://doi.org/10.1137/15m1015704openalex-snapshot
Breaking the Minsky--Papert Barrier for Constant-Depth Circuits
inferred← citeshttps://doi.org/10.1137/16m1059369openalex-snapshot
Deterministic Communication vs. Partition Number
inferred← citeshttps://doi.org/10.1137/16m1064477openalex-snapshot
The Power of Asymmetry in Constant-Depth Circuits
inferred← citeshttps://doi.org/10.1137/16m1082007openalex-snapshot
Communication Lower Bounds via Critical Block Sensitivity
inferred← citeshttps://doi.org/10.1137/17m1136869openalex-snapshot
Structure of Protocols for XOR Functions
inferred← citeshttps://doi.org/10.1137/17m1152966openalex-snapshot
Approximating Rectangles by Juntas and Weakly Exponential Lower Bounds for LP Relaxations of CSPs
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/18m1217097openalex-snapshot
Conditional Disclosure of Secrets: Amplification, Closure, Amortization, Lower-bounds, and Separations
inferred← citeshttps://doi.org/10.1137/19m1271348openalex-snapshot
A Short List of Equalities Induces Large Sign-Rank
inferred← citeshttps://doi.org/10.1137/19m1310153openalex-snapshot
Query-to-Communication Lifting Using Low-Discrepancy Gadgets
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.1137/24m1638616openalex-snapshot
Quantum Lower Bounds by Sample-to-Query Lifting
inferred← citeshttps://doi.org/10.1145/1806689.1806703openalex-snapshot
Hardness amplification in proof complexity
inferred← citeshttps://doi.org/10.1145/1993636.1993644openalex-snapshot
An optimal lower bound on the communication complexity of gap-hamming-distance
inferred← citeshttps://doi.org/10.1145/2488608.2488628openalex-snapshot
From information to exact communication
inferred← citeshttps://doi.org/10.1145/2488608.2488725openalex-snapshot
Communication lower bounds using directional derivatives
inferred← citeshttps://doi.org/10.1145/2554797.2554833openalex-snapshot
Faster private release of marginals on small databases
inferred← citeshttps://doi.org/10.1145/2591796.2591838openalex-snapshot
Communication lower bounds via critical block sensitivity
inferred← citeshttps://doi.org/10.1145/2591796.2591871openalex-snapshot
Breaking the minsky-papert barrier for constant-depth circuits
inferred← citeshttps://doi.org/10.1145/2611462.2611488openalex-snapshot
Can quantum communication speed up distributed computation?
inferred← citeshttps://doi.org/10.1145/2629334openalex-snapshot
Communication Lower Bounds Using Directional Derivatives
inferred← citeshttps://doi.org/10.1145/2746539.2746596openalex-snapshot
Rectangles Are Nonnegative Juntas
inferred← citeshttps://doi.org/10.1145/3055399.3055438openalex-snapshot
Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs
inferred← citeshttps://doi.org/10.1145/3055399.3055478openalex-snapshot
Strongly exponential lower bounds for monotone computation
inferred← citeshttps://doi.org/10.1145/3188745.3188784openalex-snapshot
The polynomial method strikes back: tight quantum query bounds via dual polynomials
inferred← citeshttps://doi.org/10.1145/3188745.3188914openalex-snapshot
Lifting Nullstellensatz to monotone span programs over any field
inferred← citeshttps://doi.org/10.1145/3313276.3316408openalex-snapshot
Near-optimal lower bounds on the threshold degree and sign-rank of AC 0
inferred← citeshttps://doi.org/10.1145/3341106openalex-snapshot
White-Box vs. Black-Box Complexity of Search Problems
inferred← citeshttps://doi.org/10.1145/3357713.3384297openalex-snapshot
The power of factorization mechanisms in local and central differential privacy
inferred← citeshttps://doi.org/10.1145/3404858openalex-snapshot
A Lower Bound for Sampling Disjoint Sets
inferred← citeshttps://doi.org/10.1145/3470860openalex-snapshot
Improved Bounds on Fourier Entropy and Min-entropy
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.3585216openalex-snapshot
Depth-𝑑 Threshold Circuits vs. Depth-(𝑑+1) AND-OR Trees
inferred← citeshttps://doi.org/10.1145/3662158.3662788openalex-snapshot
On the Power of Quantum Distributed Proofs
inferred← citeshttps://doi.org/10.1145/3798129.3800895openalex-snapshot
Restriction Trees for Sparsity and Applications
inferred← citeshttps://doi.org/10.22331/q-2021-03-07-402openalex-snapshot
Quantum Random Access Codes for Boolean Functions
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.22331/q-2025-10-16-1885openalex-snapshot
Conditional disclosure of secrets with quantum resources
inferred← citeshttps://doi.org/10.26421/qic12.7-8-11openalex-snapshot
The quantum query complexity of AC0
inferred← citeshttps://doi.org/10.26421/qic21.15-16-1openalex-snapshot
Quantum communication complexity of distribution testing
inferred← citeshttps://doi.org/10.4230/lipics.ccc.2016.17openalex-snapshot
On the Sum-of-Squares Degree of Symmetric Quadratic Functions
inferred← citeshttps://doi.org/10.4230/lipics.ccc.2022.1openalex-snapshot
Algebraic Representations of Unique Bipartite Perfect Matching
inferred← citeshttps://doi.org/10.4230/lipics.fsttcs.2017.23openalex-snapshot
A Lifting Theorem with Applications to Symmetric Functions
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.4230/lipics.stacs.2020.45openalex-snapshot
Improved Bounds on Fourier Entropy and Min-Entropy
inferred← citeshttps://doi.org/10.4230/lipics.tqc.2020.1openalex-snapshot
Exponential Quantum Communication Reductions from Generalizations of the Boolean Hidden Matching Problem
inferred← citeshttps://doi.org/10.48550/arxiv.1207.5211openalex-snapshot
Can Quantum Communication Speed Up Distributed Computation?
inferred← citeshttps://doi.org/10.48550/arxiv.1311.2355openalex-snapshot
Communication Lower Bounds via Critical Block Sensitivity
inferred← citeshttps://doi.org/10.48550/arxiv.1503.07261openalex-snapshot
Dual Polynomials for Collision and Element Distinctness
inferred← citeshttps://doi.org/10.48550/arxiv.1611.05754openalex-snapshot
Separating quantum communication and approximate rank
inferred← citeshttps://doi.org/10.48550/arxiv.1705.02397openalex-snapshot
Weights at the Bottom Matter When the Top is Heavy
inferred← citeshttps://doi.org/10.48550/arxiv.1710.01969openalex-snapshot
Simultaneous Multiparty Communication Complexity of Composed Functions
inferred← citeshttps://doi.org/10.48550/arxiv.1807.06256openalex-snapshot
Classical lower bounds from quantum upper bounds
inferred← citeshttps://doi.org/10.48550/arxiv.1903.00544openalex-snapshot
Sign-Rank Can Increase Under Intersection
inferred← citeshttps://doi.org/10.48550/arxiv.2010.11925openalex-snapshot
The Polynomial Method is Universal for Distribution-Free Correlational SQ Learning
inferred← citeshttps://doi.org/10.7916/d8251gb1openalex-snapshot
Analytic Methods in Concrete Complexity
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.