This seminar deals with the relatively young but rapidly growing field of combinatorial property testing (most recent STOC conferences feature several papers on property testing and other sub-linear approximation algorithms, so the importance of this field in Computer Theory can by now be regarded as established). This seminar will be given in Hebrew, but its web-page (as well as most of the reading material for the seminar) is in English.
In essence, property testing deals with the information that can be gathered from an input by a probabilistic algorithm reading only a small portion of the input. In the original formulation the algorithm was allowed to read only a number of bits that is independent of the input size, but in many cases other sub-linear functions of the input size are also considered (for both upper and lower bounds). While it is hopeless for such an algorithm to decide whether the input satisfies a given property, in many cases it is possible to distinguish between inputs that satisfy the property and inputs that are "far" from satisfying it.
There is currently no introductory textbook on property testing, but there are several surveys, [R], [F] and [G] (for complete references see the topics page). There is also an extensive body of papers on the subject, the list provided at the end of this page is only a small part of it. Apart from an introduction to this topic, this seminar will also introduce you to the art of reading, understanding and presenting current research papers.
This seminar requires some knowledge and intuition regarding commonly used probabilistic methods. If you have attended the course Probabilistic Methods and Algorithms in our faculty (or a similar course elsewhere) then you already have that knowledge. Otherwise, get from the course website the lecture notes, the tutorial notes, and the exercise booklet, and read the following.
If for some reason you cannot get the material from Webcourse, here are direct links to older versions of some of it.
In preparation for the seminar it is also recommended that you browse my survey on the topic [F]. Then you can look at the list of topics below, and have an early idea which of them is of interest for you to give your seminar talk.
Students participating in this seminar are expected to attend all sessions and to give a talk on one of the subjects outlined below, as well as undergo a short oral test on a different subject that will be set up in advance (usually a talk by one of the other students). You will be allowed some choice of the test subject. The rational is that you will experience both the preparation of a talk (with help from me if you desire - I advise that you do a practice-talk in my office prior to the actual talk), as well as the on-your-own understanding of a subject for the test.
Full attendance is mandatory. Aside from this, the grade will be based 70% on the given talk and 30% on the test (but you have to pass both).
From 2007 the seminar homepage has been split into several pages, each with its own update schedule. Here are the links: