On the public citation graph
Lower Bounds in Communication Complexity
0 signed · 115 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.1002/rsa.20232openalex-snapshot
Lower bounds in communication complexity based on factorization norms
inferredcites →https://doi.org/10.1002/rsa.3240010401openalex-snapshot
Quasi‐random classes of hypergraphs
inferredcites →https://doi.org/10.1006/inco.1994.1051openalex-snapshot
The Bns Lower-Bound for Multiparty Protocols Is Nearly Optimal
inferredcites →https://doi.org/10.1006/jcss.1997.1545openalex-snapshot
The Space Complexity of Approximating the Frequency Moments
inferredcites →https://doi.org/10.1007/11523468_94openalex-snapshot
Hadamard Tensors and Lower Bounds on Multiparty Communication 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/978-3-642-03816-7_24openalex-snapshot
The Communication Complexity of Non-signaling Distributions
inferredcites →https://doi.org/10.1007/978-3-642-14165-2_41openalex-snapshot
Composition Theorems in Communication Complexity
inferredcites →https://doi.org/10.1007/bf01192527openalex-snapshot
On rank vs. communication complexity
inferredcites →https://doi.org/10.1007/bf01192528openalex-snapshot
On the ?log rank?-conjecture in communication complexity
inferredcites →https://doi.org/10.1007/bf01206318openalex-snapshot
Fourier analysis for probabilistic communication complexity
inferredcites →https://doi.org/10.1007/bf01263419openalex-snapshot
On the degree of boolean functions as real polynomials
inferredcites →https://doi.org/10.1007/bf01272517openalex-snapshot
On the power of small-depth threshold circuits
inferredcites →https://doi.org/10.1007/pl00001602openalex-snapshot
The BNS-Chung criterion for multi-party communication complexity
inferredcites →https://doi.org/10.1007/s00037-003-0175-xopenalex-snapshot
Towards proving strong direct product theorems
inferredcites →https://doi.org/10.1007/s00037-007-0220-2openalex-snapshot
A Strong Direct Product Theorem for Corruption and the Multiparty Communication Complexity of Disjointness
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/s00493-007-2160-5openalex-snapshot
Complexity measures of sign matrices
inferredcites →https://doi.org/10.1007/s004930050052openalex-snapshot
Quick Approximation to Matrices and Applications
inferredcites →https://doi.org/10.1016/0001-8708(79)90017-3openalex-snapshot
Constantes de Grothendieck et fonctions de type positif sur les sphères
inferredcites →https://doi.org/10.1016/0012-365x(75)90058-8openalex-snapshot
On the ratio of optimal integral and fractional covers
inferredcites →https://doi.org/10.1016/0012-365x(88)90199-9openalex-snapshot
On conjectures of Graffiti
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/0022-0000(86)90046-2openalex-snapshot
Probabilistic communication complexity
inferredcites →https://doi.org/10.1016/0022-0000(91)90024-yopenalex-snapshot
Expressing combinatorial optimization problems by Linear Programs
inferredcites →https://doi.org/10.1016/0196-6774(90)90014-6openalex-snapshot
Tensor rank is NP-complete
inferredcites →https://doi.org/10.1016/0304-3975(92)90260-mopenalex-snapshot
On the distributional complexity of disjointness
inferredcites →https://doi.org/10.1016/0304-3975(95)00005-4openalex-snapshot
Geometric arguments yield better bounds for threshold circuits and distributed computing
inferredcites →https://doi.org/10.1016/j.jcss.2003.11.006openalex-snapshot
An information statistics approach to data stream and communication complexity
inferredcites →https://doi.org/10.1016/s0012-365x(03)00227-9openalex-snapshot
Problems and results in extremal combinatorics—I
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(01)00144-xopenalex-snapshot
Complexity measures and decision tree complexity: a survey
inferredcites →https://doi.org/10.1017/cbo9780511526633.007openalex-snapshot
On Submodular Complexity Measures
inferredcites →https://doi.org/10.1017/cbo9780511569166openalex-snapshot
Summing and Nuclear Norms in Banach Space Theory
inferredcites →https://doi.org/10.1017/s0963548305007170openalex-snapshot
Measures of Pseudorandomness for Finite Sequences: Minimal Values
inferredcites →https://doi.org/10.1017/s0963548307008917openalex-snapshot
Perturbed Identity Matrices Have High Rank: Proof and Applications
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.1080/00029890.1976.11994095openalex-snapshot
A Bound for the Chromatic Number of a Graph
inferredcites →https://doi.org/10.1103/physrevlett.23.880openalex-snapshot
Proposed Experiment to Test Local Hidden-Variable Theories
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.1989.63538openalex-snapshot
A note on the power of threshold circuits
inferredcites →https://doi.org/10.1137/060654645openalex-snapshot
Lower Bounds for Lovász–Schrijver Systems and Beyond Follow from Multiparty Communication Complexity
inferredcites →https://doi.org/10.1137/070709967openalex-snapshot
On the Complexity of Nonnegative Matrix Factorization
inferredcites →https://doi.org/10.1137/08071421xopenalex-snapshot
Separating ${AC}^0$ from Depth-2 Majority Circuits
inferredcites →https://doi.org/10.1137/s0097539700375944openalex-snapshot
Communication Complexity of Simultaneous Messages
inferredcites →https://doi.org/10.1137/s0097539704441629openalex-snapshot
Approximating the Cut-Norm via Grothendieck's Inequality
inferredcites →https://doi.org/10.1137/s0895480192238482openalex-snapshot
Fractional Covers and Communication Complexity
inferredcites →https://doi.org/10.1145/185675.306789openalex-snapshot
On the hardness of approximating minimization problems
inferredcites →https://doi.org/10.1145/227683.227684openalex-snapshot
Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
inferredcites →https://doi.org/10.1145/301250.301343openalex-snapshot
Exponential separation of quantum and classical communication complexity
inferredcites →https://doi.org/10.1145/502090.502097openalex-snapshot
Quantum lower bounds by polynomials
inferredcites →https://doi.org/10.1145/780542.780640openalex-snapshot
Two applications of information complexity
inferredcites →https://doi.org/10.1515/crll.1911.140.1openalex-snapshot
Bemerkungen zur Theorie der beschränkten Bilinearformen mit unendlich vielen Veränderlichen.
inferredcites →https://doi.org/10.26421/qic9.5-6-7openalex-snapshot
Quantum communication complexity of block-composed functions
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1002/cpa.21398openalex-snapshot
Grothendieck‐Type Inequalities in Combinatorial Optimization
inferred← citeshttps://doi.org/10.1007/978-1-4939-2864-4_799openalex-snapshot
Communication Complexity
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-319-06686-8_8openalex-snapshot
Property Testing Bounds for Linear and Quadratic Functions via Parity Decision Trees
inferred← citeshttps://doi.org/10.1007/978-3-319-19225-3_24openalex-snapshot
Quantum State Complexity of Formal Languages
inferred← citeshttps://doi.org/10.1007/978-3-319-48314-6_4openalex-snapshot
Fooling Pairs in Randomized Communication Complexity
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-20877-5_39openalex-snapshot
Tight Bounds on Communication Complexity of Symmetric XOR Functions in One-Way and SMP Models
inferred← citeshttps://doi.org/10.1007/978-3-642-27848-8_799-1openalex-snapshot
Communication Complexity
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/978-3-642-31594-7_52openalex-snapshot
Classical and Quantum Partition Bound and Detector Inefficiency
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-47672-7_78openalex-snapshot
Amplification of One-Way Information Complexity via Codes and Noise Sensitivity
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/s10107-014-0837-2openalex-snapshot
Lower bounds on nonnegative rank via nonnegative nuclear norms
inferred← citeshttps://doi.org/10.1007/s10107-015-0937-7openalex-snapshot
Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank
inferred← citeshttps://doi.org/10.1007/s10898-015-0350-zopenalex-snapshot
Heuristics for exact nonnegative matrix factorization
inferred← citeshttps://doi.org/10.1007/s11537-018-1727-9openalex-snapshot
Information complexity and applications
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.2026.105416openalex-snapshot
A hierarchy of constant communication complexity
inferred← citeshttps://doi.org/10.1016/j.tcs.2010.03.027openalex-snapshot
On the parity complexity measures of Boolean functions
inferred← citeshttps://doi.org/10.1109/focs.2011.75openalex-snapshot
Quantum Query Complexity of State Conversion
inferred← citeshttps://doi.org/10.1109/focs.2012.68openalex-snapshot
Lower Bounds on Information Complexity via Zero-Communication Protocols and Applications
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.2014.27openalex-snapshot
Exponential Separation of Information and Communication
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.2019.00062openalex-snapshot
Exponential Separation between Quantum Communication and Logarithm of Approximate Rank
inferred← citeshttps://doi.org/10.1109/focs.2019.00063openalex-snapshot
Quantum Log-Approximate-Rank Conjecture is Also False
inferred← citeshttps://doi.org/10.1109/focs52979.2021.00125openalex-snapshot
A direct product theorem for quantum communication complexity with applications to device-independent QKD
inferred← citeshttps://doi.org/10.1109/focs61266.2024.00035openalex-snapshot
The Communication Complexity of Approximating Matrix Rank
inferred← citeshttps://doi.org/10.1109/isit.2017.8006848openalex-snapshot
Communication cost of transforming a nearest plane partition to the Voronoi partition
inferred← citeshttps://doi.org/10.1109/isit57864.2024.10619320openalex-snapshot
On the Asymptotic Nonnegative Rank of Matrices and its Applications in Information Theory
inferred← citeshttps://doi.org/10.1109/tit.2018.2806486openalex-snapshot
A Conditional Information Inequality and Its Combinatorial Applications
inferred← citeshttps://doi.org/10.1109/tit.2019.2959760openalex-snapshot
On the Capacity of Computation Broadcast
inferred← citeshttps://doi.org/10.1109/tit.2025.3534920openalex-snapshot
Quantum and Classical Communication Complexity of Permutation-Invariant Functions
inferred← citeshttps://doi.org/10.1134/s0032946021020046openalex-snapshot
Counting the Number of Perfect Matchings, and Generalized Decision Trees
inferred← citeshttps://doi.org/10.1137/110842661openalex-snapshot
Strong Direct Product Theorems for Quantum Communication and Query Complexity
inferred← citeshttps://doi.org/10.1137/130928273openalex-snapshot
Lower Bounds on Information Complexity via Zero-Communication Protocols and Applications
inferred← citeshttps://doi.org/10.1137/16m1096293openalex-snapshot
Exponential Separation of Communication and External Information
inferred← citeshttps://doi.org/10.1137/23m1549353openalex-snapshot
A Direct Product Theorem for Quantum Communication Complexity with Applications to Device-Independent Cryptography
inferred← citeshttps://doi.org/10.1145/2907939openalex-snapshot
Exponential Separation of Information and Communication for Boolean Functions
inferred← citeshttps://doi.org/10.1145/3055399.3055401openalex-snapshot
Exponential separation of quantum communication and classical information
inferred← citeshttps://doi.org/10.1145/3188745.3188896openalex-snapshot
On the Parameterized Complexity of Approximating Dominating Set
inferred← citeshttps://doi.org/10.1145/3470860openalex-snapshot
Improved Bounds on Fourier Entropy and Min-entropy
inferred← citeshttps://doi.org/10.1145/3618260.3649711openalex-snapshot
Hardness Condensation by Restriction
inferred← citeshttps://doi.org/10.1145/3647629openalex-snapshot
On parity decision trees for Fourier-sparse Boolean functions
inferred← citeshttps://doi.org/10.1145/3798129.3800895openalex-snapshot
Restriction Trees for Sparsity and Applications
inferred← citeshttps://doi.org/10.2139/ssrn.5393544openalex-snapshot
Consumable Data Via Quantum Communication
inferred← citeshttps://doi.org/10.22331/q-2020-06-25-286openalex-snapshot
On the Entanglement Cost of One-Shot Compression
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.24963/kr.2023/34openalex-snapshot
The Impact of Structure in Answer Set Counting: Fighting Cycles and its Limits
inferred← citeshttps://doi.org/10.26421/qic17.15-16-1openalex-snapshot
Better protocol for XOR game using communication protocol and nonlocal boxes
inferred← citeshttps://doi.org/10.4230/lipics.itcs.2022.67openalex-snapshot
Small Circuits Imply Efficient Arthur-Merlin Protocols
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.