Computer Science and Discrete Mathematics (CSDM)

In this talk, we show a strong XOR lemma for bounded-round two-player randomized communication.  For a function f:X×Y→{0,1}, the n-fold XOR function f^⊕n:X^n×Y^n→{0,1} maps n input pairs (x_1,...,x_n), (y_1,...,y_n) to the XOR of the n output bits f...

In this talk I will first review some basics about communication complexity.  Secondly I will survey some (old and new) equivalences between central problems in communication complexity and related questions in additive combinatorics.  In particular...

In this talk, I'll discuss a recent result where we settle the complexities of the maximum-cardinality bipartite matching problem (BMM) up to poly-logarithmic factors in five models of computation:  The two-party communication, AND query, OR query...

The theory of graph quasirandomness studies sequences of graphs that "look like" samples of the Erdős--Rényi random graph. The upshot of the theory is that several ways of comparing a sequence with the random graph turn out to be equivalent. For...

Many algorithms and heuristics that work well in practice have poor performance under the worst-case analysis, due to delicate pathological instances that one may never encounter. To bridge this theory-practice gap, Spielman and Teng introduced the...

Suppose we are given a random rank-r order-3 tensor---that is, an n-by-n-by-n array of numbers that is the sum of r random rank-1 terms---and our goal is to recover the individual rank-1 terms. In principle this decomposition task is possible when r<

In recent years, the average-case complexity of various high-dimensional statistical tasks has been resolved in restricted-but-powerful models of computation such as statistical queries, sum-of-squares, or low-degree polynomials. However, the hardness of tensor decomposition has remained elusive, and I will explain what makes this problem difficult. We show the first formal hardness for average-case tensor decomposition: when r>>n3/2, the decomposition task is hard for algorithms that can be expressed as low-degree polynomials in the tensor entries.

We give the first almost-linear time algorithm for computing exact maximum flows and minimum-cost flows on directed graphs. By well known reductions, this implies almost-linear time algorithms for several problems including bipartite matching...

In interactive coding, Alice and Bob wish to compute some function f of their private inputs x and y. They do this by engaging in a non-adaptive (fixed speaking order, fixed length) protocol to jointly compute f(x,y). The goal is to do this in an...

The lifeblood of interactive proof systems is randomness, without which interaction becomes redundant. Thus, a natural long-standing question is which types of proof systems can indeed be derandomized and collapsed to a single-message NP-type...

Algorithms for understanding data generated from distributions over large discrete domains are of fundamental importance.  In this talk, we consider the sample complexity of *property testing algorithms* that seek to to distinguish whether or not an...