We consider the problem of elimination in communication complexity, that was first raised by Ambainis et al. (2001) and later studied by Beimel et al. (2014) for its connection to the famous direct sum question. In this problem, let f from {0,1}^{2n} to {0,1} be any boolean function. Alice and Bob get k inputs x_1,...,x_k and y_1,...,y_k respectively, with x_i,y_i in {0,1}^n. They want to output a k-bit vector v, such that there exists one index i for which v_i is not equal f(x_i,y_i). We prove a general result lower bounding the randomized communication complexity of the elimination problem for f using its discrepancy. Consequently, we obtain strong lower bounds for the functions Inner-Product and Greater-Than, that work for exponentially larger values of k than the best previous bounds. To prove our result, we use a pseudo-random notion called regularity that was first used by Raz and Wigderson (1999). We show that functions with small discrepancy are regular. We also observe that a weaker notion, that we call weak-regularity, already implies hardness of elimination. Finally, we give a different proof, borrowing ideas from Viola (2015) to show that Greater-Than is weakly regular.

Quantum query complexity is known to behave multiplicatively under block composition: for any two functions f, g with quantum query complexities Q(f) and Q(g), the block composition F obtained by applying f to the results of g on disjoint sets of variables satisfies Q(F)=Theta(Q(f) * Q(g)). Meanwhile, "shared-input" compositions, where the copies of the inner functions g may share n inputs in an arbitrary fashion, are not well understood. I will describe a general setting in which the overlapping structure of the inputs to copies of g can be exploited algorithmically. Specifically, for any function f, I will give an algorithm for evaluating any shared-input composition of f and g=AND using ~O((Q(f) * n)^{1/2}) quantum queries. As long as Q(f)<<n, this improves on the bound of O(Q(f) * n^{1/2}) that follows by treating each conjunction independently, and is tight for worst-case choices of f. I will describe consequences in circuit complexity and learning theory, and highlight several tantalizing open questions. Joint work with Mark Bun and Robin Kothari.

We show that if we add a little noise to any distribution with bounded independence then we fool tests given by the product of bounded functions. This result has applications to pseudorandomness and communication complexity. In the talk we shall consider decoding noisy codewords of length m split among k parties. For Reed-Solomon codes of dimension m/k where k = O(1), communication Omega(pm) is required to decode one message symbol from a codeword with pm errors, and this is nearly tight. This result gives a formal sense in which decoding is harder than encoding. Based on work with Elad Haramaty and Chin Ho Lee.

In this talk, we consider randomized query complexity in the low-error regime, along with the direct sum problem for randomized query complexity. First, we give a total function whose \eps-error query complexity scales with log(1/\eps), even when the query algorithm is allowed to abort with constant probability. Asymptotic separations between zero-error and (1/3)-error query complexity for total functions weren't even known until very recently. We then give a strong direct sum theorem for randomized query complexity. Specifically, we show that computing k copies of any function f with error \eps requires k times the query complexity of computing one copy with low error (~ \eps/k) and constant abort probability. Taken together, these results give a total function f, such that computing k copies of f requires an Omega(k log k) blowup in query complexity, partially answering a question of Drucker [\cite{Drucker 12}] As a technical tool, we introduce the notion of a query resistant code, which is a probabilistic encoding ENC of an alphabet \Sigma such that at least half of the bits of ENC(x) must be queried before learning anything about x \in \Sigma.

This is joint work with Eric Blais.

Interactive proof systems allow a resource-bounded verifier to decide an intractable language (or compute a hard function) by communicating with a powerful but untrusted prover. Such systems guarantee that the prover can only convince the verifier of true statements. In the context of centralized computation, a celebrated result shows that interactive proofs are extremely powerful, allowing polynomial-time verifiers to decide any language in PSPACE. In this work we initiate the study of interactive distributed proofs: a network of nodes interacts with a single untrusted prover, who sees the entire network graph, to decide whether the graph satisfies some property. We focus on the communication cost of the protocol ? the number of bits the nodes must exchange with the prover and with each other. Our model can also be viewed as a generalization of the various models of ?distributed NP? (proof labeling schemes, etc.) which received significant attention recently: while these models only allow the prover to present each network node with a string of advice, our model allows for back-and-forth interaction. We prove both upper and lower bounds for the new model. We show that for some problems, interaction can exponentially decrease the communication cost compared to a non-interactive prover, but on the other hand, some problems retain non-trivial cost even with interaction.

