Video Lectures

Finding cliques in random graphs and the closely related "planted" clique variant, where a clique of size k is planted in a random G(n,1/2) graph, have been the focus of substantial study in algorithm design. Despite much effort, the best known...

In this talk I will describe nondeterministic reductions which yield new direct product theorems (DPTs) for Boolean circuits. In our theorems one assumes that a function F is "mildly hard" against *nondeterministic* circuits of some size s(n) , and...

Galaxies are the visible building blocks of the Universe, astrophysical laboratories that have ­profoundly informed our knowledge of cosmology and nature. Black holes—once a bizarre ­mathematical ­consequence of Einstein’s relativity theory—are now...

In many distributed systems, the cost of computation is dominated by the cost of communication between the machines participating in the computation. Communication complexity is therefore a very useful tool in understanding distributed computation...

On March 21, 2013, the most detailed map of the infant universe to date was publicly released, showing relic radiation from the Big Bang, imprinted when the universe was just 380,000 years old. This was the first release of cosmological data from...

A continuous representation of a profinite group induces a continuous pseudorepresentation, where a pseudorepresentation is the data of the
characteristic polynomial coefficients. We discuss the geometry of the resulting map from the moduli formal...

Politics is not merely a series of policy battles, but an ongoing struggle for the primacy of our favored understandings about both how the world is and how it ought to be. For a social movement to be successful, it must win discrete policy battles, but, more importantly, re-write the political field in its own favor. Social movements achieve lasting success not primarily through pursuing political changes, but by changing politics itself.

I present a new, fully anisotropic, criterion for formation of trapped surfaces in vacuum obtained in collaboration with J. Luk and I. Rodnianski. We provide conditions on null data, concentrated in a neighborhood of a short null geodesic segment...

We study algorithms for combinatorial market design problems, where a collection of objects are priced and sold to potential buyers subject to equilibrium constraints. We introduce the notion of a combinatorial Walrasian equilibium (CWE) as a...