Proofs and Computers
St. Petersburg, 2. - 12.4.2006
Within the scope of the fourth "Joint Advanced
Student School - JASS'2006" in St.
Petersburg (April 2 - April 12), we offer the course "Proofs and
Computers".
Directors:
Prof. Dr. Yu. V.
Matiyasevich (Steklov Institute, St. Petersburg)
Prof. Dr. E.
W. Mayr (TU München)
Assistants:
Dr. E. Hirsch, D. Chibisov
Application:
The course addresses highly motivated and interested students. Active
preparation and contribution of the participants will be required. The
course language is English. Expenses for travel, board and lodging of
german participants are covered by the school.
Application deadline for GERMAN applicants:
January 29, 2006.
Application form: PDF
.
German applicants should send their
applications to D. Chibisov.
Russian
applicants should send their applications to Prof.
Dr. Yu. V.
Matiyasevich.
Organization:
Every participant is expected to give a talk
and to prepare a paper on one of the topics below. Some help is
provided on the organizational
stuff page.
Course Description:
The course is devoted, besides the fundamentals
of complexity theory, to the extension of classical model of
computation by interactive and randomized
algorithms. This extension leads to the notion of interactive proofs.
Since many interesting and computationally intensive problems (like
proofs that a given graph cannot be colored with 3 colors, or unsatisfiability of a given first-order logic
formula) can be solved probabilistically in an efficient manner, the
complexity consideration of interactively provable problems is an
important issue.
N
|
Topic
|
1
|
Bernhard Haeupler
Complexity classes and
reductions: P,
NP, reductions, NP-completeness. Languages that are neither NP-hard nor
polynomial-time solvable. Polynomial hierarchy. PSPACE-complete
problems.
[1] Lectures 1, 2, 9
[3] Chapters 7-9, 17
|
2
|
Felix
Weninger
Randomness: classes RP, BPP, PP
[1]
Lectures 7, 8
[3]
Chapter 11
|
3
|
Anton Bankevich
The
hierarchy theorems: time, space,
non-determinitic time, discussion
[2] Lectures 3, 4
[1]
Lectures 3, 4, 5
[3]
Chapter 7
|
4
|
Ilya Posov
Valiant-Vazirani
Lemma
[2] Lecture 7,
[12], [14]
|
5
6
|
Dmitry Antipov
Toda's
theorem, part 1
Dmitry Shiryaev
Toda's
theorem, part 2
[2] Lectures 8, 9
[13]
|
7
|
Florian Zuleger
Interactive
proofs: IP, AM, MA
[3]
Chapter 12.2
[1]
Lecture 11
[18], [19]
|
8
|
Johannes Mittmann
IP=PSPACE
[3]
Chapter 19.2
[8], [10], optional [9]
|
9
|
Dmitry Itsykson
#P.
Complexity of the
permanent. An interactie proof for P^{#P} with pemanent as an oracle.
[2] Lecture 12
[3] Chapter 18
[11], [16], [20]
|
10
|
Konstantin Ushakov
Circuit
complexity: Karp-Lipton theorem and
PP not in Size[n^k]
[1] Lecture 9
[2] Lecture 6.1,
Lecture 12
[15] Lecture 14
[17]
|
11
12
|
Lukas Bulwahn
PCP
1
Bernhard
Vesenmayer
PCP 2
[1]
Lecture 12
[4], [5], [6] , [21]
|
References:
[1] O. Goldreich: Introduction to Complexity
Theory - Lecture Notes, 1999, http://www.wisdom.weizmann.ac.il/~oded/cc.html
[2] E. Hirsch: Structural Complexity I. Lecture Notes
(in Russian), http://logic.pdmi.ras.ru/%7Ehirsch/students/complexity1/
[3] C. Papadimitriou: Computational Complexity, Addison
Wesley, 1994
[4] C. Scheideler: Modern Complexity Theory - Lecture
Notes, 2001
[5] I. Dinur: The PCP Theorem by Gap Amplification,
Electronic Colloquium on Computational Complexity, 46, 2005
[6] I. Dinur, O. Reingold: Assignment Testers: Towards
a Combinatorial Proof of the PCP-Theorem, in Proc. of the 45th
Annual IEEE Symposium on Foundations of Computer Science, 2004
[7] O. Goldreich, S. Safra: A Combinatorial Existence
Lemma with Application to Proving the PCP Theorem, SIAM J. Computing,
29 (4), 2000
[8] A. Shamir: IP=PSPACE, Journal of the ACM, 39 (4),
1992
[9] A. Shen: IP = PSPACE: Simplified Proof, Journal of
the ACM, 39 (4), 1992
[10] B. J. Mares: A Detailed Proof, that IP = PSPACE,
Brown Universtiy, http://www.cs.brown.edu/courses/gs019/papers/ip.pdf
[11] L.G. Valiant: The complexity of computing the
permanent, Theoretical Computer Scince , vol. 8, pp. 189 - 201,
1979
[12] L.G. Valiant, V.V. Vazirani: NP is as easy as
detecting unique solution, Theoretical Computer Scince , v,ol. 47 (1),
pp. 85 - 93, 1986
[13] S. Toda: PP is as Hard as the Polynomial-Time Hierarchy, http://locus.siam.org/fulltext/SICOMP/volume-20/0220053.pdf
[14] Dantsin E. Ya., Hirsch E. A., Ivanov S. V., Vsemirnov M. A.:
Algorithms for SAT and upper bounds on their complexity (in Russian) ftp://ftp.pdmi.ras.ru/pub/publicat/znsl/v277/p014.ps.gz
[15] M. Blaeser: Complexity Theory. Lecture Notes, 2005, http://www-cc.cs.uni-sb.de/cct/
[16]
C.Lund , L. Fortnow , H.Karloff: Algebraic methods for
interactive proof systems, Journal of the ACM (JACM), v.39 n.4,
p.859-868, Oct. 1992
[17] N. V. Vinodchandran: A Note on the circuit complexity, in
Electronic Colloquium on Computational Complexity, Report TR04-056,
2004, http://eccc.uni-trier.de/eccc-reports/2004/TR04-056/
[18] N.K. Vereshchagin: On the power of PP. In Proc. of the 7th IEEE
Annual Conference on Strcture in Compl. Theory, Boston, MA, USA, 1992
[19] L. Babai. Trading group theory for randomness. In Proc. of th1
17th ACM Symposium on Theory of Computing, 1985
[20] A. Ben-Dor, Sh. Halevi: Zero-One Permanent is #P-Complete, A
Simpler Proof. 108-117, ftp://theory.lcs.mit.edu/pub/people/shaih/01perm.ps.gz
[21] S. Hougardy, H. J. Prömel, A. Steger: Probabilistically
Checkable Proofs and their Consequences for Approximation Algorithms, http://www.informatik.hu-berlin.de/~hougardy/paper/almss.pdf