## The Evolution of Bodies Bound by Gravity

Peter Goldreich
October 30, 2009 (All day)

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 bodies supported by thermal pressure, the hot regions become hotter, whereas in those supported by rotation, the regions of rapid spin spinup. Goldreich will explain this behavior and describe its ultimate consequences.

## Torture and Accountability in the "War on Terror": What Should Be Done?

David Cole
Professor, Georgetown University Law Center
October 23, 2009 (All day)

## Who Were Artists in Ancient Egypt and What Audiences Did They Address?

John Baines
Professor of Egyptology, University of Oxford; Member, School of Historical Studies, 2009-10
October 21, 2009 (All day)

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 artifacts, built spaces, and events, many requiring vast resources, was a major social preoccupation. How far can we capture and characterize the group responsible for commissioning and carrying out works?

## Hardness of Projection Games

Dana Moshkovitz
October 20, 2009 - 10:30am

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 to the first query determines at most one satisfying answer to the second query.
If the proof is correct, the checking algorithm always accepts. On the other, the probability that the checking algorithm accepts a proof for an invalid statement (this is the "error" of the check), is small.

## PCPs of Sub-Constant Error Via Derandomized Direct Product

Or Meir
The Weizmann Institute of Science
October 19, 2009 - 11:15am

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 claims) as much as possible. In particular, using low-degree curves, it is possible to construct PCP verifiers that use only two queries and have soundness error that is an inverse poly-logarithmic function in the input length.

## Edward T. Cone Concert Talk

Anthony Tommasini, Chief Music Critic
New York Times
October 17, 2009 - 6:30pm

Tommasini discusses his role as a music critic.

## CSDM - Using Local Conductance to Give Improved Algorithms for Unique Games

William Matthews
University of California at San Diego
October 13, 2009 - 10:30am

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 good local conductance, i.e. high conductance for small subgraphs. The second algorithm runs in mildly exponential time, exp(αn), but makes no assumptions about the underlying constraint graph.

## Using Local Conductance to Give Improved Algorithms for Unique Games

William Matthews
University of California at San Diego
October 13, 2009 - 10:30am

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 good local conductance, i.e. high conductance for small subgraphs. The second algorithm runs in mildly exponential time, exp(αn), but makes no assumptions about the underlying constraint graph.

## CSDM - On The Complexity of Circuit Satisfiability

Ramamohan Paturi
University of California at San Diego
October 12, 2009 - 11:15am

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 restricted to probabilistic
circuit families {Cn,m} where the size of Cn,m is bounded by 2o(n)poly(m).

Amir Yehudayoff