The quest for understanding the origin of our universe has been
dramatically transformed since the expansion of the universe was
discovered by Edwin Hubble in 1929, thanks to impressive advances
in astronomical observations and laboratory...
I will first give an overview of several constructions of graph
sparsifiers and their properties. I will then present a method of
sparsifying a subgraph W of a graph G with optimal number of edges
and talk about the implications of subgraph...
I will survey some constructions of expander graphs using
variants of Kazhdan property T . First, I describe an approach to
property T using bounded generation and then I will describe a
recent method based on the geometric properties of...
An XOR game is a very simple model of evaluating a distributed
function f(x,y) . With probability p(x,y) a Verifier sends
questions x, y to Alice and Bob, respectively. Without
communicating, Alice and Bob then output a, b in {-1,+1} in the
hope...
Bodies bound by gravity can evolve in surprising ways. In accord
with everyday experience and physical law, heat flows from regions
of high to low temperature, and angular momentum from regions of
fast to slow spin. However, counter to intuition, in...
In this lecture, David Cole, Professor at Georgetown University
Law Center, discusses how it became legal in the United States to
engage in techniques such as water boarding by examining the role
of lawyers in the Justice Department during the...
Ancient Egyptian artworks were typically made by people of
unknown name, for extremely small audiences. The only form that had
wide visibility was large-scale architecture, but it often
presented a message of exclusion. The production of
aesthetic...
The PCP Theorem shows that any mathematical proof can be
efficiently converted into a form that can be checked
probabilistically by making only *two* queries to the proof, and
performing a "projection test" on the answers. This means that the
answer...
A PCP is a proof system in which the proofs that can be verified
by a verifier that reads only a very small part of the proof. One
line of research concerning PCPs is trying to reduce their
soundness error (i.e., the probability of accepting false...
