max planck institut
informatik

# Sublinear Algorithms (WS 2012)

## Basic Information

Lecture time: Wednesday 14.15-15.45 024, Campus E1.4 Thomas Sauerwald The course counts as computer science lecture (2 SWS, 6 CP). The lecture will be given in English. There will be 4 problem sets and you need to collect 50 percent of the points in order to be eligible for the final exam. The final exam will take place on Feb 21 (room TBA).

### Description

Sublinear algorithms is a new area, where the algorithm is required to give an (approximate) answer without reading or storing the whole input. It is of particular interest in the study of massive data sets that occur in many applications such as financial transitions, Internet traffic analysis, biological databases etc. Due to the sheer size of these data sets that goes beyond billions, even linear time algorithms may be far too slow.

Despite the seemingly strong requirement to run in sublinear time, sublinear time algorithms exist for various problems in databases, graph theory, geometry, combinatorial optimization, string operations and statistical analysis. In this course we will introduce the basic models and techniques of sublinear algorithms, and cover some of the highlights in this exciting area.

## Lectures

Date Topic Reference
Oct 17 1. Introduction, Motivation, Examples Slides

Oct 25 2. Testing Monotonicity of Lists, Approximating Number of Connected Components Lecture Notes

Oct 31 3. Approximating Number of Connected Components (analysis), Hoeffding's inequality (incl. proof) Lecture Notes

Nov 7 4. Testing Properties of Distributions (Uniformity) Lecture Notes

Nov 14 5. Testing Properties of Distributions (Uniformity (cntd.), Lower Bound) see Notes from Lecture 4 or Notes from Lecture 6

Nov 21 6. Testing Properties of Distributions (Lower Bound (cntd.)), Testing Closeness of Distributions Lecture Notes

Nov 28 7. Testing Properties of Dense Graphs: Bipartiteness Lecture Notes (small update on Dec. 14)
Dec 5 8. Testing Properties of Dense Graphs: Bipartiteness (cntd.) see updated Notes from Lecture 7
Dec 12 9. Testing Properties of Dense Graphs: MAX-CUT Lecture Notes

Dec 19 10. Testing Properties of Dense Graphs: MAX-CUT see updated Notes from Lecture 9
Jan 9 no class
Jan 16 11. Regularity Lemma see the book "Graph Theory" (Chapter 7) by Reinhard Diestel
Jan 23 12. Regularity Lemma (cntd.)
Jan 30 13. Regularity Lemma: Application to Testing Triangle-Freeness Lecture Notes

Feb 6 14. Streaming Algorithms: Count-Min-Sketch and Approximating the Number of Distinct Elements Lecture Notes

If you have any comments (typos, questions etc.) regarding the lecture (notes), please send an email (sauerwal@mpi-inf.mpg.de) or approach me after lecture.

### Exercises

Your homework can be submitted by email or by dropping it at my office (E1.4, room 307) or the secretaries office (E1.4, room 302).
The next tutorial will be on Feb 7 starting 4.00pm in room 0.24 (the lecture room)

### Some References

• Noga Alon, Yossi Matias, Mario Szegedy: The Space Complexity of Approximating the Frequency Moments. Journal of Computer and System Sciences, 58(1): 137-147, 1999
• Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, Patrick White: Testing that distributions are close. Proceedings of 41st Annual Symposium on Foundations of Computer Science (FOCS 2000), pages 259-269, 2000
• Artur Czumaj, Christian Sohler: Testing Expansion in Bounded-Degree Graphs. Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), pages 570-578, 2007
• Reinhard Diestel: Graph Theory, Graduate Texts in Mathematics, Volume 173, Springer Verlag, 2010.
• Funda Ergün, Sampath Kannan, Ravi Kumar, Ronitt Rubinfeld, Mahesh Viswanathan: Spot-Checkers. Journal of Computer and System and Sciences, 60(3): 717-75, 2000
• Uriel Feige: On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph. SIAM Journal on Computing, 35(4): 964-984, 2006
• Oded Goldreich, Dana Ron: Property Testing in Bounded Degree Graphs. Algorithmica 32(2): 302-343, 2002
• Satyen Kale, C. Seshadhri: An Expansion Tester for Bounded Degree Graphs. SIAM J. Comput. 40(3): 709-720, 2011
• Dana Ron: Algorithmic and Analysis Techniques in Property Testing, 2009
More Courses of the Algorithms and Complexity Group
Search MPII (type ? for help)