Given by Eldar Fischer. Office hours: to be announced (Room 625).
2.3.2005: The graded Exercise 4 submissions are in my office, and the official solution is now online. As this concludes the course, you can expect the grades to come out in a couple of days.
9.2.2005: A clarification: With regards to the second question in the last exercise, you can use there anything you know from your physics studies concerning electric resistance networks.
7.2.2005: The graded Exercise 3 submissions are with me and free for the take. The official solution is now online.
23.1.2005: The last exercise is now online (and don't forget Exercise 3 for tomorrow). It features three questions and is due on 17.2.2005.
16.1.2005: The deadline for Exercise 3 has been extended to Monday 24.1.2005. Good luck.
2.1.2005: There was an error in the last question of Exercise 3. The site now has the corrected version.
30.12.2004: Just in time for the new year, the new exercise is here (and so are the solutions for the previous ones). Good luck.
28.12.2004: There is an error in the course book. In the middle of Page 17, in the formulation of the lemma that is equivalent to |S|=1, the middle two inequalities should be α0β1≤γ1δ0 and α1β0≤γ1δ0.
19.12.2004: The solution to the first two questions of Exercise 1 is online. On another issue, don't forget that the next class is a 3-hour one.
12.12.2004: Here is a reminder of the hint given in class for Question 1 in Exercise 2: It may help you to see what happens with respect to the degrees of the vertices, i.e. in how many "3-edges" each vertex participates. Also, for Question 3 (the isolating lemma one), if you only manage to prove it but with a different coefficient in the "1-3n/m" (instead of "3"), then feel free to submit it (it will be counted as a partial solution).
07.12.2004: Exercise 1 is checked. You can get yours from my office this Tuesday and Wednesday (from around noon); on Thursday I will not be in my office, but I will also bring the exercises to Sunday's class. Unfortunately there will be no possibility to get the grades from gr. By the way, I have changed the "2003" in a couple of previous news to the more correct "2004" :-)
23.11.2004: The new exercise is out; it includes four new questions and a "second chance" for the automorphism question. Its submission deadline is almost four weeks from now - use them, there will be no second chances for this one. Note that this time the questions are not ordered by ascending order of difficulty. Good luck.
14.11.2004: Here is a small hint for Question 3 in Exercise 1: Not all permutations are the same. It may do well to consider more than one case.
31.10.2004: Assignment 1, due 22.11, is now online. Good luck.
5.9.2004: The new year's site is up. This time there is a short preparatory work for you on the site, so please read about "Assignment Zero" and then head to the Course Material section below.
Combinatorics and computer science have more to do with probabilistic theory then first meets the eye.
In the realm of combinatorics, probabilistic methods were first introduced as a result of Erdös's pioneering work in the field, starting with his lower bounds on the function resulting from Ramsey's theorem. In computer science theory, apart from the numerous applications that combinatorial theory has in this field, probability theory also plays a pronounced explicit role. There are many instances in which probabilistic algorithms are considered, and other instances in which the algorithms are analyzed for a random input rather than for the worst case. It is worthy of note that there are still major open questions with regards to the strength that probabilistic algorithms may have over deterministic ones.
The primary goal of this course is to introduce some of of the probabilistic methods used in the analysis of algorithms and in combinatorial proofs, and some parts of probability theory that are commonly used in algorithmic analysis. Together with the methods themselves (in most cases with an accompanying proof of their correctness), some applications will be presented. Basic knowledge of probabilistic theory is assumed, as well as fair knowledge of algorithms, and some knowledge in combinatorial theory and mainly graph theory.
This course is mathematical as much as it is a course in computer science, and mathematical proofs play a major role in it. This is not unexpected; the boarders between combinatorial theory and computer science are many times blurred, and the topic of this course is such an instance.
During the course I will hand 3-4 assignments with 4-5 questions each. The time to complete an assignment will typically last 2-3 weeks. There is a good chance that the last assignment will be given near the end of the course, in which case it will be collected after the last lecture. Each of you have to submit your own answers and understand them. I may be lenient if you consult each other about general methods concerning the harder questions, but not so lenient if people start handing me 1:1 copies of the answers.
I reserve the right to call some of you up and ask you about your answers, although I expect to do this rarely. The scenarios in which I may do this include the following:
There is no test; the grade will be based solely on the performance in answering the assignment questions (all questions and assignments count, not just the submitted ones). I will be keeping a record of the performance for every individual question, so the final formula for the grade will not necessarily be the average grade of the assignments; I am not giving the formula in advance because I may decide in the end to give a factor (or to refrain from giving one).
The lecture notes for this year's course will most probably be almost identical to the notes of last year's course, which you can view here.
Assignment 0 (not for submission) and 1-4 (expired): here.
Solution of Assignments 0-4: here.
The following are not all of the subjects of the course, just a list of some of its topics that I believe gives an idea as to what the course is about (Note: Some may change during the course).
To prove that a certain structure exists, one can prove instead that a random structure will with some probability be the required one. In its simplest form the probabilistic method is just a shorthand for counting. If it is proven that the probability that a random structure is the required one is not only positive, but is also bounded from below, this may result in a probabilistic algorithm for obtaining the structure as well.
For every instance of 3SAT with n clauses, there exists an assignment to its variables for which at least 7n/8 of the clauses are satisfied. Why? Because the expected number of satisfied clauses when choosing the assignment uniformly at random is 7n/8. Since the expectation is linear (the expectation of a sum of variables is the sum of their expectations), its calculation is easy. The expectation is probably the most used parameter in probabilistic proofs in computer science.
This lemma is used in algorithms, in order to reduce a case where one needs to find some maximal structure (e.g. in a graph), to the case where the maximal structure is unique.
This is a fancy name to proving bounds using the mean deviation parameter of a random variable. It is useful when one needs to prove that a random variable gets with high probability a value that is close to its expectation, using the Chebyschev inequality.
In some settings, such as when summing many independent coin-flips, the probability that a random variable deviates substantially from its expectation is exponentially low. Sometimes such bounds are what is required for completing a proof; this relatively simple method is also one of the most used ones.
Consider a stock option: Every day its price is supposedly the expectation of the price of the stock itself on the expiry date, conditioned on the information gathered so far. How can a sequence of random variables representing this accumulation of information behave? The properties of such sequences, and most notably their large deviation inequalities, have applications also in combinatorial proofs.
This lemma is used more in mathematical proofs than in computer science. Still, this unorthodox and beautiful use of probabilistic theory merits the attention of the course.
Deterministic algorithms are preferable to probabilistic ones, and this is where derandomization techniques may help. I will cover the method of conditional expectations, and if there is time, I will also outline the method of small sample spaces; the complete construction of small sample spaces is also intended to be part of a future advanced topics course on algebraic methods.
This is method for proving lower bounds on probabilistic algorithms, that works by shifting the randomness from the algorithm to its input. In many cases deterministic algorithms with random inputs are easier to analyze than probabilistic algorithms.