Events and Activities

Explore current and upcoming events and activities happening at the Institute for Advanced Study.

Sep 29

Computer Science/Discrete Mathematics Seminar II

An introductory survey on expanders and their applications
Avi Wigderson
10:30am | Simonyi Hall 101 and Remote Access - see Zoom link below
Expander graphs are among the most useful objects in computer science and mathematics. They have found applications in numerous areas of both.  I will...
Oct 05

Computer Science/Discrete Mathematics Seminar I

Splitting Necklaces: Existence, Hardness and Approximation
Noga Alon
11:15am | Simonyi Hall 101 and Remote Access - see Zoom link below
It is known that any opened necklace with beads of n types can be partitioned by at most (k-1)n cuts into intervals that can be distributed into k collections, each containing...
Oct 06

Computer Science/Discrete Mathematics Seminar II

Simplified Lifting Theorems in Communication Complexity via Sunflowers
Toniann Pitassi
10:30am | Simonyi Hall 101 and Remote Access - see Zoom link below
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,...
Oct 12

Computer Science/Discrete Mathematics Seminar I

Explicit near-fully X-Ramanujan graphs
Xinyu Wu
11:15am | Simonyi Hall 101 and Remote Access - see Zoom link below
In this talk I will introduce constructions of finite graphs which resemble some given infinite graph both in terms of their local neighborhoods, and also their spectrum....
Oct 13

Computer Science/Discrete Mathematics Seminar II

Arithmetic progressions and spectral structure
Thomas Bloom
10:30am | Simonyi Hall 101 and Remote Access - see Zoom link below
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...
Oct 19

Computer Science/Discrete Mathematics Seminar I

A Parallel Repetition Theorem for the GHZ Game
Justin Holmgren
11:15am | Simonyi Hall 101 and Remote Access - see Zoom link below
We prove that parallel repetition of the (3-player) GHZ game reduces the value of the game polynomially fast to 0. That is, the value of the GHZ game repeated in parallel t...
Oct 20

Computer Science/Discrete Mathematics Seminar II

The threshold for the square of a Hamilton cycle
Jinyoung Park
10:30am | Remote Access - see Zoom link below
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...
Oct 26

Computer Science/Discrete Mathematics Seminar I

Fractionally Log-Concave and Sector-Stable Polynomials: Counting Planar Matchings and More
Nima Anari
11:15am | Remote Access - see Zoom link below
We introduce two new notions for polynomials associated with discrete set-valued probability distributions. These notions generalize well-studied properties like real-...
Oct 27

Computer Science/Discrete Mathematics Seminar II

On the extension complexity of random polytopes
Lisa Sauermann
10:30am | Simonyi 101 and Remote Access
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...
Nov 02

Computer Science/Discrete Mathematics Seminar I

Anti-concentration and the Gap-Hamming problem
Anup Rao
11:15am
We prove new lower bounds on the well known Gap-Hamming problem in communication complexity. Our main technical result is an anti-concentration bound for the inner product of...