max planck institut
mpii logo Minerva of the Max Planck Society

Great Ideas in Theoretical Computer Science (Summer 2013)

  • If you registered the course or would like to get the course information in time, please join the mailing list by clicking HERE .
  • [July 14] Notes of Lecture 3,5,7,9 are updated.
  • [Oct 4] Re-exam is scheduled on October 7th.
Lecturer Kurt Mehlhorn and He Sun  



Time Monday 16-18, first meeting 22.04.2013
Syllabus PDF
Poster PDF
Blog Here
Mailing List Here
Room 024 in the MPI building (E1 4)
Videocast Our course has a videocast for people studying at MPI-SWS Kaiserslautern and TU-KL Informatics. The videocast location is Room 112, MPI-SWS Kaiserslautern, Paul-Ehrlich-Str. 26 (*new building!*).
Credits You earn 6 Credit Points (LP)
Prerequisites Basic knowledge of algorithm design.
Content The course is to discuss (i) ideas in theoretical computer science that provide deep understanding, (ii) ideas that give computer scientists intuitions, (iii) ideas that have great influence in studying Algorithms & Complexity, and (iv) ideas that creat excitement.
  • Time vs. Space, P vs. NP, and More.
  • Interactive System, Zero Knowledge Proofs, the PCP Theorem.
  • Expander Graphs.
  • Learning Theory.
  • Streaming Algorithms.
  • Public-Key Cryptography.
  • Linear Programming.
  • Randomness in Computation.
  • Introduction to Approximation Algorithms.
Preliminary Schedule
Date Lecture Topic Lecture Notes Main References Other References
Apr. 22 He Introduction slides
Apr. 29 He P vs. NP, and Polynomial-Time Hierarchy Lecture Notes [AB09] [Sip92]
May 6 He Randomness in Computation Lecture Notes [Gol10] [Wig09]
May 13 Kurt Linear Programming Lecture Notes [Sch03]
May 13 Kurt Linear Programming (Contd.) Lecture Notes [Sch03]
Jun. 3 He Data Streaming Algorithms Lecture Notes [AMS99, CM05,CM12,Ind06] [Cor, Mut05]
Jun. 10 Kurt Approximation Algorithms Lecture Notes
Jun. 12 He Tutorial 1 Solutions of Problem Set 1
Jun. 17 He Expander Graphs in Computer Science Lecture Notes [HLW06]
Jun. 24 Kurt Learning Algorithms Lecture Notes [Val84]
Jul. 1 He Zero-Knowledge Proofs Lecture Notes [Gol10] [GMR89,GMW91,QQQ89]
Jul. 8 He Public-Key Cryptography Lecture Notes
Jul. 15 He Review
Jul. 22 Final Exam
Problem Sets
  • Problem Set 1 PDF
  • Problem Set 2 PDF
  • Problem Set 3 PDF
  • The final exam will be held in the last week of the semester.
  • Homework 50% (3 Problem Sets), Final Exam 50% (Written exam).
  • You need to collect at least 50% of the homework points to be eligible to take the final exam.
Similar Courses
Main References
  • [AB09] S. Arora, and B. Barak: Computational Complexity: A Modern Approach, Cambridge University Press, 2009
  • [Gol10] O. Goldreich: A Primer on Pseudorandom Generators PDF
  • [Sch03] A. Schrijver. Combinatorial Optimization (3 Volumes), Springer Verlag, 2003.
  • [CM12] G. Cormode, and S. Muthukrishnan: Approximating Data with the Count-Min Data Structure. IEEE Software, (2012). PDF
  • [CM05] G. Cormode, and S. Muthukrishnan: An Improved Data Stream Summary: The Count-Min Sketch and its Applications. J. Algorithm 55(1): 58-75 (2005) . PDF
  • [Ind06] P. Indyk: Stable Distributions, Pseudorandom Generators, Embeddings and Data Stream Computation. J. ACM, July 2006. PDF
  • [AMS99] A. Noga, M. Yossi, and S. Mario: The Space Complexity of Approximating the Frequency Moments", Journal of Computer and System Sciences, 58 (1): 137–147, 1999. PDF
  • [HLW06] S. Horry, N. Linial, and A. Wigderson: Expander Graphs and Their Applications. Bulletin of the American Mathematical Society, 43(4): 439-561 PDF
  • [Val84] L. Valiant: A theory of the learnable. Communications of the ACM, 27(11):1134-1142, 1984. PDF
  • [Gol10] O. Goldreich: A Short Tutorial of Zero-Knowledge, 2010. PDF
Other References
  • [Sip92] M. Sipser: The History and Status of the P vs NP Question. In Proceedings of the 24th Annual Symposium on Theory of Computation, 603-618, 1992. PDF
  • [Wig09] A. Wigderson: Computational Intractability and Pseudorandomness. Institute Letter, 2009. PDF
  • [Cor] G. Cormode: Sketch Techniques for Approximate Query Processing. PDF
  • [Mut05] S. Muthukrishnan: Data Streams: Algorithms and Applications, Foundations and Trends in TCS, 1(2):117-286, 2005. PDF
  • [GMR85] S. Goldwasser, S. Micali, and C. Rackoff. The knowledge complexity of interactive proof-systems (extended abstract). In 17th Annual ACM Symposium on Theory of Computing (STOC’85), pages 291–304, 1985. PDF
  • [GMW91] O. Goldreich, S. Micali, and A. Wigderson. Proofs that yield nothing but their validity, or all languages in np have zero-knowledge proof systems. Journal of the ACM, 38, 1 1991. PDF
  • [QQQ89] J. Quisquater et al. How to Explain Zero-Knowledge Protocols to Your Children. In: CRYPTO '89, pages 628-631, 1989. PDF
Search MPII (type ? for help)