Joint Advanced Student School - JASS'2006

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.


Program:
german
russian


N
Topic
1
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
Randomness: classes RP, BPP, PP

[1] Lectures 7, 8
[3] Chapter 11

3
The hierarchy theorems: time, space, non-determinitic time, discussion

[2] Lectures  3, 4
[1] Lectures 3, 4, 5
[3] Chapter 7

4
Valiant-Vazirani Lemma

[2] Lecture 7,
[12]
[14]

5
6
Toda's theorem, part 1
Toda's theorem, part 2

[2] Lectures 8, 9
[13]

7

Interactive proofs: IP, AM, MA

[3] Chapter 12.2
[1] Lecture 11
[18], [19]

8
IP=PSPACE

[3] Chapter 19.2
[8], [10], optional  [9]

9
#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
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
PCP 1
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