max planck institut
mpii logo Minerva of the Max Planck Society

Great Ideas in Theoretical Computer Science (Summer 2014)

  • The last tutorial is at 4pm, July 18th.
  • Final exam is on July 24th, 10-12am.
Lecturer Kurt Mehlhorn and He Sun
TAs Pavel Kolev and Luca Zanetti
Time Wednesday 14-16, first meeting 23.04.2014
Syllabus PDF
Room 0.01 of the MMCI building (Campus E1. 7)
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 create 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.
  • Algorithms for Big Data.
  • Algebraic Techniques in Algorithm Design.
Date Topic References
April 23 Introduction slides
April 30 P versus NP, and More Lecture Notes
May 7 How to Cope with NP-Completeness Lecture Notes
May 14 Streaming Algorithms Lecture Notes
May 21 Linear Programming Lecture Notes
May 28 Expander Graphs in Computer Science Lecture Notes
June 4 Zero Knowledge Lecture Notes
June 11 Public Key Cryptography Lecture Notes
June 18 Pseudorandom Generators Lecture Notes
June 25 Dealing with Non-Perfect Randomness Lecture Notes
July 2 Learning Algorithms Lecture Notes
July 9 More Great Ideas in TCS
July 16 Review
July 24 Final Exam
Problem Sets
  • The final exam will be held in the last week of the semester.
  • Homework 50% (4 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
  • P versus NP, and More
    • S. Arora, and B. Barak: Computational Complexity: A Modern Approach, Cambridge University Press, 2009
    • 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
    • Gerhard J Woeginger's web page on P vs. NP.
  • How to Cope with NP-Completeness
    • V. Vazirani: Approximation algorithms. Springer, 2001.
  • Streaming Algorithms
    • G. Cormode: Sketch Techniques for Approximate Query Processing. PDF
    • G. Cormode, and S. Muthukrishnan: Approximating Data with the Count-Min Data Structure. IEEE Software, (2012). PDF
    • 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
    • P. Indyk: Stable Distributions, Pseudorandom Generators, Embeddings and Data Stream Computation. J. ACM, July 2006. PDF
    • S. Muthukrishnan: Data Streams: Algorithms and Applications, Foundations and Trends in TCS, 1(2):117-286, 2005. PDF
    • 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
    • Youtube Video: Streaming Algorithms. Link
  • Linear Programming
    • W. J. Cook, W. H. Cunningham, W. R. Pulleyblank, and A. Schrijver. Combinatorial Optimization. John Wiley & Sons, Inc, 1998
    • V. Vazirani: Approximation algorithms. Springer, 2001.
    • A. Schrijver. Combinatorial Optimization (3 Volumes). Springer, 2003.
  • Expander Graphs in Computer Science
    • S. Horry, N. Linial, and A. Wigderson: Expander Graphs and Their Applications. Bulletin of the American Mathematical Society, 43(4): 439-561 PDF
    • F. Chung: Spectral Graph Theory, American Mathematical Society, 1997. First four chapters can be downloaded via the link.
  • Zero Knowledge Proofs
    • O. Goldreich: A Short Tutorial of Zero-Knowledge, 2010. PDF
    • 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
    • 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
    • J. Quisquater et al. How to Explain Zero-Knowledge Protocols to Your Children. In: CRYPTO '89, pages 628-631, 1989. PDF
  • Public Key Cryptography
    • The Wikipedia page on the Public Key Cryptography. Link
    • Boaz Barak's Lecture Notes the Public Key Cryptography. Link
    • Youtube Video: Public Key Cryptography - RSA Encryption Algorithm. Link
    • Youtube Video: Rivest, Shamir, Adleman - The RSA Algorithm Explained. Link
  • Pseudorandom Generators
    • O. Goldreich: A Primer on Pseudorandom Generators PDF
    • A. Wigderson: Computational Intractability and Pseudorandomness. Institute Letter, 2009. PDF
    • Youtube Video: Randomness, by A. Wigderson. Link
  • Dealing with Non-Perfect Randomness
    • Scott Aaronson: The Quest of Randomness, Link
    • Scott Aaronson: Quantum Randomness. Link
  • Student ID*****16, Grade: 1.0
  • Student ID*****04, Grade: 1.0
  • Student ID*****11, Grade: 3.0
  • Student ID*****12, Grade: 2.0
  • Student ID*****46, Grade: 4.0
  • Student ID*****35, Grade: 1.3
  • Student ID*****41, Grade: 1.7
  • Student ID*****14, Grade: 3.0
  • Student ID*****78, Grade: 2.0
  • Student ID*****34, Grade: 1.0
Search MPII (type ? for help)