Video Lectures

In his seminal work, Valiant defined algebraic analogs for the classes P and NP, which are known today as VP and VNP. He also showed that the permanent is VNP-complete (that is, the permanent is in VNP and any problem in VNP is reducible to it). We...

We prove that every graph has a spectral sparsifier with a number of edges linear in its
number of vertices. As linear-sized spectral sparsifiers of complete graphs are expanders, our
sparsifiers of arbitrary graphs can be viewed as generalizations...

An affine disperser over F2n for sources of dimension d is a function f: F2n --> F2 such that for any affine subspace S in F2n of dimension at least d, we have {f(s) : s in S} = F2 . Affine dispersers have been considered in the context of...

For the past decade, the Institute’s Science Initiative Group (SIG) has worked with the World Bank and other partners to strengthen science in developing nations. In this talk, Phillip Griffiths, who helped create SIG when he was Director of the...

We construct our understanding of the world solely from neuronal activity generated in our brains. How do we do this? Many studies have investigated how the electrical activity of neurons (action potentials) is related to outside stimuli, and...

Although the concept of randomness is ubiquitous, it turns out to be difficult to generate a truly random sequence of events. The need for “pseudorandomness” in various parts of modern science, ranging from numerical simulation to cryptography, has...