# Recently Added

## Graph and Subgraph Sparsification and its Implications to Linear System Solving and Transforming Graphs into Expanders

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 sparsification in constructing nearly-optimal ultrasparsifiers and optimizing the algebraic connectivity of a graph by adding few edges.

The talk is based on joint work with Makarychev,Saberi,Teng.

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

## In the Beginning: Modern Cosmology and the Origin of Our Universe

## The Evolution of Bodies Bound by Gravity

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

## Constructions of Expanders Using Group Theory

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 configurations of subspaces in a finite dimensional Euclidean space.

## Grothendieck Inequalities, XOR Games, and Communication Complexity

## Hardness of Projection Games

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

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.