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...
We present two new approximation algorithms for Unique Games.
The first generalizes the results of Arora et al. who give
polynomial time approximation algorithms for graphs with high
conductance. We give a polynomial time algorithm assuming
only...
We present two new approximation algorithms for Unique Games.
The first generalizes the results of Arora et al. who give
polynomial time approximation algorithms for graphs with high
conductance. We give a polynomial time algorithm assuming
only...
We present a gap theorem regarding the complexity of the circuit
satisfiability problem.
We prove that the success probability of deciding Circuit
Satisfiability for deterministic
circuits with n variables and size m is either
2−n or 2−o(n) when...