On the public citation graph
On rank vs. communication complexity
0 signed · 148 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/jgt.3190130413openalex-snapshot
A counterexample to the rank‐coloring conjecture
inferredcites →https://doi.org/10.1007/bf01192528openalex-snapshot
On the ?log rank?-conjecture in communication complexity
inferredcites →https://doi.org/10.1016/0012-365x(88)90199-9openalex-snapshot
On conjectures of Graffiti
inferredcites →https://doi.org/10.1016/0012-365x(92)90691-8openalex-snapshot
The gap between the chromatic number of a graph and the rank of its adjacency matrix is superlinear
inferredcites →https://doi.org/10.1016/0304-3975(92)90260-mopenalex-snapshot
On the distributional complexity of disjointness
inferredcites →https://doi.org/10.1080/00029890.1976.11994095openalex-snapshot
A Bound for the Chromatic Number of a Graph
inferredcites →https://doi.org/10.1109/psct.1987.10319253openalex-snapshot
Tite Probabilistic Communication Complexity of Set Intersection (Preliminary Version)
inferredcites →https://doi.org/10.1109/sfcs.1983.30openalex-snapshot
Lower bounds by probabilistic arguments
inferredcites →https://doi.org/10.1109/sfcs.1994.365711openalex-snapshot
On rank vs. communication complexity
inferredcites →https://doi.org/10.1137/0405044openalex-snapshot
The Probabilistic Communication Complexity of Set Intersection
inferredcites →https://doi.org/10.1145/129712.129757openalex-snapshot
On the degree of Boolean functions as real polynomials
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)
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1002/jgt.20367openalex-snapshot
On set intersection representations of graphs
inferred← citeshttps://doi.org/10.1006/inco.2001.3069openalex-snapshot
Communication Complexity Method for Measuring Nondeterminism in Finite Automata
inferred← citeshttps://doi.org/10.1007/3-540-36504-4_9openalex-snapshot
Cryptographic Primitives Enforcing Communication and Storage Complexity
inferred← citeshttps://doi.org/10.1007/978-1-4757-6048-4_47openalex-snapshot
Communication Complexity of Functions on Direct Sums
inferred← citeshttps://doi.org/10.1007/978-3-030-79416-3_7openalex-snapshot
Upper Bounds on Communication in Terms of Approximate Rank
inferred← citeshttps://doi.org/10.1007/978-3-031-59835-7_9openalex-snapshot
The Extension Complexity of Polytopes with Bounded Integral Slack Matrices
inferred← citeshttps://doi.org/10.1007/978-3-031-82014-4_11openalex-snapshot
Ning Cai’s Work on Communication Complexity
inferred← citeshttps://doi.org/10.1007/978-3-319-13749-0_1openalex-snapshot
Ultrametric Vs. Quantum Query Algorithms
inferred← citeshttps://doi.org/10.1007/978-3-319-17142-5_10openalex-snapshot
On the Power of Parity Queries in Boolean Decision Trees
inferred← citeshttps://doi.org/10.1007/978-3-319-21819-9_2openalex-snapshot
Ultrametric Algorithms and Automata
inferred← citeshttps://doi.org/10.1007/978-3-319-63715-0_1openalex-snapshot
Secure Computation Based on Leaky Correlations: High Resilience Setting
inferred← citeshttps://doi.org/10.1007/978-3-540-45138-9_1openalex-snapshot
Distributed Quantum Computing
inferred← citeshttps://doi.org/10.1007/978-3-642-02927-1_33openalex-snapshot
Partition Arguments in Multiparty Communication Complexity
inferred← citeshttps://doi.org/10.1007/978-3-642-36899-8_21openalex-snapshot
Multiparty Communication Complexity of Vector–Valued and Sum–Type Functions
inferred← citeshttps://doi.org/10.1007/978-3-642-38233-8_25openalex-snapshot
Query Complexity of Matroids
inferred← citeshttps://doi.org/10.1007/978-3-642-38236-9_21openalex-snapshot
Any Monotone Property of 3-Uniform Hypergraphs Is Weakly Evasive
inferred← citeshttps://doi.org/10.1007/978-3-662-43948-7_58openalex-snapshot
Approximate Nonnegative Rank Is Equivalent to the Smooth Rectangle Bound
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-981-96-1090-7_11openalex-snapshot
Relations Between Monotone Complexity Measures Based on Decision Tree Complexity
inferred← citeshttps://doi.org/10.1007/bf01192528openalex-snapshot
On the ?log rank?-conjecture in communication complexity
inferred← citeshttps://doi.org/10.1007/bfb0029950openalex-snapshot
Communication complexity and sequential computation
inferred← citeshttps://doi.org/10.1007/pl00001612openalex-snapshot
The “log rank” conjecture for modular communication complexity
inferred← citeshttps://doi.org/10.1007/s00037-018-0176-4openalex-snapshot
Approximate Nonnegative Rank is Equivalent to the Smooth Rectangle Bound
inferred← citeshttps://doi.org/10.1007/s00037-019-00188-1openalex-snapshot
On Derandomized Composition of Boolean Functions
inferred← citeshttps://doi.org/10.1007/s00208-026-03355-2openalex-snapshot
Factorization norms and an inverse theorem for MaxCut
inferred← citeshttps://doi.org/10.1007/s00224-023-10158-4openalex-snapshot
Upper Bounds on Communication in Terms of Approximate Rank
inferred← citeshttps://doi.org/10.1007/s00493-012-2746-4openalex-snapshot
A counterexample to the Alon-Saks-Seymour conjecture and related problems
inferred← citeshttps://doi.org/10.1007/s00493-015-2922-4openalex-snapshot
On order and rank of graphs
inferred← citeshttps://doi.org/10.1007/s11128-019-2297-3openalex-snapshot
Evaluation of exact quantum query complexities by semidefinite programming
inferred← citeshttps://doi.org/10.1007/s11856-023-2505-9openalex-snapshot
Bipartite perfect matching as a real polynomial
inferred← citeshttps://doi.org/10.1007/s11856-023-2517-5openalex-snapshot
Around the log-rank conjecture
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/j.aml.2006.05.024openalex-snapshot
Communication complexity of some number theoretic functions
inferred← citeshttps://doi.org/10.1016/j.dam.2010.10.015openalex-snapshot
Panconnectivity and edge-pancyclicity of k -ary n -cubes with faulty elements
inferred← citeshttps://doi.org/10.1016/j.dam.2025.01.003openalex-snapshot
Interplay between resiliency and polynomial degree — Recursive amplification, higher order sensitivity and beyond
inferred← citeshttps://doi.org/10.1016/j.disc.2012.12.001openalex-snapshot
Variations on a theme of Graham and Pollak
inferred← citeshttps://doi.org/10.1016/j.disc.2023.113503openalex-snapshot
On bounds of A-eigenvalue multiplicity and the rank of a complex unit gain graph
inferred← citeshttps://doi.org/10.1016/j.ins.2007.08.012openalex-snapshot
Edge-pancyclicity and path-embeddability of bijective connection graphs
inferred← citeshttps://doi.org/10.1016/j.ins.2009.09.007openalex-snapshot
Path embeddings in faulty 3-ary n-cubes
inferred← citeshttps://doi.org/10.1016/j.ipl.2018.09.004openalex-snapshot
The corruption bound, log-rank, and communication complexity
inferred← citeshttps://doi.org/10.1016/j.ipl.2022.106293openalex-snapshot
On public-coin zero-error randomized communication complexity
inferred← citeshttps://doi.org/10.1016/j.jcss.2005.06.006openalex-snapshot
Polynomial degree vs. quantum query complexity
inferred← citeshttps://doi.org/10.1016/j.jpdc.2006.04.004openalex-snapshot
Optimal fault-tolerant embedding of paths in twisted cubes
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.2018.07.001openalex-snapshot
The augmentation property of binary matrices for the binary and Boolean rank
inferred← citeshttps://doi.org/10.1016/j.laa.2025.12.018openalex-snapshot
Optimal dual frame pairs: A synergy with graph theory
inferred← citeshttps://doi.org/10.1016/j.tcs.2010.01.018openalex-snapshot
Partition arguments in multiparty communication complexity
inferred← citeshttps://doi.org/10.1016/j.tcs.2014.11.012openalex-snapshot
Any monotone property of 3-uniform hypergraphs is weakly evasive
inferred← citeshttps://doi.org/10.1016/s0012-365x(03)00225-5openalex-snapshot
Extremal problems under dimension constraints
inferred← citeshttps://doi.org/10.1016/s0024-3795(99)00226-8openalex-snapshot
Matrix rank and communication complexity
inferred← citeshttps://doi.org/10.1016/s0065-2458(08)60342-3openalex-snapshot
Communication Complexity
inferred← citeshttps://doi.org/10.1016/s0304-3975(01)00144-xopenalex-snapshot
Complexity measures and decision tree complexity: a survey
inferred← citeshttps://doi.org/10.1017/9781108671644.016openalex-snapshot
Extension Complexity of Polytopes
inferred← citeshttps://doi.org/10.1017/cbo9781139814782openalex-snapshot
Analysis of Boolean Functions
inferred← citeshttps://doi.org/10.1017/fmp.2023.17openalex-snapshot
Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture
inferred← citeshttps://doi.org/10.1109/ccc.2000.856758openalex-snapshot
Characterization of non-deterministic quantum query and quantum communication complexity
inferred← citeshttps://doi.org/10.1109/ccc.2001.933879openalex-snapshot
Communication complexity lower bounds by polynomials
inferred← citeshttps://doi.org/10.1109/ccc.2010.31openalex-snapshot
The Partition Bound for Classical Communication Complexity and Query Complexity
inferred← citeshttps://doi.org/10.1109/ccc.2014.22openalex-snapshot
A Composition Theorem for Parity Kill Number
inferred← citeshttps://doi.org/10.1109/cecnet.2011.5768403openalex-snapshot
Embedding paths into the 4-ary n-cube with faulty nodes
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.2012.39openalex-snapshot
An Additive Combinatorics Approach Relating Rank to Communication Complexity
inferred← citeshttps://doi.org/10.1109/focs.2013.76openalex-snapshot
Fourier Sparsity, Spectral Norm, and the Log-Rank Conjecture
inferred← citeshttps://doi.org/10.1109/focs.2015.69openalex-snapshot
Lower Bounds for Clique vs. Independent Set
inferred← citeshttps://doi.org/10.1109/focs.2015.70openalex-snapshot
Deterministic Communication vs. Partition Number
inferred← citeshttps://doi.org/10.1109/focs.2016.32openalex-snapshot
On the Communication Complexity of Approximate Fixed Points
inferred← citeshttps://doi.org/10.1109/focs52979.2021.00020openalex-snapshot
Unambiguous DNFs and Alon-Saks-Seymour
inferred← citeshttps://doi.org/10.1109/isit.2017.8006528openalex-snapshot
Enumeration of Boolean functions of sensitivity three and inheritance of nondegeneracy
inferred← citeshttps://doi.org/10.1109/ismvl.2007.11openalex-snapshot
Boolean Functions of Low Polynomial Degree for Quantum Query Complexity Theory
inferred← citeshttps://doi.org/10.1109/ita.2013.6502978openalex-snapshot
Communication complexity and data compression
inferred← citeshttps://doi.org/10.1109/ita.2016.7888182openalex-snapshot
Communication complexity of functions related to set intersection
inferred← citeshttps://doi.org/10.1109/sfcs.1998.743480openalex-snapshot
The quantum communication complexity of sampling
inferred← citeshttps://doi.org/10.1109/sfcs.2003.1238197openalex-snapshot
Polynomial degree vs. quantum query complexity
inferred← citeshttps://doi.org/10.1109/tpds.2007.1003openalex-snapshot
Optimal Embeddings of Paths with Various Lengths in Twisted Cubes
inferred← citeshttps://doi.org/10.1137/130939043openalex-snapshot
Superlinear Advantage for Exact Quantum Algorithms
inferred← citeshttps://doi.org/10.1137/16m1059369openalex-snapshot
Deterministic Communication vs. Partition Number
inferred← citeshttps://doi.org/10.1137/22m1480616openalex-snapshot
Unambiguous DNFs and Alon–Saks–Seymour
inferred← citeshttps://doi.org/10.1137/s0097539702407345openalex-snapshot
Nondeterministic Quantum Query and Communication Complexities
inferred← citeshttps://doi.org/10.1137/s009753979935476openalex-snapshot
The Quantum Communication Complexity of Sampling
inferred← citeshttps://doi.org/10.1142/s021969132650013xopenalex-snapshot
On spectrally optimal duals for r-erasures of frames generated by graphs
inferred← citeshttps://doi.org/10.1145/1250790.1250867openalex-snapshot
Negative weights make adversaries stronger
inferred← citeshttps://doi.org/10.1145/1536414.1536479openalex-snapshot
On the complexity of communication complexity
inferred← citeshttps://doi.org/10.1145/237814.237817openalex-snapshot
The linear-array conjecture in communication complexity is false
inferred← citeshttps://doi.org/10.1145/2422436.2422454openalex-snapshot
Evasiveness through a circuit lens
inferred← citeshttps://doi.org/10.1145/2527748.2527763openalex-snapshot
Gems in decision tree complexity revisited
inferred← citeshttps://doi.org/10.1145/2629598openalex-snapshot
An Additive Combinatorics Approach Relating Rank to Communication Complexity
inferred← citeshttps://doi.org/10.1145/2897518.2897644openalex-snapshot
Separations in query complexity using cheat sheets
inferred← citeshttps://doi.org/10.1145/3170711openalex-snapshot
Randomized Communication versus Partition Number
inferred← citeshttps://doi.org/10.1145/333580.333587openalex-snapshot
Some contributions of the study of abstract communication complexity to other areas of computer science
inferred← citeshttps://doi.org/10.1145/333623.333628openalex-snapshot
Classical versus quantum communication complexity
inferred← citeshttps://doi.org/10.1145/3406325.3451002openalex-snapshot
Bipartite perfect matching as a real polynomial
inferred← citeshttps://doi.org/10.1145/3406325.3451047openalex-snapshot
Degree vs. approximate degree and Quantum implications of Huang’s sensitivity theorem
inferred← citeshttps://doi.org/10.1145/3543684openalex-snapshot
Point-hyperplane Incidence Geometry and the Log-rank Conjecture
inferred← citeshttps://doi.org/10.1145/3654780.3654788openalex-snapshot
Guest Column: Structure in Communication Complexity and Constant-Cost Complexity Classes
inferred← citeshttps://doi.org/10.1145/3798129.3800897openalex-snapshot
Monte Carlo to Las Vegas for Recursively Composed Functions
inferred← citeshttps://doi.org/10.1561/0400000011openalex-snapshot
Complexity Lower Bounds using Linear Algebra
inferred← citeshttps://doi.org/10.1561/0400000040openalex-snapshot
Lower Bounds in Communication Complexity
inferred← citeshttps://doi.org/10.25596/jalc-2002-419openalex-snapshot
3-Party Message Complexity is Better than 2-Party Ones for Proving Lower Bounds on the Size of Minimal Nondeterministic Finite Automata
inferred← citeshttps://doi.org/10.37236/513openalex-snapshot
More Counterexamples to the Alon-Saks-Seymour and Rank-Coloring Conjectures
inferred← citeshttps://doi.org/10.4204/eptcs.1.8openalex-snapshot
Communications in cellular automata
inferred← citeshttps://doi.org/10.4230/lipics.icalp.2017.51openalex-snapshot
Sensitivity Conjecture and Log-Rank Conjecture for Functions with Small Alternating Numbers
inferred← citeshttps://doi.org/10.4230/lipics.itcs.2025.71openalex-snapshot
Exact quantum query complexity for total Boolean functions
inferred← citeshttps://doi.org/10.48550/arxiv.0909.5684openalex-snapshot
Partition Arguments in Multiparty Communication Complexity
inferred← citeshttps://doi.org/10.48550/arxiv.1011.0354openalex-snapshot
Variations on the Sensitivity Conjecture
inferred← citeshttps://doi.org/10.48550/arxiv.1102.2932openalex-snapshot
Applications of Monotone Rank to Complexity Theory
inferred← citeshttps://doi.org/10.48550/arxiv.1102.3522openalex-snapshot
Traced communication complexity of cellular automata
inferred← citeshttps://doi.org/10.48550/arxiv.1111.5884openalex-snapshot
An additive combinatorics approach to the log-rank conjecture in communication complexity
inferred← citeshttps://doi.org/10.48550/arxiv.1211.0721openalex-snapshot
Superlinear advantage for exact quantum algorithms
inferred← citeshttps://doi.org/10.48550/arxiv.2005.00566openalex-snapshot
Relationships between the number of inputs and other complexity measures of Boolean functions
inferred← citeshttps://doi.org/10.48550/arxiv.cs/0001014openalex-snapshot
Nondeterministic Quantum Query and Quantum Communication Complexities
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.