Lecturer 
Kurt Mehlhorn
and He Sun

TAs 
Pavel Kolev
and Luca Zanetti

Time 
Wednesday 1416, 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.

Topics 
 Time vs. Space, P vs. NP, and More.
 Interactive System, Zero Knowledge Proofs, the PCP Theorem.
 Expander Graphs.
 Learning Theory.
 Streaming Algorithms.
 PublicKey Cryptography.
 Linear Programming.
 Randomness in Computation.
 Introduction to Approximation Algorithms.
 Algorithms for Big Data.
 Algebraic Techniques in Algorithm Design.

Schedule 

Problem Sets 

Grading 
 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 

Reference 
 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, 603618, 1992. PDF
 Gerhard J Woeginger's web page on P vs. NP.
 How to Cope with NPCompleteness
 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 CountMin Data Structure. IEEE Software, (2012). PDF
 G. Cormode, and S. Muthukrishnan: An Improved Data Stream Summary: The CountMin Sketch and its Applications. J. Algorithm 55(1): 5875 (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):117286, 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): 439561
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 ZeroKnowledge, 2010. PDF
 S. Goldwasser, S. Micali, and C. Rackoff. The knowledge complexity of interactive proofsystems (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 zeroknowledge proof systems. Journal of
the ACM, 38, 1 1991. PDF
 J. Quisquater et al. How to Explain ZeroKnowledge Protocols to Your Children. In: CRYPTO '89,
pages 628631, 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 NonPerfect Randomness
 Scott Aaronson: The Quest of Randomness, Link
 Scott Aaronson: Quantum Randomness. Link

Grades 
 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
