Communication Complexity

By Amit Chakrabarti. 2016

1,331 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Electrical and Electronic Engineering, Information Theory, Algorithms & Complexity

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Electrical and Electronic Engineering

In Information Theory

In Algorithms & Complexity

Citations in the corpus

Advances and Open Problems in Federated Learning (2019, background): “, [376]) and communication complexity (see [248] for a textbook reference).”
Learning Distributions from their Samples under Communication Constraints (2019, background): “Formally, a blackboard communication protocol Π BB can be viewed as a binary tree [17], where each internal node v of the tree is assigned a deterministic label l v ∈ [ n ] indicating the identity of the node to write the next bit on the blackboard if the protocol reaches tree node v ; the left and…”
Distributed Simulation and Distributed Inference (2018, neutral): “A formal description of such a protocol can be given in the form of a multiplayer protocol tree à la [KN97].”
Inference Under Information Constraints II: Communication Constraints and Shared Randomness (2019, methodology): “mmunication protocol. The proof uses a standard method for simulating sequential protocols with SMP protocols, by increasing the number of players (see, for instance, reduction of round complexity in [40]). Lemma IV.3. For every n≥1, if there exists an interactive public-coin ℓ-bit perfect simulatio”
Protocols for Learning Classifiers on Distributed Data (2012, background): “In the noiseless setting, extending from a two-party protocol to a k -party (where data is distributed to k disjoint nodes) can be achieved by allowing an additional factor k or k 2 communication, depending on the hypothesis class.”
Secure multiparty computation of approximations (2001, positive): “There are several known methods for approximating the Hamming distance using polylogarithmic communication [4, 39, 17, 37].”
Distributed verification and hardness of distributed approximation (2010, positive): “Specifically, we relate the communication lower bound from the standard communication complexity model [18] to compute some appropriately chosen function f , to the distributed time complexity lower bound for computing the same function in a specially chosen graph G.”
Memory, Communication, and Statistical Queries (2016, background): “There is a huge literature on communication complexity (see Kushilevitz and Nisan (1997); Lee and Shraibman (2009) for surveys), and the related concept of information complexity from the theoretical computer science community (Chakrabarti et al., 2001; Bar-Yossef et al., 2004; Braverman and Rao,…”
An optimal lower bound on the communication complexity of gap-hamming-distance (2010, neutral): “For a detailed coverage of the basics of the ﬁeld, as well as a number of applications, we refer the reader to the textbook of Kushilevitz and Nisan [KN97].”
Approximation Guarantees for Adaptive Sampling (2018, background): “These areas include sorting and selection (Valiant, 1975; Cole, 1988; Braverman et al., 2016), communication complexity (Papadimitriou & Sipser, 1984; Duris et al., 1984; Nisan & Widgerson, 1991), multi-armed bandits (Agarwal et al., 2017), sparse recovery (Haupt et al., 2009a; Indyk et al., 2011;…”
Differentially private multi-party computation (2014, background): “These are classical topics: state of the art of the communication complexity formulation is archived in [30]; the SFE formulation has been extensively studied with the goal of characterizing which functions can be securely evaluated [39, 2, 20, 10].”
Beyond set disjointness: the communication complexity of finding the intersection (2014, background): “While O(k log(n/k)) bits is achieved trivially and deterministically with a single message, we ask what is possible with more than one message and with randomization.”
Simple Adaptive Strategies: From Regret-matching To Uncoupled Dynamics (2013, background): “…communication complexity of the uncoupled dynamics gives the minimum number of periods needed to reach the (approximate) equilibrium (this connection was made by Conitzer and Sandholm 2004 for two-person games; for communication complexity in general, see Yao 1979 and Kushilevitz and Nisan 1997).”
Lower Bounds for Learning Distributions under Communication Constraints via Fisher Information (2019, background): “,mi−1 ∈ [2]}, where each strategy qm1,.”