ERATO河原林PJ 理論グループ & ELC合同講演会 (講演者 Shubhangi Saraf 先生 & Swastik Kopparty 先生)
日時
2013年6月26日(金), 15:00-17:30
場所
ELCセンター（キャンパスイノベーションセンター東京 5F 502号室）
http://www.cictokyo.jp/access.html
詳細
http://www.al.ics.saitama-u.ac.jp/elc/event/list.cgi?regid=20130626-0000-20130626–20130621-102239-147
================
Speaker
Shubhangi Saraf 先生 (Rutgers University)
Title
Incidence geometry and applications to theoretical computer science
Abstract
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
Abstract
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 poly log 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.
