Communication Complexity

Follow this topic Ask about this topic

Communication complexity asks how many bits or qubits parties must exchange when each sees only part of an input. Classical methods such as fooling sets, information-theoretic reductions, and lifting theorems establish lower bounds, while protocol design studies compression, coarsening, and interactive messages. The field also informs distributed optimization and bandits, private statistical verification, multi-agent reasoning, and quantum coordination. A central challenge is that communication costs and achievable accuracy depend strongly on the protocol model, privacy constraints, and whether the goal is computation, sampling, or certified output.

Latest papers

20 papers3 papers in the last four weeks, with none the four weeks before. 0.0% of all new papers.

SpatialPC: Deep Computation with Sublinear Local Credit Propagation
Oct 26, 2026Benjamin Prada, Shion Matsumoto, Ankur Arjun MaliLocal Learning Fine-Grained Credit Assignment
Trustworthy Knowledge-Driven AI Lab Bellini College of Artificial Intelligence, Cybersecurity and Computing University of South Florida Tampa, FL 33620
Communication Complexity of Universal Features
Oct 19, 2026Lunjia Hu, Anish Jayant, Peter Li +2Representation Learning Communication Complexity
Northeastern University · Georgia Institute of Technology · Harvard University
Bidirectionality is Necessary in Cellular Machines for Exact-Arrival Multi-Agent Path Finding
Oct 19, 2026Masashi AonoMulti-Agent Path Finding Cellular Automata
Amoeba Energy Co., Ltd., Tokyo, Japan · Keio University, Fujisawa, Kanagawa, Japan
Tree Plurality Veto: Voting in Few Rounds with Efficient Communication and Low Metric Distortion
Oct 17, 2026Gabriel Chen, Yu Cheng, Alice WangSocial Choice Theory Communication Complexity
Brown University.
Quantum Coordination Advantages in AI State-Tracking Tasks: Semantic Compilation and Latent Memory
Aug 11, 2026Ming YangState Tracking Communication Complexity
Computationally Efficient Collaborative Communication Via Regularity-Based Coarsening
Aug 5, 2026Mark Bedaywi, Scott Emmons, Nika Haghtalab +1Agent Communication Protocols Multi-Agent Systems
University of California, Berkeley
Optimal Unambiguous DNFs and Alon-Saks-Seymour
Aug 3, 2026Chirag PabbarajuQuery Complexity Sample Compression
Stanford University.
Sign compression for Muon: SignMuon, MuonSign, and the Limits of Error Feedback
Jul 31, 2026Maria Smirnova, Alexey KravatskiySign-Based Optimization Communication-Efficient Distributed Training
MIRIAI Moscow, Russia
Field Codes for Distributed Coupling Samplers and Certified Empirical Transport
Jul 29, 2026Hung Mai, Hai Nguyen, Luong Doan +4Communication Complexity Optimal Transport
1B0Labs, N2TP Technology · 3Nanyang Technological University · 4Phenikaa University, Vietnam
Regularity as seen by Alice and Bob
Jul 15, 2026Omid Yaghoubi, Mikołaj Bojańczyk, Aliaume Lopez +1Communication Complexity
Dynamic Trust-Aware Sparse Communication Topology for LLM-Based Multi-Agent Consensus
Jun 1, 2026Wanshuang Gou, Zihan LiuMulti-Agent LLM Systems Multi-Agent System Optimization
Chengdu University
Information-Theoretic Lower Bounds for Bit-Constrained Stochastic Optimization via a Reduction to Compressed Gaussian Mean Estimation
May 30, 2026Munsik KimStochastic Optimization Stochastic Optimization Convergence
Batched Stochastic Linear Bandits with 1-Bit Communication Constraints
May 29, 2026Ivan Lau, Daniel McMorrow, Kevin Jamieson +1Multi-Armed Bandits Batched Bandits
National University of Singapore · University of Washington
Smoothed Score Queries and the Complexity of Sampling
May 26, 2026Jingbo LiuSample Complexity Communication Complexity
Department of Statistics, University of Illinois Urbana–Champaign
DarkForest: Less Talk, Higher Accuracy for Multi-Agent LLMs
May 24, 2026Yi Li, Songtao Wei, Dongming Jiang +3Multi-Agent LLM Systems Multi-Agent System Optimization
University of Texas at Dallas · Independent Researcher · University of California, Davis
The Communication Complexity of Instant-Runoff Voting
May 22, 2026Élie de Panafieu, François Durand, Jérôme LangSocial Choice Theory Communication Complexity
LAMSADE, CNRS · 1Nokia Bell Labs · 2CNRS, LAMSADE, Universit´e Paris-Dauphine, PSL, France
How Much Cache Does Reasoning Need? Depth-Cache Tradeoffs in KV-Compressed Transformers
Apr 20, 2026Xiao WangTransformer Inference KV Caching
Differentially Private Verification of Distribution Properties
Apr 12, 2026Elbert Du, Cynthia Dwork, Pranay Tankala +1Differential Privacy Communication Complexity
Harvard University · Rutgers University
Better Bounds for the Distributed Experts Problem
Mar 10, 2026David P. Woodruff, Samson ZhouRegret Minimization Communication Complexity
Carnegie Mellon University · Texas A&M University
Benefits and Limitations of Communication in Multi-Agent Reasoning
Oct 14, 2025Michael Rizvi-Martel, Satwik Bhattamishra, Neil Rathi +2Multi-Agent Reasoning Communication Complexity
Mila & Universit´e de Montr´eal · University of Oxford · Stanford University +1

