Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR19-072 | 17th May 2019 22:20

Broadcast Congested Clique: Planted Cliques and Pseudorandom Generators



Consider the multiparty communication complexity model where there are n processors, each receiving as input a row of an n by n matrix M with entries in {0, 1}, and in each round each party can broadcast a single bit to all other parties (this is known as the BCAST(1) model). There are many lower bounds known for the number of rounds necessary for certain problems in this model, but they are all worst case lower bounds which apply only for very specifically constructed input distributions. We develop a framework for showing lower bounds in this setting for more natural input distributions, and apply the framework to show:
A lower bound for finding planted cliques in random inputs (i.e., each entry of the matrix is random, except there is a random subset a_1,..., a_k in [n] where M_{a_i,a_j} = 1 for all i and j). Specifically, we show that if k = n^(1/4 - eps), this problem requires a number of rounds polynomial in n.

A pseudo-random generator which fools the BCAST(1) model. That is, we show a distribution which is efficiently samplable using few random bits, and which is indistinguishable from uniform by a low-round BCAST(1) protocol. This allows us to show that every t = Omega(log n) round randomized algorithm in which each processor uses up to n random bits can be efficiently transformed into an O(t)-round randomized algorithm in which each processor uses only up to O(t) random bits, while maintaining a high success probability.

As a corollary of the pseudo-random generator, we also prove the first average case lower bound for the model (specifically, for the problem of determining whether the input matrix is full rank), as well as an average-case time hierarchy.

ISSN 1433-8092 | Imprint