14.2.2002: For those of you that want to get a quick start on the topics of this seminar, it is recommended that you browse my survey on the subject. Here is a direct link.
11.3.2002: A new topic has been added, about testing of dense k-SAT instances. A relevant reference has been added as well.
13.3.2002: To those that asked: The timing of the oral test will be arranged with each of you on an individual basis, with the only constraint being that it has to be this semester (up to the first half of July).
07.4.2002: Due to some students getting Tzav-8, I will give the next talk on April 10; the April 22 talks will be the scheduled ones about testing of dense graphs, and the April 24 ones will be those that were scheduled originally for April 10.
I will also assign topics to all students that do not have them yet. I will first need another volunteer for an April 24 talk about testing of strings. There is also one open spot regarding sparse graph testing, one or two spots about lower bounds (most of the lectures about lower bounds will be given by me), two open spots about dense k-SAT testing (think of this as generalized hypergraph colorability testing), and some more open spots about dense graphs and about monotonicity.
29.4.2002: Here is the schedule for the following weeks.
29.4.2002: From now on we are meeting in Taub 7.
15.5.2002: The schedule for the rest of the seminar:
13.6.2002: Some last minute changes in the schedule due to technical difficulties: Ziev Weinstein's lecture will be the first talk in 19.6, and Ran Wolf's lecture will be moved to 26.6. I will then conclude the seminar with a survey of some open questions in the field. Remember that apart from lecturing, each participating student should also undergo a short oral exam. Those of you that haven't yet done so, please coordinate with me the topic and the date.
03.7.2002: All those that did not set up with me the 20 minute oral exam yet, please do it now. Remember that it should be taken until the end of July. Good luck.
05.8.2002: I have submitted today the grades. For those of you that want to know the break-up of their grades (the 70% talk and the 30% test), I have put these near the door of my office.
This seminar deals with the relatively young but rapidly growing field of combinatorial property testing. The seminar will be given in Hebrew, only its web-page 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, usually only a constant number of bits. 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.
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 subject that will be set up in advance (and not covered by the talk). You will be allowed some choice of the test subject.
Full attendance is mandatory. Aside from this, the grade will be based 70% on the given talk and 30% on the test.
There is currently no introductory textbook on this subject, but there are several surveys, [R], [F] and [G]. There is also extensive literature, the bibliography at the end of this page is only a small part of it. you may have to gather information from more than one paper in preparation for your talk.
Students participating in the seminar will each give a talk on one of the following subjects (the talks will be one to two hours long, depending on the number of students). Some subjects are large enough in their scope to merit more than one session. Subjects marked as "mandatory" will be given priority over other subjects when assigning the talks to be given by the students.
It is recommended that you browse some of the articles (links to them are provided in the bibliography section below) in preparation for the seminar, to help decide your choice of a topic. Start by taking a look at the surveys, and then take a look at the articles related to the subjects on which you may be interested in giving a talk.
This will be given by me. It will include the definition of property testing, a proof example of a simple testing algorithm, and a short survey of some of the main results in the following topics.
It was proven in [AKNS] that given a fixed regular language (of binary strings), a string can be efficiently tested for the property of being in that language. On the other hand, there already exist context free languages that are not testable. The positive result was then generalized in [Ne], where it is proven that all languages recognizable by a fixed-width oblivious read-once branching program are testable; this paper will form the main part of a student-given talk on this topic.
The fact that being k-colorable (for a fixed k) is a testable graph property is already implicit in a proof by Rödl and Duke from 1985, that uses the Regularity Lemma of Szemerédi (note that this has appeared before the notion of testing was formalized). The first explicit investigation into graph property testing appears in [GGR], where it is proven that a general class of partition-related graph properties is testable, and in particular contains a much improved proof of the testability of k-colorability of graphs. The [GGR] paper is considered a milestone in the field of property testing.
This subject has some historic significance in its relation to the first investigation into property testing, and is also linked to the topics of program checking and probabilistically checkable proofs. The first result in the field is [BLR], concerning linearity testing. A good source for results concerning low-degree tests is [RS].
There are properties which can be proven to require many queries to test. The proofs usually use a simple instance of Yao's method; a talk on this subject should cover this method, an example (probably the proof that it is hard to test two graphs for the property of being isomorphic), and the difference (in some cases) between the efficiency of adaptive testing algorithms versus non-adaptive ones. This subject is scattered between several papers (e.g. the first non-testable property was given in [GGR], a proof about graph isomorphism exists in [AFKS] but it can be improved upon, and so on); I will help the student giving this talk to sort out the relevant material.
This subject spans several topics. In [EKRRV] it was proven (among other things) that a sequence of n integers can be tested for the property of being monotone nondecreasing using O(log(n)) many queries. While this is more than the usual constant, it is still a low number (note also that the model itself is different - here the input is not binary). I will probably present this particular result as one of the examples in the introduction I will give at the beginning of the seminar.
Another problem is to test that a binary function over the d-dimensional Boolean hypercube is monotone - the function f is considered monotone if ui<=vi for every i implies f(u1,...,ud)<=f(v1,...,vd). In [GGLRS] it is proven that this property can be tested using O(d) queries. This result can form the basis for a talk. There are also other investigations of the topic of testing for monotonicity, such as the generalization in [DGLRRS] of the result of [GGLRS]. If more students will be interested in giving talks on this topic, additional material will be provided.
This subject is relatively heavy, so it requires a close collaboration of at least two students that will give talks about it. The talks should include a presentation of the Regularity Lemma, including an outline of its proof and some of its other applications, and the proof by N. Alon (found in [GGR]) that the property of not having a fixed graph H as a (not necessarily induced) subgraph is testable. The full proof of the generalization in [AFKS] is probably out of the scope of this seminar.
This deals with a different model of graph testing, that is more suitable for for testing properties of sparse graphs (the original model in essence does not distinguish between sparse graphs and empty ones). The difference is both in the in the input format (here the graphs are given by their adjacency lists), and in the definitions of what it means to be close. The main paper on this topic is [GR].
The term "dense" means that a k-SAT instance over n variables is considered far from being satisfiable if one has to remove from it at least a number of clauses that is proportional to nk to make it satisfiable. This is very much related to testing (dense) hypergraphs for colorability, investigated by Czumaj and Sohler. The paper proving the existence of a test for satisfiability in this setting is [AS].
Generalizing the results about testing for linearity or for low degree, [Ru] deals with properties defined using functional equations (for example, "f(x+y)=f(x)+f(y)" is the functional equation for the linearity of f). Testability is proven by showing "robustness", which in essence means that the algorithm of checking that the equation is satisfied at randomly chosen points is already a test for the property.
An exciting new topic that combines property testing and computational geometry. Some results are in [CSZ] and other papers by these authors, but there is a good chance that a student giving a talk on this subject will also have to contact the authors personally for some of the details of their proofs.
This is somewhat of a digression from property testing, as it deals with algorithms that receive samples (according some input distribution) rather than make queries. Nevertheless this is related, and appears here because of its possible applications as well as its inherent interest. The first result about testing that the input distribution is close to uniform (based only on independent samples chosen according to the distribution) was essentially proven by O. Goldreich and D. Ron; other results and a full description of this problem are found in [BFRSW].
Depending on the interest, number of participating students, and other factors, more topics may be available. For example, the algebraically motivated properties investigated in [EKRRV], or property testing in the quantum framework that was investigated in [BFNR].
I may introduce some additional material during the seminar to provide additional perspectives concerning some of the results, but the student-given talks themseleves will be mostly based on the articles cited in the description of each subject, and whose full details are given below.
[F] E. Fischer, The art of uninformed decisions: A primer to property testing, The Computational Complexity Column of The Bulletin of the European Association for Theoretical Computer Science 75 (2001), 97-126. Availability: my homepage.
[G] O. Goldreich, Combinatorial property testing - a survey, In: Randomization Methods in Algorithm Design (P. Pardalos, S. Rajasekaran and J. Rolim eds.), AMS-DIMACS (1998), 45-60. Availability: Oded Goldreich's homepage.
[R] D. Ron, Property testing (a tutorial), In: Handbook of Randomized Computing (S. Rajasekaran, P. M. Pardalos, J. H. Reif and J. D. P. Rolim eds), Kluwer Press (2001). Availability: Dana Ron's homepage.
[AFKS] N. Alon, E. Fischer, M. Krivelevich and M. Szegedy, Efficient testing of large graphs, Combinatorica 20 (2000), 451-476. Availability: my homepage.
[AKNS] N. Alon, M. Krivelevich, I. Newman and M. Szegedy, Regular languages are testable with a constant number of queries, Siam Journal on Computeing 30 (2001), 1842-1862. Availability: Ilan Newman's homepage.
[AS] N. Alon and A. Shapira, Testing satisfiability, Proceedings of the 13th ACM SODA (2002). Availability: Asaf Shapira's homepage.
[BFRSW] T. Batu, L. Fortnow, R. Rubinfeld, W. Smith and P. White, Testing that distributions are close, Proceedings of the 41st IEEE FOCS (2000), 259-269. Availability: Ronitt Rubinfeld's homepage.
[BLR] M. Blum, M. Luby and R. Rubinfeld, Self-testing/correcting with applications to numerical problems, Journal of Computer and System Sciences 47 (1993), 549-595. Availability: Michael Luby's homepage.
[BFNR] H. Buhrman, L. Fortnow, I. Newman and H. Röhrig, Quantum property testing, Proceedings of the Erato workshop on Quantum Information Science (2001). Availability: Lance Fortnow's homepage.
[CSZ] A. Czumaj, C. Sohler and M. Ziegler, Property testing in computational geometry, Proceedings of the 8th Annual European Symposium on Algorithms (2000), 155-166. Availability: Artur Czumaj's homepage.
[DGLRRS] Y. Dodis, O. Goldreich, E. Lehman, S. Raskhodnikova, D. Ron and A. Samorodnitsky, Improved testing algorithms for monotonicity, Proceedings of the 3rd International Workshop on Randomization and Approximation Techniques in Computer Science (1999), 97-108. Availability: Dana Ron's homepage.
[EKRRV] F. Ergün, S. Kannan, R. Kumar, R. Rubinfeld and M. Viswanathan, Spot checkers, Journal of Computer and System Science 60 (2000), 717-751. Availability: Ronitt Rubinfeld's homepage.
[GGLRS] O. Goldreich, S. Goldwasser, E. Lehman, D. Ron and A. Samorodnitsky, Testing monotonicity, Combinatorica 20 (2000), 301-337. Availability: Dana Ron's homepage.
[GGR] O. Goldreich, S. Goldwasser and D. Ron, Property testing and its connection to learning and approximation, Journal of the ACM 45 (1998), 653-750. Availability: Dana Ron's homepage.
[GR] O. Goldreich and D. Ron, Property testing in bounded degree graphs, Proceedings of the 29th ACM STOC (1997), 406-415. Availability: Dana Ron's homepage.
[Ne] I. Newmanm, Testing of functions that have small width branching programs, Proceedings of the 41st IEEE FOCS (2000), 251-258. Availability: Ilan Newman's homepage.
[Ru] R. Rubinfeld, On the robustness of functional equations, {\em SIAM Journal on Computing} 28 (1999), 1972--1997. Availability: Ronitt Rubinfeld's homepage (note the slightly different title there).
[RS] R. Rubinfeld and M. Sudan, Robust characterization of polynomials with applications to program testing, SIAM Journal of Computing 25 (1996), 252-271. Availability: Ronitt Rubinfeld's homepage.