Seminars Sorted by Series

We present an explicit pseudorandom generator with seed length $\tilde{O}((\log n)^{w+1})$ for read-once, oblivious, width $w$ branching programs that can read their input bits in any order. This improves upon the work of Impaggliazzo, Meka and...

A theme that cuts across many domains of computer science and mathematics is to find simple representations of complex mathematical objects such as graphs, functions, or distributions on data. These representations need to capture how the object...

Neural networks have been around for many decades. An important question is what has led to their recent surge in performance and popularity. I will start with an introduction to deep neural networks, covering the terminology and standard approaches...

Geometric Complexity Theory (GCT) was developed by Mulmuley and Sohoni as an approach towards the algebraic version of the P vs NP problem, VP vs VNP, and, more generally, proving lower bounds on arithmetic circuits. Exploiting symmetries, it...

Proof complexity studies the problem computer scientists and mathematicians face every day: given a statement, how can we prove it? A natural and well-studied question in proof complexity is to find upper and lower bounds on the length of the...

We study the complexity of constructing a hitting set for the class of polynomials that can be infinitesimally approximated by polynomials that are computed by polynomial sized algebraic circuits, over the real or complex numbers. Specifically, we...

We give a constant-factor approximation algorithm for the asymmetric traveling salesman problem. Our approximation guarantee is analyzed with respect to the standard LP relaxation, and thus our result confirms the conjectured constant integrality...

I will show an explicit construction of a binary error correcting code with relative distance $\frac{1-\epsilon}{2}$ and relative rate $\epsilon^{2+o(1)}$. This comes close to the Gilbert-Varshamov bound that shows such codes with rate $\epsilon^2$...

We develop efficient algorithms for estimating low-degree moments of unknown distributions in the presence of adversarial outliers. The guarantees of our algorithms improve in many cases significantly over the best previous ones, obtained in recent...

The talk will motivate recent work on saturation of ultrapowers from a general mathematical point of view, emphasizing some connections to combinatorics.

In a sequence of extremely fundamental results in the 80's, Kaltofen showed that any factor of n-variate polynomial with degree and arithmetic circuit size poly(n) has an arithmetic circuit of size poly(n). In other words, the complexity class VP is...

We will discuss a model of distributed learning in the spirit of Yao's communication complexity model. We consider a two-party setting, where each of the players gets a list of labelled examples and they communicate in order to jointly perform a...

Boolean function analysis traditionally studies Boolean functions on the Boolean cube, using Fourier analysis on the group Z_2^n. Other domains of interest include the biased Boolean cube, other abelian groups, and Gaussian space. In all cases, the...

Let F be a family of subsets over a domain X that is closed under taking intersections. Such structures are abundant in various fields of mathematics such as topology, algebra, analysis, and more. In this talk we will view these objects through the...

We propose a new second-order method for geodesically convex optimization on the natural hyperbolic metric over positive definite matrices. We apply it to solve the operator scaling problem in time polynomial in the input size and logarithmic in the...

Algorithmic graph partitioning tasks are naturally related to geometric issues. Over the past decades, several deeper connections of this type have emerged. In this talk, we will describe one example by showing that, up to lower order factors, the...

In this talk, we consider the problem of explicitly constructing a binary tree code with constant distance and constant alphabet size. We present an explicit binary tree code with constant distance and alphabet size polylog(n), where n is the depth...

We consider the following question: how many points with bounded norm can a "non-degenerate" lattice have. Here, by a "non-degenerate" lattice, we mean an n-dimensional lattice with no surprisingly dense lower-dimensional sublattices.

Dadush and...

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...

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...

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...

A graph G is called a small set expander if any small set of vertices contains only a small fraction of the edges adjacent to it. This talk is mainly concerned with the investigation of small set expansion on the Grassmann Graphs, a study that was...

The Unique-Games Conjecture is a central open problem in the field of PCP’s (Probabilistically Checkable Proofs) and hardness of approximation, implying tight inapproximability results for wide class of optimization problems.

We will discuss PCPs...

