Seminars

May
06
2019

Holi Festival

4:00pm|Housing Activities Room
Anisha Thomas is hosting the festival of Holi for the IAS community.
Apr
15
2019

Computer Science/Discrete Mathematics Seminar I

On the possibility of an instance-based complexity theory.
11:00am|Simonyi Hall 101

Worst-case analysis of algorithms has been the central method of theoretical computer science for the last 60 years, leading to great discoveries in algorithm design and a beautiful theory of computational hardness. However, worst-case analysis can...

Apr
09
2019

Computer Science/Discrete Mathematics Seminar II

Flow polytopes
10:30am|Simonyi Hall 101
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...
Apr
08
2019

Seminar on Theoretical Machine Learning

Fast minimization of structured convex quartics
Brian Bullins
12:15pm|White Levy Room
Recent progress in optimization theory has shown how we may harness second-order, i.e. Hessian, information, for achieving faster rates for both convex and non-convex optimization problems. Given this observation, it is then natural to ask what sort...
Apr
08
2019

Computer Science/Discrete Mathematics Seminar I

Collective Coin-Flipping Protocols and Influences of Coalitions
11:00am|Simonyi Hall 101
The seminal result of Kahn, Kalai and Linial implies that a coalition of a small number of players can bias the outcome of a Boolean function with respect to the uniform measure. We extend this result to arbitrary product measures, by combining...
Apr
02
2019

Computer Science/Discrete Mathematics Seminar II

A high-dimensional Littlewood--Offord inequality
Li-Yang Tan
10:30am|Simonyi Hall 101

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.

Apr
01
2019

Computer Science/Discrete Mathematics Seminar I

Fooling polytopes
Li-Yang Tan
11:00am|Simonyi Hall 101

We give a pseudorandom generator that fools $m$-facet polytopes over $\{0,1\}^n$ with seed length $\mathrm{polylog}(m) \cdot \mathrm{log}(n)$. The previous best seed length had superlinear dependence on $m$. An immediate consequence is a...