Given by Eldar Fischer (Room 625, Tel: 3967).
This is no longer the course homepage. Please head instead to the new Webcourse page. The course itself has also been revised. The main changes are that the course will be worth three points, and will have four weekly hours (two lecture hours, plus a tutorial hour and a practice hour given by a TA). The final grading remains homework based and similar to previous years.
Pages with specific information for previous years: 2002-2003, 2003-2004, 2004-2005, 2005-2006, 2006-2007, 2007-2008, 2008-2009, 2009-2010.
Combinatorics and computer science have more to do with probabilistic theory than 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. Since then probabilistic methods have revolutionized and continue to revolutionize combinatorial theory to this present day. In computer science theory, apart from the numerous applications that combinatorial theory has in this field, probability theory also plays a pronounced 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 possible 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 the proof of combinatorial theorems. These methods will in most cases be presented with an accompanying proof of their correctness, as well as some applications. Basic knowledge of probabilistic theory is assumed (and should be augmented with Assignment Zero, see below), 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 borders between combinatorial theory and computer science are blurred in many places, 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 during the exam period (as this course has no exam you can use the saved time for completing the last exercise). There is no joint submission possible; each of you has to submit your own solutions. The general theme is that consultation on the harder questions is Ok, but not copying. In the unfortunate case that I will not witness the individualistic feel that comes from each of you formalizing your answers on your own, I may change the rules (in the many years of the course this has not happened yet).
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). Usually the final formula is of the form "ax+b", where "x" is the sum of the grades for all questions, but this is not guaranteed.
There are some basic intuitions in probabilistic theory that help the understanding of this course (and are good for you in general), but for which there is no room in the course itself. For experiencing them you are requested to download the so-called "Assignment Zero" below and try to solve the questions. This one is not for submission and will not form part of your grade. For your convenience the questions are bundled with their solutions; if you cannot solve them on your own then you should at least understand the solutions in full.
The course material such as exercises and solutions will be given in the page specific for this year, linked at the top of this page. For your convenience the material which does not change every year is duplicated 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.
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 in addition it is proven that the probability that a random structure is the required one is not only positive, but is also bounded from below, then it 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.
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 such an 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 an interesting algebraic method in itself, but is unfortunately outside the scope of this probabilistic methods course.