Seminars

Deep learning builds upon the mysterious ability of gradient-based methods to solve related non-convex optimization problems. However, a complete theoretical understanding is missing even in the simpler setting of training a deep linear neural...

We will describe a recently discovered connection between private information retrieval and secret sharing, and a new secret-sharing scheme for general access structures that breaks a long-conjectured exponential barrier.

Based on joint work with...

These two talks will introduce the asymptotic rank and asymptotic subrank of tensors and graphs - notions that are key to understanding basic questions in several fields including algebraic complexity theory, information theory and combinatorics.

M...

Tensors occur throughout mathematics. Their rank, defined in analogy with matrix rank, is however much more poorly understood, both from a structural and algorithmic viewpoints.

This will be an introductory talk to some of the basic issues...

In modern “Big Data” applications, structured learning is the most widely employed methodology. Within this paradigm, the fundamental challenge lies in developing practical, effective algorithmic inference methods. Often (e.g., deep learning)...

In their seminal paper, Bennett, Bernstein, Brassard and Vazirani [SICOMP, 1997] showed that relative to an oracle, quantum algorithms are unable to solve NP-complete problems in sub-exponential time (i.e., that Grover's search is optimal in this...

The EKR theorem, which is the cornerstone of extremal combinatorics, characterizes maximal intersecting families of sets. Its setting fixes a ground set of size n, and then studies the size and structure of intersecting families of subsets of fixed...