We study the distributed simulation problem where @math players aim to generate sequences of random coin flips where some subsets of the players share an independent common coin which can be tossed multiple times, and there is a publicly seen blackboard through which the players communicate with each other. We provide a tight representation of the optimal communication rates via linear programming, and more importantly, propose explicit algorithms for the optimal distributed simulation for a wide class of hypergraphs. In particular, the optimal communication rate in complete hypergraphs is still achievable in sparser hypergraphs containing a path-connected cycle-free cluster of topologically connected components. Some key steps in analyzing the upper bounds rely on two different definitions of connectivity in hypergraphs, which may be of independent interest.
@cite_14: 
@cite_26: 
@cite_22: Let M e 0, 1, 2, ..., m —1 , N e 0, 1, 2,..., n —1 , and f:M × N → 0, 1 a Boolean-valued function. We will be interested in the following problem and its related questions. Let i e M , j e N be integers known only to two persons P 1 and P 2 , respectively. For P 1 and P 2 to determine cooperatively the value f ( i, j ), they send information to each other alternately, one bit at a time, according to some algorithm. The quantity of interest, which measures the information exchange necessary for computing f , is the minimum number of bits exchanged in any algorithm. For example, if f ( i, j ) e ( i + j ) mod 2. then 1 bit of information (conveying whether i is odd) sent from P 1 to P 2 will enable P 2 to determine f ( i, j ), and this is clearly the best possible. The above problem is a variation of a model of Abelson [1] concerning information transfer in distributive computions.
@cite_9: We consider parameter estimation in distributed networks, where each node in the network observes an independent sample from an underlying distribution and has (k ) bits to communicate its sample to a centralized processor which computes an estimate of a desired parameter of the distribution. We develop lower bounds for the minimax risk of estimating the underlying parameter under squared ( ) loss for a large class of distributions. Our results show that under mild regularity conditions, the communication constraint reduces the effective sample size by a factor of (d ) when (k ) is small, where (d ) is the dimension of the estimated parameter. Furthermore, this penalty reduces at most exponentially with increasing (k ), which is the case for some models, e.g., estimating high-dimensional distributions. For other models however, we show that the sample size reduction is re-mediated only linearly with increasing (k ) when some sub-Gaussian structure is available. We apply our results to the distributed setting with product Bernoulli model, multinomial model, and both dense sparse Gaussian location models which recover or strengthen existing results. Our approach significantly deviates from existing approaches for developing information-theoretic lower bounds for communication-efficient estimation. We circumvent the need for strong data processing inequalities used in prior work and develop a geometric approach which builds on a new representation of the communication constraint. This approach allows us to strengthen and generalize existing results with tight logarithmic factors, as well as simpler and more transparent proofs.
@cite_42: The purpose of this paper is to resolve several open problems in the current literature on Boolean circuits, communication complexity, and hashing functions. These lower bound results share the common feature that their proofs utilize probabilistic arguments in an essential way. Specifically, we prove that, to compute the majority function of n Boolean variables, the size of any depth-3 monotone circuit must be greater than 2ne, and the size of any width-2 branching program must have super-polynomial growth. We also show that, for the problem of deciding whether i ≤ j for two n-bit integers i and j, the probabilistic e-error one-way communication complexity is of order θ(n), while the two-way e-error complexity is O((log n)2). We will also prove that, to compute i ? j mod p for an n-bit prime p, the probabilistic e-error two-way communication complexity is of order θ(n). Finally, we prove a conjecture of Ullman that uniform hashing is asymptotically optimal in its expected retrieval cost among open address hashing schemes.
@cite_1: Independent samples from an unknown probability distribution @math on a domain of size @math are distributed across @math players, with each player holding one sample. Each player can communicate @math bits to a central referee in a simultaneous message passing (SMP) model of communication to help the referee infer a property of the unknown @math . When @math bits, the problem reduces to the well-studied collocated case where all the samples are available in one place. In this work, we focus on the communication-starved setting of @math , in which the landscape may change drastically. We propose a general formulation for inference problems in this distributed setting, and instantiate it to two prototypical inference questions: learning and uniformity testing.
@cite_32: Abstract Many combinatorial optimization problems call for the optimization of a linear function over a certain polytope. Typically, these polytopes have an exponential number of facets. We explore the problem of finding small linear programming formulations when one may use any new variables and constraints. We show that expressing the matching and the Traveling Salesman Problem by a symmetric linear program requires exponential size. We relate the minimum size needed by a LP to express a polytope to a combinatorial parameter, point out some connections with communication complexity theory, and examine the vertex packing polytope for some classes of graphs.
@cite_6: Abstract We investigate the relative power of the common random string model vs. the private random string model in communication complexity. We show that the models are essentially equal.
@cite_44: Multiple players are each given one independent sample, about which they can only provide limited information to a central referee. Each player is allowed to describe its observed sample to the referee using a channel from a family of channels @math , which can be instantiated to capture both the communication- and privacy-constrained settings and beyond. The referee uses the messages from players to solve an inference problem for the unknown distribution that generated the samples. We derive lower bounds for sample complexity of learning and testing discrete distributions in this information-constrained setting. Underlying our bounds is a characterization of the contraction in chi-square distances between the observed distributions of the samples when information constraints are placed. This contraction is captured in a local neighborhood in terms of chi-square and decoupled chi-square fluctuations of a given channel, two quantities we introduce. The former captures the average distance between distributions of channel output for two product distributions on the input, and the latter for a product distribution and a mixture of product distribution on the input. Our bounds are tight for both public- and private-coin protocols. Interestingly, the sample complexity of testing is order-wise higher when restricted to private-coin protocols.
@cite_43: We consider the following norm ∥ƒ for Boolean functions ƒ: 0, 1 n × 0, 1 n → 0, 1 : ∥ƒ|| = max ¦M(ƒ∗)v¦, v ϵ R2n, ¦v¦ = 1 . Here, M(ƒ∗) denotes the 2n × 2n-matrix obtained by setting M(ƒ∗)x,y=1 if ƒ(x,y)=1−1 if ƒ(x,y)=0. Further, we refer to the usual product of real matrices and vectors and denote by ¦v¦ the Euclidean norm of real vectors v. In this paper it will be shown by geometric arguments that for each function ƒ: 0,1 n × 0,1 n → 0,1 the following is true. - The length of each probabilistic communication protocol which computes ƒ with error bounded by 12 − 1s, s ϵ N, can be estimated from below by 14(n − log2∥ƒ||−log2 √s−2). - The number of edges of any threshold circuit of depth two computing ƒ cannot be smaller than 2n−1‖ƒ‖ These results yield better lower bounds on probabilistic communication complexity as well as on the complexity of threshold circuits of depth two. Further, characterizing ∥ƒ∥ by the eigenvalues of M(ƒ∗) we obtain a method to construct iteratively functions which are hard to compute in the above models. This implies lower bounds for decision problems that previous probabilistic techniques from Yao (1983), Halstenberg and Reischuk (1988) and (1987) cannot be applied to.
@cite_31: We study the tradeoff between the statistical error and communication cost of distributed statistical estimation problems in high dimensions. In the distributed sparse Gaussian mean estimation problem, each of the m machines receives n data points from a d-dimensional Gaussian distribution with unknown mean θ which is promised to be k-sparse. The machines communicate by message passing and aim to estimate the mean θ. We provide a tight (up to logarithmic factors) tradeoff between the estimation error and the number of bits communicated between the machines. This directly leads to a lower bound for the distributed sparse linear regression problem: to achieve the statistical minimax error, the total communication is at least Ω(min n,d m), where n is the number of observations that each machine receives and d is the ambient dimension. These lower results improve upon Shamir (NIPS'14) and Steinhardt-Duchi (COLT'15) by allowing multi-round iterative communication model. We also give the first optimal simultaneous protocol in the dense case for mean estimation. As our main technique, we prove a distributed data processing inequality, as a generalization of usual data processing inequalities, which might be of independent interest and useful for other problems.
@cite_25: It is possible to view communication complexity as the solution of an integer programming problem. The authors relax this integer programming problem to a linear programming problem, and try to deduce from it information regarding the original communication complexity question. This approach works well for nondeterministic communication complexity. In this case the authors get a special case of Lovasz's fractional cover measure and use it to completely characterize the amortized nondeterministic communication complexity. In the case of deterministic complexity the situation is more complicated. The authors discuss two attempts, and obtain some results using each of them. >
@cite_12: We establish lower bounds on minimax risks for distributed statistical estimation under a communication budget. Such lower bounds reveal the minimum amount of communication required by any procedure to achieve the centralized minimax-optimal rates for statistical estimation. We study two classes of protocols: one in which machines send messages independently, and a second allowing for interactive communication. We establish lower bounds for several problems, including various types of location models, as well as for parameter estimation in regression models.
We also review some literature on the communication complexity. First introduced in @cite_22 , the blackboard communication protocol serves as an elegant mathematical framework for the study of communication complexity. A series of research are devoted to the lower bounds in communication complexity, where the is the prominent tool for all the deterministic @cite_14 @cite_32 , nondeterministic @cite_25 and randomized communication complexities @cite_42 @cite_6 @cite_43 . We refer to @cite_26 for a survey of these methods. Another closely-related problem is distributed inference under communication constraints @cite_12 , where distributed simulation of private public randomness is useful for distributed learning and property testing @cite_1 @cite_44 . To establish lower bounds on the communication complexity in distributed inference, the copy-paste property of the blackboard communication model typically plays an important role @cite_31 @cite_9 . However, our technique to establish the lower bound is different, where only the sequential nature of the blackboard communication protocol is used in the proof of Theorem (cf. Lemma ), which may be of independent interest.