Seminars Sorted by Series

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

Sometimes, it is possible to represent a complicated polytope as a projection of a much simpler polytope. To quantify this phenomenon, the extension complexity of a polytope P is defined to be the minimum number of facets in a (possibly higher...

Miller computed the character table of $S_n$ for some fairly large n's and noticed that almost all of the entries were even. Based on this, he conjectured that the proportion of even entries in the character table of $S_n$ tends to $1$ as $n\to...

Let X and Y be normed spaces. In functional analysis, a ``theorem on factorization through L2'' refers to the following type of statement: 

Every bounded linear operator A mapping X to Y (i.e. sup_x ||A(x)||_Y/||x||_X infinity), can be written as...

Let X and Y be normed spaces. In functional analysis, a ``theorem on factorization through L2'' refers to the following type of statement: 

Every bounded linear operator A mapping X to Y (i.e. sup_x ||A(x)||_Y/||x||_X infinity), can be written as...

I will discuss techniques, structural results, and open problems from two of my recent papers, in the context of a broader area of work on the motivating question: "how do we get the most from our data?"

In the first part of the talk, I will...

Expander graphs in general, and Ramanujan graphs in particular, have played an important role in computer science and pure mathematics in the last four decades. In recent years the area of high dimensional expanders (i.e. simplical complexes with...