Communication Complexity

DOI10.1017/9781108671644zbMath1436.68005OpenAlexW4211154544MaRDI QIDQ5213788

Amir Yehudayoff, Anup Rao

Publication date: 4 February 2020

Full work available at URL: https://doi.org/10.1017/9781108671644

zbMATH Keywords

computer algebrasignal processingcomputational geometrycommunication complexityalgorithmics

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Distributed systems (68M14) Distributed algorithms (68W15) Online algorithms; streaming algorithms (68W27) Theory of data (68Pxx) Networks and circuits as models of computation; circuit complexity (68Q06) Communication complexity, information complexity (68Q11)

Related Items (25)

Disjointness through the lens of Vapnik-Chervonenkis dimension: sparsity and beyond ⋮ Anticoncentration and the Exact Gap-Hamming Problem ⋮ Explicit exponential lower bounds for exact hyperplane covers ⋮ On public-coin zero-error randomized communication complexity ⋮ Shadows of Newton polytopes ⋮ Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\) ⋮ Optimal high-dimensional and nonparametric distributed testing under communication constraints ⋮ Lifting query complexity to time-space complexity for two-way finite automata ⋮ Revisiting time-space tradeoffs for function inversion ⋮ The communication complexity of functions with large outputs ⋮ Paradigms for Unconditional Pseudorandom Generators ⋮ Optimal One-Pass Nonparametric Estimation Under Memory Constraint ⋮ Low communication complexity protocols, collision resistant hash functions and secret key-agreement protocols ⋮ Bounds on oblivious multiparty quantum communication complexity ⋮ Communication and information complexity ⋮ Unnamed Item ⋮ Disjointness through the Lens of Vapnik-Chervonenkis Dimension: Sparsity and Beyond ⋮ Unnamed Item ⋮ Superfast coloring in CONGEST via efficient color sampling ⋮ Extended formulations from communication protocols in output-efficient time ⋮ Superfast coloring in CONGEST via efficient color sampling ⋮ Unnamed Item ⋮ The Communication Complexity of Set Intersection and Multiple Equality Testing ⋮ On a communication complexity problem in combinatorial number theory ⋮ Reflections on Proof Complexity and Counting Principles

This page was built for publication: Communication Complexity