Lecturer 
Kurt Mehlhorn
and He Sun


Time 
Monday 1618, 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 MPISWS Kaiserslautern and TUKL Informatics. The videocast location is
Room 112, MPISWS Kaiserslautern, PaulEhrlichStr. 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.

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.

Preliminary Schedule 
Date 
Lecture 
Topic 
Lecture Notes 
Main References 
Other References 
Apr. 22

He

Introduction

slides



Apr. 29

He

P vs. NP, and PolynomialTime 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

ZeroKnowledge Proofs

Lecture Notes

[Gol10] 
[GMR89,GMW91,QQQ89] 
Jul. 8

He

PublicKey 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

Grading 
 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 CountMin Data Structure. IEEE Software, (2012). PDF
 [CM05] G. Cormode, and S. Muthukrishnan: An Improved Data Stream Summary: The CountMin Sketch and its Applications. J. Algorithm 55(1): 5875 (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): 439561
PDF
 [Val84] L. Valiant: A theory of the learnable. Communications of the ACM, 27(11):11341142, 1984.
PDF
 [Gol10] O. Goldreich: A Short Tutorial of ZeroKnowledge, 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, 603618, 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):117286, 2005. PDF
 [GMR85] 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
 [GMW91] 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
 [QQQ89] J. Quisquater et al. How to Explain ZeroKnowledge Protocols to Your Children. In: CRYPTO '89,
pages 628631, 1989. PDF
