We prove a parallel repetition theorem for general games with value tending to 0. We also give alternate proofs for the parallel repetition theorems of Dinur & Steurer, Holenstein and Rao. Parallel repetition theorems fall in the category of hardness amplification results and have a lot of applications in theoretical computer science, including hardness of approximation. Our proofs heavily rely on information theory but only use basic properties of mutual information such as chain rule. I will give a high level overview of our proof focussing on the role of information theory. This is joint work with Mark Braverman.

We consider the problem of estimating the value of max cut in a graph in the streaming model of computation.

At one extreme, there is a trivial $2$-approximation for this problem that uses only $O(\log n)$ space, namely, count the number of edges and output half of this value as the estimate for max cut value. On the other extreme, if one allows $\tilde{O}(n)$ space, then a near-optimal solution to the max cut value can be obtained by storing an $\tilde{O}(n)$-size sparsifier that essentially preserves the max cut. An intriguing question is if poly-logarithmic space suffices to obtain a non-trivial approximation to the max-cut value (that is, beating the factor $2$). It was recently shown that the problem of estimating the size of a maximum matching in a graph admits a non-trivial approximation in poly-logarithmic space.

Our main result is that any streaming algorithm that breaks the $2$-approximation barrier requires $\tilde{\Omega}(\sqrt{n})$ space even if the edges of the input graph are presented in random order. Our result is obtained by exhibiting a distribution over graphs which are either bipartite or $\frac{1}{2}$-far from being bipartite, and establishing that $\tilde{\Omega}(\sqrt{n})$ space is necessary to differentiate between these two cases. Thus as a direct corollary we obtain that $\tilde{\Omega}(\sqrt{n})$ space is also necessary to test if a graph is bipartite or $\frac{1}{2}$-far from being bipartite.

We also show that for any $\epsilon > 0$, any streaming algorithm that obtains a $(1 + \epsilon)$-approximation to the max cut value when edges arrive in adversarial order requires $n^{1 - O(\epsilon)}$ space, implying that $\Omega(n)$ space is necessary to obtain an arbitrarily good approximation to the max cut value.

We continue the study of welfare maximization in unit-demand (matching) markets, in a distributed information model where agent?s valuations are unknown to the central planner, and therefore communication is required to determine an efficient allocation. Dobzinski, Nisan and Oren (STOC?14) showed that if the market size is n, then r rounds of interaction (with logarithmic bandwidth) suffice to obtain an n^{1/(r+1)}-approximation to the optimal social welfare. In particular, this implies that such markets converge to a stable state (constant approximation) in time logarithmic in the market size.

We obtain the first multi-round lower bound for this setup. We show that even if the allowable per- round bandwidth of each agent is n?(r), the approximation ratio of any r-round (randomized) protocol is no better than ?(n^{1/5^{r+1}}, implying an ?(log log n) lower bound on the rate of convergence of the market to equilibrium.

Our construction and techniques may be of interest to round-communication tradeoffs in the more general setting of combinatorial auctions, for which the only known lower bound is for simultaneous (r = 1) protocols [DNO14].

We study internal compression of communication protocols to their internal entropy, which is the entropy of the transcript from the players' perspective. We provide two internal compression schemes with error. One of a protocol of Fiege et al.\ for finding the first difference between two strings. The second and main one is an internal compression with error $\eps > 0$ of a protocol with internal entropy $H^{int}$ and communication complexity $C$ to a protocol with communication at most order $(H^{int}/\eps)^2 \log(\log(C))$.

This immediately implies a similar compression to the internal information of public coin protocols, which exponentially improves over previously known public coin compressions in the dependence on $C$. It further shows that in a recent protocol of Ganor, Kol and Raz, it is impossible to move the private randomness to be public without an exponential cost. No such example was previously known.

Joint work with Balthazar Bauer (ENS Lyon) and Amir Yehudayoff (Technion).

Distributed computing is a natural application domain for communication complexity: the typical distributed system has multiple participants, each with only a partial view of the global state of the system, and the players must communicate to achieve some shared goal. Communication is often the most important resource, because its cost is usually orders-of-magnitude greater than the cost of local computation.

In this talk we describe how two-party information complexity can be extended to the multi-party setting, and how it has recently been used to obtain strong lower bounds. We point out that several nice properties of the two-party model unfortunately do not carry over to multi-party communication, so new notions are necessary.

Sparse (or small) set disjointness is the communication game where Alice and Bob are given each a set of size k in a larger universe and they are to find out if the two sets are disjoint. The randomized communication complexity of this problem is was found by Hastad and Wigderson ('97, '07): it is O(k). In this joint result with Mert Saglam we improve their O(log k) round protocol to a log* k round protocol of the same complexity and find an optimal tradeoff between the length and the number of rounds: to solve the sparse set disjointness problem in an r *>

A major advantage of our protocols is that we find the intersection of the two sets exactly and do not only decide whether it is empty. For the lower bound we use a new isoperimetric inequality.

In 1979 Yao published a paper that started the field of communication complexity and asked, in particular, what was the randomized complexity of the Equality function in the Simultaneous Message Passing (SMP) model. The tight lower bound was given only in 1996 by Newman and Szegedy.

In this work we develop a new lower bound method for analyzing the complexity of Equality in SMP.

Our technique allows us to obtain the the following new results:

• It allows to show a tight lower bound for the quantum-classical case.
• It leads to tight lower bounds for both Equality and its complement in all non-deterministic versions of quantum-classical SMP, where Merlin may also be quantum. Previous methods do not seem to work in this case.

Our characterization leads to tight trade-offs between the message lengths needed for players Alice, Bob, Merlin, not just the maximum message length among them, and highlights that the complement of Equality is easier than Equality in the case of classical proofs, but not for quantum proofs.

Along the way, we give tight analysis of a new quantum communication primitive, where a honest classical and an untrusted quantum party help a third party to obtain an approximate copy of a quantum state.

In the context of multiplayer games, the parallel repetition problem can be phrased as follows: given a game G with optimal winning probability 1−α and its repeated version Gn (in which n games are played together, in parallel), can the players use strategies that are substantially better than ones in which each game is played independently? This question is relevant in physics for the study of correlations and plays an important role in computer science in the context of complexity and cryptography. In this work the case of multiplayer non-signalling games is considered, i.e., the only restriction on the players is that they are not allowed to communicate during the game. For complete-support games (games where all possible combinations of questions have non-zero probability to be asked) with any number of players we prove a threshold theorem stating that the probability that non-signalling players win more than a fraction 1−α+β of the n games is exponentially small in nβ2, for every 0≤β≤α. For games with incomplete support we derive a similar statement, for a slightly modified form of repetition. The result is proved using a new technique, based on a recent de Finetti theorem, which allows us to avoid central technical difficulties that arise in standard proofs of parallel repetition theorems.

We give improved parallel repetition theorems for multiplayer, one-round games with entangled players, when the inputs to the players are uncorrelated. We do so by exploiting a novel connection between communication protocols and quantum parallel repetition, first explored by Chailloux and Scarpa: by taking advantage of fast quantum protocols for distributed search, we show that for this class of games (called free games), the entangled value of the n-fold repetition decays as (1 - eps^{3/2})^{\Omega(n/s)}, where 1 - eps is the entangled value of the original game, and s is the output alphabet size.

In contrast, the best known parallel repetition theorem for free games (due to Barak, et al.) in the classical setting is that the n-fold repetition value is bounded by (1 -eps^2)^{\Omega(n/s)}, suggesting the possibility of a separation between the behavior of quantum and classical games under parallel repetition.

Our proof takes advantage of the Aaronson-Ambainis quantum search protocol, and a general theorem of Nayak and Salzman that bounds the ability of parties to convey classical messages using two-way quantum communication. No prior knowledge of quantum information will be assumed.

Joint work with Kai-Min Chung and Xiaodi Wu.

Additive number theory contains a number of so-called "sumset inequalities" that relate the cardinalities of various finite subsets of an abelian group G, for instance, the sumset A+A and the difference set A-A of a finite subset A of G. We explore probabilistic analogues of such results, showing for instance that for independent, identically distributed random variables X and X’ that are discrete and take values in an abelian group G, the entropies of X+X' and X-X' strongly constrain each other. We also discuss statements analogous to the entropy power inequality (which is well known for R^n) that can be made for specific discrete groups of interest such as the integers and finite cyclic groups. Some of our results have extensions to general locally compact abelian groups, and applications to probability theory, combinatorics, information theory, and convex geometry. Based on (multiple) joint works with Ioannis Kontoyiannis (Athens), Jiange Li (Delaware), Liyao Wang (Yale), and Jaeoh Woo (Yale).

We study the complexity of parallelizing streaming algorithms (or equivalently, branching programs). If M(f) denotes the minimum average memory required to compute a function f(x1,x2,...,xn) how much memory is required to compute f on k independent streams that arrive in parallel? We show that when the inputs (updates) are sampled independently from some domain and M(f)=(n), then computing the value of f on k streams requires average memory at least knM(f).

Our results are obtained by defining new ways to measure the information complexity of streaming algorithms. We define two such measures: the \emph{transitional} and \emph{cumulative} information content. We prove that any streaming algorithm with transitional information content I can be simulated using average memory (n(I+1)). On the other hand, if every algorithm with cumulative information content I can be simulated with average memory (I+1), then computing f on k streams requires average memory at least (k(M(f)−1)).

Joint work with Anup Rao.

The sensitivity conjecture is a major outstanding foundational problems about boolean functions is the sensitivity conjecture. In one of its many forms, it asserts that the degree of a boolean function (i.e. the minimum degree of a real polynomial that interpolates the function) is bounded above by some fixed power of its sensitivity (which is the maximum vertex degree of the graph defined on the inputs where two inputs are adjacent if they differ in exactly one coordinate and their function values are different). We propose an attack on the sensitivity conjecture in terms of a novel two-player communication game. A strong enough lower bound on the cost of this game would imply the sensitivity conjecture.

To investigate the problem of bounding the cost of the game, three natural (stronger) variants of the question are considered. For two of these variants, protocols are presented that show that the hoped for lower bound does not hold. These protocols satisfy a certain monotonicity property, and (in contrast to the situation for the two variants) we show that the cost of any monotone protocol satisfies a strong lower bound.

This is joint work with Justin Gilmer and Michal Koucký.

I'll discuss various tools for proving lower bounds in the message passing communication model, where there are k players each with an input who speak to each other in a point-to-point communication network, with the goal being to solve a function of their inputs while minimizing total communication. I'll mostly focus on several recent works in which the servers try to estimate the number of distinct elements on the union of their datasets, though I'll also discuss results for graph problems, linear-algebraic problems, and other statistical problems.

This is based on joint works with Yi Li, Xiaoming Sun, Chengu Wang, and Qin Zhang.

We consider the point-to-point message passing model of communication in which there are k processors with individual private inputs, each n-bit long. Each processor is located at the node of an underlying undirected graph and has access to private random coins. An edge of the graph is a private channel of communication between its endpoints. The processors have to compute a given function of all their inputs by communicating along these channels. While this model has been widely used in distributed computing, strong lower bounds on the amount of communication needed to compute simple functions have just begun to appear. In this talk, we will see a tight lower bound of Ω(kn) on the communication needed for computing the Tribes function, when the underlying graph is a star of k + 1 nodes that has k leaves with inputs and a center with no input. Lower bound on this topology easily implies comparable bounds for others. These lower bounds are obtained by building upon the recent information theoretic techniques of Braverman et.al ([BEO+13], FOCS’13) and combining it with the earlier work of Jayram, Kumar and Sivakumar ([JKS03], STOC’03). This approach yields information complexity bounds that is of independent interest.

Joint work with Sagnik Mukhopadhyay.

We study the relationship between communication and information in 2-party communication protocols when the information is asymmetric. If I_A denotes the number of bits of information revealed by the first party, I_B denotes the information revealed by the second party, and C is the number of bits of communication in the protocol, we show that 

-- one can simulate the protocol using order  I_A + C^{3/4} I_B^{1/4} log C  bits of communication,
-- one can simulate the protocol using order I_A  2^{O(I_B)} bits of communication

The first result gives the best known bound on the complexity of a simulation when I_A >> I_B ,C^{3/4}. The second gives the best known bound when I_B << log C. In addition we show that if a function is computed by a protocol with asymmetric information complexity, then the inputs must have a large, nearly monochromatic rectangle of the right dimensions, a fact that is useful for proving lower bounds on lopsided communication problems.

This is joint work with Anup Rao.