# 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

### Seminar on Theoretical Machine Learning

Is optimization/ERM the right metaphor for deep learning?

12:15pm|Princeton University, CS 302

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