On the public citation graph
Rounds in Communication Complexity Revisited
0 signed · 153 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.1016/0022-0000(79)90044-8openalex-snapshot
Universal classes of hash functions
inferredcites →https://doi.org/10.1109/fscs.1990.89582openalex-snapshot
On the power of small-depth threshold circuits
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.1996.0050openalex-snapshot
New Lower Bounds and Hierarchy Results for Restricted Branching Programs
inferred← citeshttps://doi.org/10.1006/jcss.1998.1577openalex-snapshot
On Data Structures and Asymmetric Communication Complexity
inferred← citeshttps://doi.org/10.1006/jcss.2000.1731openalex-snapshot
The Communication Complexity of Pointer Chasing
inferred← citeshttps://doi.org/10.1007/10719839_21openalex-snapshot
Improved Upper Bounds on the Simultaneous Messages Complexity of the Generalized Addressing Function
inferred← citeshttps://doi.org/10.1007/11523468_94openalex-snapshot
Hadamard Tensors and Lower Bounds on Multiparty Communication Complexity
inferred← citeshttps://doi.org/10.1007/11821069_40openalex-snapshot
NOF-Multiparty Information Complexity Bounds for Pointer Jumping
inferred← citeshttps://doi.org/10.1007/3-540-36206-1_20openalex-snapshot
The Quantum Communication Complexity of the Pointer Chasing Problem: The Bit Version
inferred← citeshttps://doi.org/10.1007/3-540-45061-0_26openalex-snapshot
A Direct Sum Theorem in Communication Complexity via Message Compression
inferred← citeshttps://doi.org/10.1007/3-540-45322-9_1openalex-snapshot
Randomized Communication Protocols
inferred← citeshttps://doi.org/10.1007/3-540-59042-0_88openalex-snapshot
Simultaneous messages vs. communication
inferred← citeshttps://doi.org/10.1007/3-540-60922-9_40openalex-snapshot
Read-once projections and formal circuit verification with binary decision diagrams
inferred← citeshttps://doi.org/10.1007/3-540-60922-9_51openalex-snapshot
Upper bounds on multiparty communication complexity of shifts
inferred← citeshttps://doi.org/10.1007/3-540-60922-9_52openalex-snapshot
Some bounds on multiparty communication complexity of pointer jumping
inferred← citeshttps://doi.org/10.1007/978-1-4757-6048-4_49openalex-snapshot
Communication Complexity and BDD Lower Bound Techniques
inferred← citeshttps://doi.org/10.1007/978-3-030-14812-6_39openalex-snapshot
Space Lower Bounds for Graph Stream Problems
inferred← citeshttps://doi.org/10.1007/978-3-031-32733-9_21openalex-snapshot
Energy-Efficient Distributed Algorithms for Synchronous Networks
inferred← citeshttps://doi.org/10.1007/978-3-031-91092-0_11openalex-snapshot
The Complexity of Memory Checking with Covert Security
inferred← citeshttps://doi.org/10.1007/978-3-031-91736-3_17openalex-snapshot
Pointer Chasing with Unlimited Interaction
inferred← citeshttps://doi.org/10.1007/978-3-540-27836-8_63openalex-snapshot
Communication Versus Computation
inferred← citeshttps://doi.org/10.1007/978-3-540-30539-2_11openalex-snapshot
Privacy in Non-private Environments
inferred← citeshttps://doi.org/10.1007/978-3-540-70575-8_62openalex-snapshot
Tight Lower Bounds for Multi-pass Stream Computation Via Pass Elimination
inferred← citeshttps://doi.org/10.1007/978-3-540-73420-8_14openalex-snapshot
Separating Deterministic from Nondeterministic NOF Multiparty Communication Complexity
inferred← citeshttps://doi.org/10.1007/978-3-540-73420-8_61openalex-snapshot
Lower Bounds for Quantile Estimation in Random-Order and Multi-pass Streaming
inferred← citeshttps://doi.org/10.1007/978-3-540-78291-9_4openalex-snapshot
An Introductory Course on Communication Complexity
inferred← citeshttps://doi.org/10.1007/978-3-540-85363-3_30openalex-snapshot
Improved Separations between Nondeterministic and Randomized Multiparty Communication
inferred← citeshttps://doi.org/10.1007/978-3-642-20877-5_40openalex-snapshot
The Hardness of Median in the Synchronized Bit Communication Model
inferred← citeshttps://doi.org/10.1007/978-3-642-24100-0_4openalex-snapshot
Trading Bit, Message, and Time Complexity of Distributed Algorithms
inferred← citeshttps://doi.org/10.1007/978-3-642-40273-9_9openalex-snapshot
Computing (and Life) Is All about Tradeoffs
inferred← citeshttps://doi.org/10.1007/pl00001602openalex-snapshot
The BNS-Chung criterion for multi-party communication complexity
inferred← citeshttps://doi.org/10.1007/s00037-007-0220-2openalex-snapshot
A Strong Direct Product Theorem for Corruption and the Multiparty Communication Complexity of Disjointness
inferred← citeshttps://doi.org/10.1007/s00037-007-0224-yopenalex-snapshot
Communication vs. Computation
inferred← citeshttps://doi.org/10.1007/s00037-012-0052-6openalex-snapshot
Hadamard tensors and lower bounds on multiparty communication complexity
inferred← citeshttps://doi.org/10.1007/s00037-013-0078-4openalex-snapshot
The NOF Multiparty Communication Complexity of Composed Functions
inferred← citeshttps://doi.org/10.1007/s00037-018-0168-4openalex-snapshot
An adaptivity hierarchy theorem for property testing
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/s00224-002-1050-xopenalex-snapshot
The Power of Nondeterminism and Randomness for Oblivious Branching Programs
inferred← citeshttps://doi.org/10.1007/s00224-009-9243-1openalex-snapshot
Privacy in Non-private Environments
inferred← citeshttps://doi.org/10.1007/s00224-013-9476-xopenalex-snapshot
Optimal Collapsing Protocol for Multiparty Pointer Jumping
inferred← citeshttps://doi.org/10.1007/s00446-024-00475-3openalex-snapshot
($$\Delta + 1$$) vertex coloring in O(n) communication
inferred← citeshttps://doi.org/10.1007/s00453-002-1007-0openalex-snapshot
A 3-Party Simultaneous Protocol for SUM-INDEX
inferred← citeshttps://doi.org/10.1007/s00453-016-0138-7openalex-snapshot
Superlinear Lower Bounds for Multipass Graph Processing
inferred← citeshttps://doi.org/10.1007/s00493-009-2667-zopenalex-snapshot
One-way multiparty communication lower bound for pointer jumping with applications
inferred← citeshttps://doi.org/10.1007/s004930050054openalex-snapshot
The Linear-Array Conjecture in Communication Complexity Is False
inferred← citeshttps://doi.org/10.1007/s004930100009openalex-snapshot
The Cost of the Missing Bit: Communication Complexity with Help
inferred← citeshttps://doi.org/10.1007/s10957-023-02353-7openalex-snapshot
Algorithms for Cardinality-Constrained Monotone DR-Submodular Maximization with Low Adaptivity and Query Complexity
inferred← citeshttps://doi.org/10.1007/s11047-022-09904-3openalex-snapshot
Exponential separation between quantum and classical ordered binary decision diagrams, reordering method and hierarchies
inferred← citeshttps://doi.org/10.1016/0304-3975(95)00157-3openalex-snapshot
Lower bounds for one-way probabilistic communication complexity and their application to space complexity
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.2005.11.011openalex-snapshot
Nondeterministic ordered binary decision diagrams with repeated tests and various modes of acceptance
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.1016/j.tcs.2008.04.026openalex-snapshot
Reversal complexity revisited
inferred← citeshttps://doi.org/10.1016/s0065-2458(08)60342-3openalex-snapshot
Communication Complexity
inferred← citeshttps://doi.org/10.1016/s0304-3975(97)00034-0openalex-snapshot
Hierarchy theorems for kOBDDs and kIBDDs
inferred← citeshttps://doi.org/10.1017/9781108671644.016openalex-snapshot
Extension Complexity of Polytopes
inferred← citeshttps://doi.org/10.1038/s41467-017-01887-5openalex-snapshot
Round complexity in the local transformations of quantum and classical states
inferred← citeshttps://doi.org/10.1109/18.149503openalex-snapshot
Average-case interactive communication
inferred← citeshttps://doi.org/10.1109/18.259644openalex-snapshot
Three results on interactive communication
inferred← citeshttps://doi.org/10.1109/ccc.1997.612319openalex-snapshot
Randomized simultaneous messages: solution of a problem of Yao in communication complexity
inferred← citeshttps://doi.org/10.1109/ccc.1998.694600openalex-snapshot
Lower bounds for computation with limited nondeterminism
inferred← citeshttps://doi.org/10.1109/ccc.1999.766256openalex-snapshot
The communication complexity of pointer chasing. Applications of entropy and sampling
inferred← citeshttps://doi.org/10.1109/ccc.2002.1004344openalex-snapshot
Information theory methods in communication complexity
inferred← citeshttps://doi.org/10.1109/ccc.2005.1openalex-snapshot
A Direct Sum Theorem for Corruption and the Multiparty NOF Communication Complexity of Set Disjointness
inferred← citeshttps://doi.org/10.1109/ccc.2007.14openalex-snapshot
Lower Bounds for Multi-Player Pointer Jumping
inferred← citeshttps://doi.org/10.1109/ccc.2011.33openalex-snapshot
On Arthur Merlin Games in Communication Complexity
inferred← citeshttps://doi.org/10.1109/ccc.2013.37openalex-snapshot
Superlinear Lower Bounds for Multipass Graph Processing
inferred← citeshttps://doi.org/10.1109/focs.2007.34openalex-snapshot
One-Way Multi-Party Communication Lower Bound for Pointer Jumping with Applications
inferred← citeshttps://doi.org/10.1109/focs.2007.4389513openalex-snapshot
One-Way Multi-Party Communication Lower Bound for Pointer Jumping with Applications
inferred← citeshttps://doi.org/10.1109/focs.2007.51openalex-snapshot
A Brief Look at Pairings Based Cryptography
inferred← citeshttps://doi.org/10.1109/focs.2012.74openalex-snapshot
Lower Bounds on Interactive Compressibility by Constant-Depth Circuits
inferred← citeshttps://doi.org/10.1109/focs.2013.78openalex-snapshot
On the Communication Complexity of Sparse Set Disjointness and Exists-Equal Problems
inferred← citeshttps://doi.org/10.1109/focs.2013.85openalex-snapshot
Direct Products in Communication Complexity
inferred← citeshttps://doi.org/10.1109/focs.2014.33openalex-snapshot
List and Unique Coding for Interactive Communication in the Presence of Adversarial Noise
inferred← citeshttps://doi.org/10.1109/focs.2015.53openalex-snapshot
Near-Optimal Bounds on Bounded-Round Quantum Communication Complexity of Disjointness
inferred← citeshttps://doi.org/10.1109/focs.2016.40openalex-snapshot
How Limited Interaction Hinders Real Communication (and What It Means for Proof and Circuit Complexity)
inferred← citeshttps://doi.org/10.1109/focs57990.2023.00063openalex-snapshot
Top-Down Lower Bounds for Depth-Four Circuits
inferred← citeshttps://doi.org/10.1109/sfcs.1991.185373openalex-snapshot
Interactive communication: balanced distributions, correlated files, and average-case complexity
inferred← citeshttps://doi.org/10.1109/sfcs.1994.365683openalex-snapshot
Products and help bits in decision trees
inferred← citeshttps://doi.org/10.1109/sfcs.2002.1181967openalex-snapshot
Privacy and interaction in quantum communication complexity and a theorem about the relative entropy of quantum states
inferred← citeshttps://doi.org/10.1109/tit.2007.896888openalex-snapshot
Interaction in Quantum Communication
inferred← citeshttps://doi.org/10.1137/070683155openalex-snapshot
Graph Distances in the Data-Stream Model
inferred← citeshttps://doi.org/10.1137/07069328xopenalex-snapshot
Stream Order and Order Statistics: Quantile Estimation in Random-Order Streams
inferred← citeshttps://doi.org/10.1137/1.9781611975482.112openalex-snapshot
Communication-Rounds Tradeoffs for Common Randomness and Secret Key Generation
inferred← citeshttps://doi.org/10.1137/1.9781611975994.31openalex-snapshot
Exponential Separations in Local Differential Privacy
inferred← citeshttps://doi.org/10.1137/1.9781611975994.66openalex-snapshot
Round Complexity of Common Randomness Generation: The Amortized Setting
inferred← citeshttps://doi.org/10.1137/141002001openalex-snapshot
List and Unique Coding for Interactive Communication in the Presence of Adversarial Noise
inferred← citeshttps://doi.org/10.1137/16m109867xopenalex-snapshot
Noisy Interactive Quantum Communication
inferred← citeshttps://doi.org/10.1137/17m112289xopenalex-snapshot
Verifiable Stream Computation and Arthur--Merlin Communication
inferred← citeshttps://doi.org/10.1137/20m1370021openalex-snapshot
Separating the Communication Complexity of Truthful and Nontruthful Algorithms for Combinatorial Auctions
inferred← citeshttps://doi.org/10.1137/s0097539700375944openalex-snapshot
Communication Complexity of Simultaneous Messages
inferred← citeshttps://doi.org/10.1137/s0097539794264809openalex-snapshot
Boolean Circuits, Tensor Ranks, and Communication Complexity
inferred← citeshttps://doi.org/10.1142/s0129626416500043openalex-snapshot
Clique Here: On the Distributed Complexity in Fully-Connected Networks
inferred← citeshttps://doi.org/10.1145/1265530.1265537openalex-snapshot
Machine models and lower bounds for query processing
inferred← citeshttps://doi.org/10.1145/1568318.1568323openalex-snapshot
A property of quantum relative entropy with an application to privacy in quantum communication
inferred← citeshttps://doi.org/10.1145/1595391.1595392openalex-snapshot
Improved Separations between Nondeterministic and Randomized Multiparty Communication
inferred← citeshttps://doi.org/10.1145/1806689.1806772openalex-snapshot
Towards polynomial lower bounds for dynamic problems
inferred← citeshttps://doi.org/10.1145/1855118.1886592openalex-snapshot
SIGACT News Complexity Theory Column 67
inferred← citeshttps://doi.org/10.1145/1993806.1993853openalex-snapshot
A tight unconditional lower bound on distributed randomwalk computation
inferred← citeshttps://doi.org/10.1145/225058.225093openalex-snapshot
On data structures and asymmetric 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/2488608.2488628openalex-snapshot
From information to exact communication
inferred← citeshttps://doi.org/10.1145/258533.258620openalex-snapshot
Direct product results and the GCD problem, in old and new communication models
inferred← citeshttps://doi.org/10.1145/2897518.2897563openalex-snapshot
Constant-Rate Coding for Multiparty Interactive Communication Is Impossible
inferred← citeshttps://doi.org/10.1145/301250.301413openalex-snapshot
The communication complexity of pointer chasing
inferred← citeshttps://doi.org/10.1145/3293611.3331625openalex-snapshot
Hardness of Exact Distance Queries in Sparse Graphs Through Hub Labeling
inferred← citeshttps://doi.org/10.1145/3313276.3316361openalex-snapshot
Polynomial pass lower bounds for graph streaming algorithms
inferred← citeshttps://doi.org/10.1145/335305.335396openalex-snapshot
On quantum and probabilistic communication
inferred← citeshttps://doi.org/10.1145/3459095openalex-snapshot
Exponential Separations in Local Privacy
inferred← citeshttps://doi.org/10.1145/3618260.3649686openalex-snapshot
Memory Checking Requires Logarithmic Overhead
inferred← citeshttps://doi.org/10.1145/3707202openalex-snapshot
Memory Checking Requires Logarithmic Overhead
inferred← citeshttps://doi.org/10.1145/3717823.3718148openalex-snapshot
Refuting the Direct Sum Conjecture for Total Functions in Deterministic Communication Complexity
inferred← citeshttps://doi.org/10.1145/380752.380786openalex-snapshot
Interaction in quantum communication and the complexity of set disjointness
inferred← citeshttps://doi.org/10.17877/de290r-14220openalex-snapshot
Information Complexity and Data Stream Algorithms for Basic Problems
inferred← citeshttps://doi.org/10.3103/s1066369x13030067openalex-snapshot
Extension of the hierarchy for k-OBDDs of small width
inferred← citeshttps://doi.org/10.31274/etd-180810-4556openalex-snapshot
Randomness in completeness and space-bounded computations
inferred← citeshttps://doi.org/10.3233/fi-2011-407openalex-snapshot
Trade-Offs Between Time, Space, Cooperation, and Communication Complexity for CD Grammar Systems
inferred← citeshttps://doi.org/10.3934/jimo.2022031openalex-snapshot
An adaptive algorithm for maximization of non-submodular function with a matroid constraint
inferred← citeshttps://doi.org/10.4204/eptcs.1.8openalex-snapshot
Communications in cellular automata
inferred← citeshttps://doi.org/10.4230/lipics.itcs.2022.105openalex-snapshot
Interactive Communication in Bilateral Trade
inferred← citeshttps://doi.org/10.48550/arxiv.0705.2437openalex-snapshot
A theorem about relative entropy of quantum states with an application to privacy in quantum communication
inferred← citeshttps://doi.org/10.48550/arxiv.1710.01969openalex-snapshot
Simultaneous Multiparty Communication Complexity of Composed Functions
inferred← citeshttps://doi.org/10.48550/arxiv.1801.01022openalex-snapshot
Shannon Capacity is Achievable for Binary Interactive First-Order Markovian Protocols
inferred← citeshttps://doi.org/10.48550/arxiv.1907.00813openalex-snapshot
Exponential Separations in Local Differential Privacy
inferred← citeshttps://doi.org/10.48550/arxiv.2107.05810openalex-snapshot
The Element Extraction Problem and the Cost of Determinism and Limited Adaptivity in Linear Queries
inferred← citeshttps://doi.org/10.48550/arxiv.quant-ph/0004100openalex-snapshot
On rounds in quantum communication
inferred← citeshttps://doi.org/10.48550/arxiv.quant-ph/0005106openalex-snapshot
Interaction in Quantum Communication Complexity
inferred← citeshttps://doi.org/10.53846/goediss-2588openalex-snapshot
Obere und untere Schranken für eingeschränkte Parity-Branchingprogramme
inferred← citeshttps://doi.org/10.7146/brics.v1i41.21601openalex-snapshot
On Data Structures and Asymmetric Communication Complexity
inferred← citeshttps://doi.org/10.71781/9963openalex-snapshot
Complexité de la communication sur un canal avec délai
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.