Given by Eldar Fischer. Office hours: to be announced (Room 625).
23.3.2004: The grades were submitted a few days ago, and now the site contains also the solutions for the final exercise. The final formula was "84x+16", or in other words, every "1/6" point in an exercise was worth a point in the final grade, counting back from 100. For your checked exercises and other questions and comments, please drop by my office. I hope you have enjoyed the course.
1.2.2004: The final lectures have now made it to this year's lecture notes - enjoy :-)
26.1.2004: I have now included the solution to Exercise 3, and the final Exercise 4 (corrected version). Good luck.
25.12.2003: I have added Exercise 3 to the site, as well as the solutions to Exercise 1 (those for Exercise 2 will come when your submissions are checked). I will add the new version of the large deviations and the martingale lectures by Sunday.
30.11.2003: I have added the new exercise to the site. Sorry for the delay.
18.11.2003: Tomorrow I will not have a reception hour, so those interested are welcome to look for me on Thursday at 16:30. On another issue, note that the site now also contains the beginning of the updated lecture notes for this year.
11.11.2003: A small correction in Exercise 1 Question 3: The assertion should be proven of course for k>1, not k>0.
04.11.2003: Some of the course topics are now updated.
03.11.2003: I have put the first exercise on line.
10.10.2003: This site is still under construction. In the meantime you can also take a look at last year's site.
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, probabilistic theory plays also 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 strengths 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 probabilistic 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 also 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, as the boarders between combinatorial theory and computer science are sometimes blurred, and the subject of this course is one of these instances.
During the course I will hand assignments; I have not decided yet whether I will hand 1-2 questions per week, or hand 3-4 assignments with 4-5 questions each during the course. 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).
Assignments 1-4 (expired): here.
Solutions for Assignments 1-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 can be proven that the probability that a random structure is the required one is not only positive, but 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 such "cumulative information" chains of random variables behave? The properties of such chains, 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.
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.
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 an advanced topics course on algebraic methods.