|
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 |
|
(tentative)
|
|
|
|
|
|
|
|
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.
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:00-16:00
|
Lecture: Complex Networks and Preferential Attachment |
|
(tentative)
|
|
|
|
|
|
|
|
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 |
|
|
|
|
|
|
|
|
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 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.
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
|
|---|
