Computer Science and Discrete Mathematics (CSDM)

Theoretical Computer Science and Discrete Mathematics

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

Alexandra Kolla
Institute for Advanced Study
November 10, 2009

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.

Constructions of Expanders Using Group Theory

Martin Kassabov
Cornell University; von Neumann Fellow, School of Mathematics
November 3, 2009

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.

Hardness of Projection Games

Dana Moshkovitz
Institute for Advanced Study
October 20, 2009

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

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.

CSDM - On The Complexity of Circuit Satisfiability

Ramamohan Paturi
University of California at San Diego
October 12, 2009

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

The Completeness of the Permanent

Amir Yehudayoff
Institute for Advanced Study
October 6, 2009

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.