max planck institut
mpii logo Minerva of the Max Planck Society

Advanced Randomized Methods in Computer Science (Winter 2011/12)

Lecturers:   Prof. Dr. Benjamin Doerr, Dr. Konstantinos Panagiotou, Dr. Thomas Sauerwald, and Dr. Reto Spöhel
Time: Block course (4 weeks): September 12 - October 7, 2011
10 full hours lecture and 5 full hours exercises per week (between 10-16h each day)

Room: 24 (in the MPI building E1.4)

Content: This is a special lecture on randomized methods in computer science. Each of the four weeks highlights a recent hot topic and is taught by an expert on this topic. See the list of topics below for more information.

Audience: PhD and advanced Master students at Saarland University and other places. Participants should have a solid background in theory and basic knowledge on discrete probability spaces. At Saarland university, the course counts both as a mathematics and computer science lecture.

Lecture details:

Week 1 (September 12 - 16): Mastermind, Black-Box Complexity and Other Guessing Games (Lecturer: Benjamin Doerr)
Theoretical Computer Science investigates a number of combinatorial games not only for their fun, but because these games model situations computer scientists are interested in. The main focus of this part of the lecture is black-box complexity.

The black-box complexity of a problem asks for how often I have to evaluate the quality of suitably chosen solution candidates until I know its optimal solution. In such, black-box complexity provides lower bounds for the efficiency of problem-independent search heuristics such as randomized hill-climbers, simulated annealing or evolutionary algorithms. The cycle of asking solutions and learning their quality immediately leads to a game-theoretic flavor. For example, as we will see in the lecture, the black-box complexity of the OneMax function class is intimately related to the classic guessing game of Mastermind.

Black-box complexity regained high activity as research area in the last few years. In this lecture, we give an in-depth introduction to this beautiful research area, covering mostly works of the last two years (some of which done in Saarbrücken), but also some classic results like Chvátals Mastermind paper (partially rediscovering an earlier result by Erdős and Rényi). If time permits, we undertake a detour to liar games, which have been used to model noisy communication scenarios.

Syllabus: Mo 10:00-11:00 Organization, Overview content first week, guessing mininum and maximum of n numbers with comparisons
(tentative) Mo 11:15-12:15 Lecture: Introduction to blackbox complexity. Game "Ask a bit-string". Definition black-box complexity, scheme of a black-box algorithm, motivation: information theory, complexity theory for randomized search heuristics, randomized local search.
Mo 13:30-14:30 Short exercises (30min quiet work, 30min discussion)
Mo 14:45-16:00 Blackbox complexity of general leadingones class, (1+1) evolutionary algorithm
Home work

Tu 10:00-11:00 Test, discussion of homework
Tu 11:15-12:15 Mastermind, blackbox complexity of onemax. Technique: Randomized strategies
Tu 13:30-14:30 Short exercises
Tu 14:45-16:00 Randomized strategies II. Guessing a number with one lie. Black-box complexity of leadingones II [DoerrWinzen2011]
Home work: Among others, reading assignment tenure games [Spencer1994]

We 10:00-11:00 Test, discussion of homework
We 11:15-12:15 Lower bounds: Ad-hoc solution for needle functions, Yao's minimax principle
We 14:00-15:15 Lower bounds: Yao's minimax principle, application to needle and onemax, "information theoretic lower bound" [DrosteJansenWegener2006]
Home work: Among others, reading assignment introduction to unbiased black-box complexity [LehreWitt2010]

Th 10:00-11:00 Test, discussion of homework
Th 11:15-12:15 Unbiased blackbox complexity [LehreWitt2010, DoerrKötzingWinzen2011]
Th 13:30-14:30 Short exercises
Th 15:30-20:00 Project groups

Fr 10:45-12:45 Presentation and discussion of project groups results
Reading assignment

Monday 11:00-12:00 Written exam (45min)

Week 2 (September 19 - 23): The Power of Two Choices (Lecturer: Reto Spöhel)
The notion of the ‘power of two choices’ essentially dates back to a seminal 1994 paper by Azar, Broder, Karlin, and Upfal. Roughly speaking, their result states that if one allocates a large number of jobs to a large number of servers by assigning each job to the currently less busy of two randomly chosen servers, one observes a dramatic improvement in load balancing over a completely random assignment. This breakthrough result marked the beginning of the development of the power of two choices as a powerful new paradigm in computer science, with applications to load balancing, hashing, distributed computing, network routing, and other areas.

In this course we will discuss the original 1994 result and its applications, as well as other results in theoretical computer science which are based on the simple idea of ‘picking the better of two random choices’. Time permitting, we will also present some results from the field of discrete mathematics which make use of similar ideas.

The tentative schedule for the lectures is given below. Exercises will usually take place 14:00-15:00 or 16.00-17:00 each day; this will be decided in an online fashion. For regular course participants, there will be a short test each day from 9:30 to 9:50 (except on Monday, of course). There will be an oral exam on Monday morning of Week 3 for this part of the course.

Program: Mo 14:00-16:15 Lecture: Of balls and bins - randomized load balancing
Tu 10:00-12:15 Lecture: The power of two choices in randomized load balancing
We 10:00-12:15 Lecture: The power of two choices in hashing: Multiple-choice and cuckoo hashing
Th 10:00-12:15 Lecture: Network routing, Valiant's paradigm, and the power of two choices
Fr 10:00 - 12:15 Lecture: The power of two choices in random graph processes