A $k \times n$ matrix $(k

I will survey new lower-bound methods in communication complexity that "lift" lower bounds from decision tree complexity. These methods have recently enabled progress on core questions in communication complexity (log-rank conjecture, classical-...

For any unsatisfiable CNF formula F that is hard to refute in the Resolution proof system, we show that a gadget-composed version of F is hard to refute in any proof system whose lines are computed by efficient communication protocols---or...

Tensor networks describe high-dimensional tensors as the contraction of a network (or graph) of low-dimensional tensors. Many interesting tensor can be succinctly represented in this fashion -- from many-body ground states in quantum physics to the...

What is the largest number of projections onto k coordinates guaranteed in every family of m binary vectors of length n? This fundamental question is intimately connected to important topics and results in combinatorics and computer science (Turan...

Given an arbitrary graph, we show that if we are allowed to modify (say) 1% of the edges then it is possible to obtain a much smaller regular partition than in Szemeredi's original proof of the regularity lemma. Moreover, we show that it is...

A linear matrix is a matrix whose entries are linear forms in some indeterminates $t_1,\dots, t_m$ with coefficients in some field $F$. The commutative rank of a linear matrix is obtained by interpreting it as a matrix with entries in the function...

One of the major goals of complexity theory is to prove lower bounds for various models of computation. The theory often proceeds in buckets of three steps. The first is to come up with a collection of techniques. The second is to be frustrated at...

Lorentzian polynomials link continuous convex analysis and discrete convex analysis via tropical geometry. The class of Lorentzian polynomials contains homogeneous stable polynomials as well as volume polynomials of convex bodies and projective...

I will give a gentle overview of my work with Petter Brändén on Lorentzian polynomials (

https://arxiv.org/abs/1902.03719

), which link continuous convex analysis and discrete convex analysis via tropical geometry. The class contains homogeneous...

I will talk about a recent result showing that some well-studied polynomial-based error-correcting codes (Folded Reed-Solomon Codes and Multiplicity Codes) are "list-decodable upto capacity with constant list-size".

At its core, this is a statement...

Will this procedure be finite or infinite? If finite, how long can it last? Bjorner, Lovasz, and Shor asked these questions in 1991 about the following procedure, which goes by the name “abelian sandpile”: Given a configuration of chips on the...

I will give a tour of some of the key concepts and ideas in proof complexity. First, I will define all standard propositional proof systems using the sequent calculus which gives rise to a clean characterization of proofs as computationally limited...

Are factors of sparse polynomials sparse? This is a really basic question and we are still quite far from understanding it in general. In this talk, I will discuss a recent result showing that this is in some sense true for multivariate polynomials...

We prove a new Littlewood--Offord-type anticoncentration inequality for m-facet polytopes, a high-dimensional generalization of the classic Littlewood--Offord theorem. Joint work with Ryan O'Donnell and Rocco Servedio.

A nonnegative flow on the edges of a directed acyclic graph $G$ on the vertex set $[n]$ with netflow vector $\bf{a}=(a_1, \ldots, a_n)\in \mathbb{Z}^n$ is an assignment of nonnegative real numbers to the edges of $G$ so that at each vertex $i$ the...

Extremal set theory typically asks for the largest collection of sets satisfying certain constraints. In the first talk of these series, I'll cover some of the classical results and methods in extremal set theory. In particular, I'll cover the...

The tasks of finding and randomly sampling solutions of constraint satisfaction problems over discrete variable sets arise naturally in a wide variety of areas, among them artificial intelligence, bioinformatics and combinatorics, and further have...

The tasks of finding and randomly sampling solutions of constraint satisfaction problems over discrete variable sets arise naturally in a wide variety of areas, among them artificial intelligence, bioinformatics and combinatorics, and further have...

Szemeredi's regularity lemma is an important tool in modern graph theory. It and its variants have numerous applications in graph theory, which in turn has applications in fields such as theoretical computer science and number theory. The first part...

Continuing last week's lecture, among the numerous applications of the regularity lemma, a classical one is the graph removal lemma. It has applications in fields such as number theory and theoretical computer science. For every fixed graph H, the H...

The importance of analyzing big data and in particular very large networks has shown that the traditional notion of a fast algorithm, one that runs in polynomial time, is often insufficient. This is where property testing comes in, whose goal is to...