Seminars Sorted by Series

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

I will discuss some recent results showing that the sum-of-squares SDP hierarchy can be used to find approximately optimal solutions to k-CSPs, provided that the instance satisfies certain expansion properties. These properties can be shown to...

A pseudodeterministic algorithm for a search problem (introduced by Goldwasser and Gat) is a randomized algorithm that must output the *same* correct answer with high probability over all choices of randomness. In this talk I will give several...

Many of the central problems in computational complexity revolve around proving lower bounds on the amount of resources used in various computational models. In this series of talks, we will discuss three standard objects in computational complexity...

Many of the central problems in computational complexity revolve around proving lower bounds on the amount of resources used in various computational models. In this talk we will continue our survey of the connections between three central models...

This (mostly expository) talk will be about invariant theory viewed through the lens of computational complexity. Invariant theory is the study of symmetries, captured by group actions, by polynomials that are “invariant.” Invariant theory has had a...

The following multi-determinantal algebraic variety plays an important role in algebra and computational complexity theory: SING_{n,m}, consisting of all m-tuples of n x n complex matrices which span only singular matrices. In particular, an...

We say a probability distribution µ is spectrally independent if an associated correlation matrix has a bounded largest eigenvalue for the distribution and all of its conditional distributions. We prove that if µ is spectrally independent, then the...

We will discuss some of the basic principles and results in the study of Boolean-valued functions over the discrete hypercube using discrete Fourier analysis. In particular, we will talk about basic concepts, the hypercontractive inequality and the...

High dimensional expansion generalizes edge and spectral expansion in graphs to hypergraphs (viewed as higher dimensional simplicial complexes). It is a tool that allows analysis of PCP agreement rests, mixing of Markov chains, and construction...

To connect to the CSDM Seminar via Zoom, please do the following:
1 - If you have Zoom installed on your device, enter the following meeting ID: 360043913 , click Join Meeting.
2 - If you do not have Zoom installed, click the following link to...

In this talk I will describe the notion of "agreement tests" that are motivated by PCPs but stand alone as a combinatorial property-testing question. I will show that high dimensional expanders support agreement tests, thereby derandomizing direct...

In this talk I will describe the notion of "agreement tests" that are motivated by PCPs but stand alone as a combinatorial property-testing question. I will show that high dimensional expanders support agreement tests, thereby derandomizing direct...

In the talk, I will explain the algorithm (and its analysis) for testing whether a number is a prime, invented by Agrawal, Kayal, and Saxena.

This talk aims to summarize a project I was involved in during the past 5 years, with the hope of explaining our most complete understanding so far, as well as challenges and open problems. The main messages of this project are summarized below; I...

We investigate the approximability of the following optimization problem, whose input is an
n-by-n matrix A and an origin symmetric convex set C that is given by a membership oracle:
"Maximize the quadratic form as x ranges over C."

This is a rich...

Proof Complexity studies the length of proofs of propositional tautologies in various restricted proof systems. One of the most well-studied is the Cutting Planes proof system, which captures reasoning which can be expressed using linear...

Distributed learning protocols are designed to train on distributed data without gathering it all on a single centralized machine, thus contributing to the efficiency of the system and enhancing its privacy. We study a central problem in distributed...

Expander graphs are among the most useful objects in computer science and mathematics. They have found applications in numerous areas of both. I will review their definition, and explain some of the many applications. Time permitting, I will also...

In this talk I will first motivate lifting theorems where lower bounds on communication complexity for composed functions are obtained by a general simulation theorem, essentially showing that no protocol can do any better than the obvious "query"...

How dense can a set of integers be while containing no three-term arithmetic progressions? This is one of the classical problems of additive combinatorics, and since the theorem of Roth in 1953 that such a set must have zero density, there has been...

We will talk about a recent result of Jeff Kahn, Bhargav Narayanan, and myself stating that the threshold for the random graph G(n,p) to contain the square of a Hamilton cycle is 1/sqrt n, resolving a conjecture of Kühn and Osthus from 2012. For...