## 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.

## Edward T. Cone Concert Talk

Tommasini discusses his role as a music critic.

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

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

## CSDM - On The Complexity of Circuit Satisfiability

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*when restricted to probabilistic

^{−o(n)}circuit families

*{C*where the size of C

_{n,m}}_{n,m}is bounded by 2

*.*

^{o(n)}poly(m)## The Completeness of the Permanent

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 will describe the ideas behind the proof of this completeness of the permanent.

## CSDM - The Detectability Lemma and Quantum Gap Amplification

## CSDM - Span Programs and Quantum Query Algorithms

The general adversary bound is a lower bound on the number of input queries required for a quantum algorithm to evaluate a boolean function. We show that this lower bound is in fact tight, up to a logarithmic factor. The proof is based on span programs. It implies that span programs are an (almost) equivalent computational model to quantum query algorithms.