15:00-17:30

Speaker: Shubhangi Saraf (Rutgers University)
Title: Incidence geometry and applications to theoretical computer
 science

The classical theorem of Sylvester-Gallai states the following: given
a finite set of points in the Euclidean plane, not all on the same
line, there exists a line passing through exactly two of the points.

This result has a rich and interesting history in mathematics.
Surprisingly in recent years variants of the theorem have been
influential in various diverse areas of theoretical computer science.

In this talk I will describe several extensions to the Sylvester
Gallai theorem - quantitative versions, high dimensional versions,
colorful versions and average case versions. I will also describe
some of the applications and connections in theoretical computer
science to areas such as polynomial identity testing, local
algorithms for error correcting codes as well as lower bounds for
arithmetic computation.

Based on joint works with Albert Ai, Zeev Dvir, Neeraj Kayal and
Avi Wigderson

======================
Speaker: Swastik Kopparty (Rutgers University)
Title: CONSTANT RATE PCPS FOR CIRCUIT-SAT WITH SUBLINEAR QUERY 
COMPLEXITY

The PCP theorem says that every NP-proof can be encoded to another
proof, namely, a probabilistically checkable proof (PCP), which can
be tested by a verifier that queries only a small part of the PCP. A
natural question is how large is the blow-up incurred by this
encoding, i.e., how long is the PCP compared to the original NP
proof. The state-of-the-art works of Ben-Sasson, Sudan and Dinur show
that one can encode proofs of length n by PCPs of length
(n polylog n) that can be verified using a constant number of
queries.

I will talk about a recent result, joint with Eli Ben-Sasson, Yohay
Kaplan and Or Meir, showing that one can encode proofs of length n by
PCPs of length O(n), such that the proofs can be checked
with n{epsilon} query complexity (for every epsilon > 0). This is
the first constant-rate PCP construction that achieves constant
soundness with nontrivial query complexity (o(n)).

Our proof replaces the low-degree polynomials codes in traditional
algebraic PCP constructions with algebraic-geometric (AG) codes. We
show that the automorphisms of an AG code can be used to simulate the
role of affine transformations which are crucial in earlier high-rate
algebraic PCP constructions. Using this observation we conclude that
any asymptotically good family of transitive AG codes over a constant
sized alphabet leads to a family of constant-rate PCPs with
polynomially small query complexity. The required family of
transitive AG codes was recently constructed by Henning Stichtenoth,
and appears in the appendix to our paper.