Computer Science and Discrete Mathematics (CSDM)

The classic algorithm AdaBoost allows to convert a weak learner, that is an algorithm that produces a hypothesis which is slightly better than chance, into a strong learner, achieving arbitrarily high accuracy when given enough training data. We...

The recently-discoverd Hypergraph Container Method (Saxton and Thomason, Balogh, Morris and Samotij), generalizing an earlier version for graphs (Kleitman and Winston), is used extensively in recent years in extremal and probabilistic combinatroics...

Sampling from high-dimensional, multimodal distributions is a computationally challenging and fundamental task.  This talk will focus on a family of random instances of such problems described by random quadratic potentials on the hypercube known as...

A powerful technique developed and extended in the past decade in communication complexity is the so-called "lifting theorems."  The idea is to translate the hardness results from "easier" models, e.g., query complexity, polynomial degrees, to the...

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<<n3/2. Is this a fundamental barrier for efficient algorithms?

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.