Seminars

Anisha Thomas is hosting the festival of Holi for the IAS community.

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

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

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

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

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.

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