Lecture details:

Week 1 (September 12  16):
Mastermind, BlackBox 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 blackbox complexity.
The blackbox 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, blackbox complexity provides lower bounds for the efficiency of problemindependent search heuristics such
as randomized hillclimbers, simulated annealing or evolutionary algorithms. The cycle of asking solutions and learning their quality
immediately leads to a gametheoretic flavor. For example, as we will see in the lecture, the blackbox complexity of the OneMax function
class is intimately related to the classic guessing game of Mastermind.
Blackbox complexity regained high activity as research area in the last few years. In this lecture, we give an indepth 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:0011:00

Organization, Overview content first week, guessing mininum and maximum of n numbers with comparisons

(tentative)

Mo 11:1512:15

Lecture: Introduction to blackbox complexity. Game "Ask a bitstring". Definition blackbox complexity, scheme of a blackbox algorithm, motivation: information theory, complexity theory for randomized search heuristics, randomized local search.


Mo 13:3014:30

Short exercises (30min quiet work, 30min discussion)


Mo 14:4516:00

Blackbox complexity of general leadingones class, (1+1) evolutionary algorithm


Home work




Tu 10:0011:00

Test, discussion of homework


Tu 11:1512:15

Mastermind, blackbox complexity of onemax. Technique: Randomized strategies


Tu 13:3014:30

Short exercises


Tu 14:4516:00

Randomized strategies II. Guessing a number with one lie. Blackbox complexity of leadingones II [DoerrWinzen2011]


Home work:

Among others, reading assignment tenure games [Spencer1994]



We 10:0011:00

Test, discussion of homework


We 11:1512:15

Lower bounds: Adhoc solution for needle functions, Yao's minimax principle


We 14:0015: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 blackbox complexity [LehreWitt2010]



Th 10:0011:00

Test, discussion of homework


Th 11:1512:15

Unbiased blackbox complexity [LehreWitt2010, DoerrKötzingWinzen2011]


Th 13:3014:30

Short exercises


Th 15:3020:00

Project groups



Fr 10:4512:45

Presentation and discussion of project groups results


Reading assignment




Monday 11:0012: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:0015:00 or 16.0017: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:0016:15

Lecture: Of balls and bins  randomized load
balancing 
(tentative)






Tu 10:0012:15

Lecture: The power of two choices in randomized
load balancing 







We 10:0012:15

Lecture: The power of two choices in hashing:
Multiplechoice and cuckoo hashing 





Th 10:0012: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 realworld networks. Among other things, we will see that most realworld networks have similar properties. For example, we will discuss the popular smallworld phenomenon. Then, we will consider classical and wellestablished models for realword networks, like the preferential attachment model and inhomogeneous random graphs. Finally, we will discuss more recent developments, which postulate that the geometry of realworld networks is hyperbolic, and study some exciting implications of that.
The tentative schedule for the lectures is given below. Exercises will take place 10:3011:30, starting on Tuesday.There will be an oral exam on Tuesday morning of Week 4 for this part of the course.
Literature:
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:0016:00

Lecture: Complex Networks and Preferential Attachment 
(tentative)






Tu 14:0016:00

Lecture: Classical and Inhomogeneous Random Graphs 







We 14:0016:00

Lecture: The typical diameter of Complex Networks 





Th 14:0016: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 1416 (room 24)

Lecture: Introduction to Randomized Rumor Spreading and Basic Results 







We 1416 (room 24)

Lecture: Randomized Rumor Spreading on Hypercubes 





Th 1416 (room 24)

Lecture: Randomized Rumor Spreading, Conductance and other Expansion Parameters of Graphs 







Fr 1416 (room 24)

Lecture: Randomized Rumor Spreading on Models for Social Networks 






Literature:
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 399408, 2010.
Chierichetti, Lattanzi and Panconesi, Rumor Spreading in Social Networks, Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP'09), pages 375386, 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 1587915882, 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 2130, 2011.
Feige, Peleg, Raghavan and Upfal, Randomized Broadcast in Networks, Random Structures and Algorithms, vol. 1, no. 4, pages 447460, 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 5768, 2011.
Giakkoupis and Sauerwald, Rumor Spreading and Vertex Expansion, Proceedings of the 23rd ACMSIAM Symposium on Discrete Algorithms (SODA'12), to appear.
Fountoulakis, Panagiotou and Sauerwald, UltraFast Rumor Spreading in Social Networks, Proceedings of the 23rd ACMSIAM 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 565574, 2000.
Pittel, On Spreading a Rumor, SIAM Journal on Applied Mathematics, vol. 47, no. 1, pages 213223, 1987.
Material:
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