Week 3 (September 26 - 30): Models for Complex Networks (Lecturer: Konstantinos Panagiotou)
Networks of various kinds have been in the focus of science for a long time in several disciplines. Such networks provide an abstract way of studying relationships between elements of complex systems. Examples include technological networks, like the Internet, biological networks, like the human brain, and social networks, which describe the interaction between individuals.

In this part of the course we will study several models for complex networks that have been introduced in the literature. We will begin with studying empirical work, which reveals the most important and fundamental characteristics of real-world networks. Among other things, we will see that most real-world networks have similar properties. For example, we will discuss the popular small-world phenomenon. Then, we will consider classical and well-established models for real-word networks, like the preferential attachment model and inhomogeneous random graphs. Finally, we will discuss more recent developments, which postulate that the geometry of real-world networks is hyperbolic, and study some exciting implications of that.

The tentative schedule for the lectures is given below. Exercises will take place 10:30-11:30, starting on Tuesday.There will be an oral exam on Tuesday morning of Week 4 for this part of the course.

Lecture Notes on Random Graph Models by Remco van der Hofstad
D. Krioukov, F. Papadopoulos, M. Kitsak, A. Vahdat, M. Boguna, Hyperbolic Geometry of Complex Networks, Physical Review E, v.82, 036106, 2010
M. Boguna, F. Papadopoulos, and D. Krioukov, Sustaining the Internet with Hyperbolic Mapping, Nature Communications, v.1, p.62, 2010.

Program: Mo 14:00-16:00 Lecture: Complex Networks and Preferential Attachment
Tu 14:00-16:00 Lecture: Classical and Inhomogeneous Random Graphs
We 14:00-16:00 Lecture: The typical diameter of Complex Networks
Th 14:00-16:00 Lecture: Routing in Complex Networks
Fr 14:00 - 16:00 Lecture: A Glimpse into the Furure: Graphs and Geometry
Week 4 (October 4 - 7): Randomized Rumor Spreading (Lecturer: Thomas Sauerwald)
Randomized rumor spreading protocols provide a very elegant and efficient way for spreading information in networks. The basic idea is that in each round, every node chooses a random neighbor to exchange information. This paradigm ensures that randomized rumor spreading protocols are easy to implement, local and robust against failures.

We first present some basic results to illustrate the fundamental techniques (including a tight runtime analysis for hypercube). Then we investigate the relationship between randomized rumor spreading and the expansion of the underlying network such as the conductance. Finally, we study rumor spreading on graphs that are popular models for social networks like facebook or twitter. It turns out that on these graphs, randomized rumor spreading is extremely fast.

A tentative schedule is given below (Exercises will start on Wednesday):

Tu 14-16 (room 24) Lecture: Introduction to Randomized Rumor Spreading and Basic Results
We 14-16 (room 24) Lecture: Randomized Rumor Spreading on Hypercubes
Th 14-16 (room 24) Lecture: Randomized Rumor Spreading, Conductance and other Expansion Parameters of Graphs
Fr 14-16 (room 24) Lecture: Randomized Rumor Spreading on Models for Social Networks


Chierichetti, Lattanzi and Panconesi, Almost tight bounds for rumour spreading with conductance, Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC'10), pages 399-408, 2010.

Chierichetti, Lattanzi and Panconesi, Rumor Spreading in Social Networks, Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP'09), pages 375-386, 2009.

Chung and Lu, The average distances in random graphs with given expected degrees, Proceedings of the National Academy of Sciences, Vol. 99, No. 25, pages 15879-15882, 2002.

Doerr, Fouz and Friedrich, Social networks spread rumors in sublogarithmic time, Proceedings of the 43rd ACM Symposium on Theory of Computing (STOC'11), pages 21-30, 2011.

Feige, Peleg, Raghavan and Upfal, Randomized Broadcast in Networks, Random Structures and Algorithms, vol. 1, no. 4, pages 447-460, 1990.

Giakkoupis, Tight bounds for rumor spreading in graphs of a given conductance, Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science (STACS'11), pages 57-68, 2011.

Giakkoupis and Sauerwald, Rumor Spreading and Vertex Expansion, Proceedings of the 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA'12), to appear.

Fountoulakis, Panagiotou and Sauerwald, Ultra-Fast Rumor Spreading in Social Networks, Proceedings of the 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA'12), to appear.

Karp, Shenker, Schindelhauer and Voecking, Randomized Rumor Spreading, Proceedings of the 41st IEEE Foundations of Computer Science (FOCS'00), pages 565-574, 2000.

Pittel, On Spreading a Rumor, SIAM Journal on Applied Mathematics, vol. 47, no. 1, pages 213-223, 1987.

Lecture 1: Assignment 1, Slides, Lecture Notes

Lecture 2: Assignment 2, Lecture Notes

Lecture 3: Assignment 3, Lecture Notes

Lecture 4: Slides, and see the notes from Lecture 3

Exams/Credit: The full course is equivalent to a regular 4h/week lecture plus 2h/week exercises. At Saarland University, this earns you 9 credit points when successful. As mentioned above, the course counts both as a mathematics and computer science lecture. Successful participation requires regular participation in the exercises, solving homework problems and an oral examination.

You may also participate only for two weeks (of your choice). In this case, we treat the course as equivalent to a 2h/week lecture plus 1h/week exercises (yields 5 CP). We are happy to accept external participants if space permits. If you want to transfer the credit to your institution, you should find out with them what is needed for that. Generally, thanks to the Bologna process, this should not be a problem.

Admission: Since we can accommodate a limited number of participants, we ask you to register for the course. To do so, send an email to Reto Spöhel, indicating which weeks you want to participate in. Admission is on a first-come-first-served basis.

Search MPII (type ? for help)