Oct 26, 2026J/K move · Enter open · S save

SpatialPC: Deep Computation with Sublinear Local Credit Propagation

Benjamin Prada, Shion Matsumoto, Ankur Arjun Mali

Trustworthy Knowledge-Driven AI Lab Bellini College of Artificial Intelligence, Cybersecurity and Computing University of South Florida Tampa, FL 33620

Local Learning Fine-Grained Credit Assignment Communication Complexity Predictive Coding

Open paper AskPDF arXiv

On a chain of

N

states, any local learning rule with bounded communication range needs

Θ(N)

rounds before the loss can influence the earliest parameters, and this latency is usually attributed to depth. We show that it is a property of the communication geometry rather than of depth. For

N=m^d

states placed at constant density in

d

dimensions, a light-cone argument gives an

Ω(N^{1/d})

lower bound on the number of bounded-range rounds that any local algorithm needs before its gradient estimates can be sign-correct at every parameter. We construct a unit-range, degree-

2d

directed acyclic graph that contains a Hamiltonian computation of length

N-1

and in which every state lies within directed distance

d(m-1)=Θ(N^{1/d})

of the output, matching the lower bound. In the realizable-circuit model, depth and credit depth are therefore independent parameters: represented depth

Θ(N)

and causal credit latency

Θ(N^{1/d})

coexist, with a separation of order

N^{1-1/d}

. SpatialPC realizes this separation within predictive coding. Credit is propagated by adjoint prediction dynamics (APD), a local update whose

K

-round state on a settled acyclic graph is the truncated reverse-path sum

a^K=\sum_{k<K}(J^\top)^k b

, with error exactly

(J^\top)^K a^\star

. Graph geometry fixes when credit can first arrive at a state; the Jacobian-weighted path tail fixes how many further rounds accurate credit requires. A sparse two-dimensional Moore compiler retains the

N-1

backbone with

\tfrac32N-2

unit-range edges and has measured worst-node reachability

\sqrt N+2

up to

N=65{,}536

, where a 65,535-edge backbone is reached in 258 local hops. With

T=2\sqrt N

rounds, SpatialPC keeps finite-round task gradients aligned with settled gradients (cosine

0.93

on MNIST and

0.97

on Fashion-MNIST at

N=256

) and reaches

97.6\%

and

88.1\%

test accuracy after 20 epochs.