A single-player Memory Game starts with n pairs of identical cards facing down, with a picture drawn on the face of each card. There are n distinct pictures: the two cards in each pair have the same picture. Each operation in the game reveals two cards. If these cards match, i.e., they have the same picture, then the player takes them away; otherwise the cards are turned back to face down. The object of the game is to clear all cards as quickly as possible. Past works have thoroughly studied the expected number of moves required, assuming optimal play, but these works assume that the player has perfect memory. Let T be the number of operations required to clear all cards when the player has only S bits of memory. A little thought shows that a tradeoff upper bound of ST = O(n^2 log n) is achievable. In our work, we study corresponding lower bounds. We prove that ST = Omega(n^2) in a restricted model where the player may only compare cards for equality and cannot perform any computations on the pictures. We further prove that ST^2 = Omega(n^3) without any such restrictions, assuming only that each picture can be represented as an integer in {1,2,...,R}. We do this by studying the problem in an R-way branching program model, extending an old counting argument due to Borodin and Cook, but with a new twist involving negatively associated random variables. All our lower bounds hold for both deterministic and randomized algorithms. We view these results as preliminary steps towards understanding the complexity of finding good matchings in graphs in space-limited settings. This is joint work with Yining Chen (Dartmouth).

We prove new cell-probe lower bounds for dynamic data structures that maintain a subset of {1,2,...,n}, and compute various statistics of the set. The data structure is said to handle insertions non-adaptively if the locations of memory accessed depend only on the element being inserted, and not on the contents of the memory. For any such data structure that can compute the median of the set, we prove that: t_{med} >= Omega(n^{1/(t_{ins}+1)}/(w^2 * t_{ins}^2)), where t_{ins} is the number of memory locations accessed during insertions, t_{med} is the number of memory locations accessed to compute the median, and w is the number of bits stored in each memory location. When the data structure is able to perform deletions non-adaptively and compute the minimum non-adaptively, we prove t_{min} + t_{del} >= Omega(log n /(log w + log log n)), where t_{min} is the number of locations accessed to compute the minimum, and t_{del} is the number of locations accessed to perform deletions. For the predecessor search problem, where the data structure is required to compute the predecessor of any element in the set, we prove that if computing the predecessors can be done non-adaptively, then either t_{pred} >= Omega(log n/(log log n + log w)), or t_{ins} >= Omega(n^{1/(2(t_{pred}+1))}), where t_{pred} is the number of locations accessed to compute predecessors. These bounds are nearly matched by Binary Search Trees in some range of parameters. Our results follow from using the Sunflower Lemma of Erdös and Rado [Paul Erdös and Richard Rado, 1960] together with several kinds of encoding arguments.

This is joint work with Anup Rao.

It is impossible to solve consensus without using locks in an asynchronous system where 2 processes communicate by reading from and writing to shared registers. The proof of this result, described in my boot camp lecture, builds an infinite execution, by repeatedly extending a finite execution, in which no process decides a value. In contrast, all known proofs of the impossibility of solving (n-1)-set agreement among n ? 3 processes rely on complex topological arguments, either directly or indirectly. We define a class of extension-based proofs and show that no such proof can prove the unsolvability of (n-1)-set agreement among n ? 3 processes. To do so, we view a proof as an interaction between a prover, who is trying to construct a bad execution in which n values are decided or some process takes an infinite number of steps without deciding a value, and an adversarial algorithm which is constructed adaptively. This is joint work with Dan Alistarh, James Aspnes, Rati Gelashvili, and Leqi Zhu.

I will revisit the problem of determining the space complexity of arguably the oldest problem in streaming: count the number of ones in a data stream approximately. This work is joint with Miklos Ajtai.

Subgraph counting is a fundamental primitive in graph processing, with applications in social network analysis (e.g., estimating the clustering coefficient of a graph), database processing and other areas. The space complexity of subgraph counting has been studied extensively in the literature, but many natural settings are still not well understood. In this paper we revisit the subgraph (and hypergraph) counting problem in the sketching model, where the algorithm's state as it processes a stream of updates to the graph is a linear function of the stream. This model has recently received a lot of attention in the literature, and has become a standard model for solving dynamic graph streaming problems. In this paper we give a tight bound on the sketching complexity of counting the number of occurrences of a small subgraph H in a bounded degree graph G presented as a stream of edge updates. Specifically, we show that the space complexity of the problem is governed by the fractional vertex cover number of the graph H. Our subgraph counting algorithm implements a natural vertex sampling approach, with sampling probabilities governed by the vertex cover of H. Our main technical contribution lies in a new set of Fourier analytic tools that we develop to analyze multiplayer communication protocols in the simultaneous communication model, allowing us to prove a tight lower bound. We believe that our techniques are likely to find applications in other settings. Besides giving tight bounds for all graphs H, both our algorithm and lower bounds extend to the hypergraph setting, albeit with some loss in space complexity.