29.5.2005: Some (final?) schedule updates.
14.5.2006: A tentative (note the use of this word) schedule for the rest of the semester is now online.
2.4.2006: The schedule is updated with the upcoming talks. Also watch your email for copies of some of the talk slides.
14.2.2006: The list of topics and papers is currently not updated from last year. There may be small changes with regards to adding talk options or pointing to newer versions of articles.
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]. 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, you will need to do the following reading assignments (in Hebrew):
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).
| Date | Person | Topic | Comments |
| 19.3, 26.3 | Me | Introduction and list of topics | |
| 2.4 | Liron Bornstein | Bipartiteness testing in dense graphs | |
| Evgeny Gokhberg | Maxcut estimation | ||
| 9.4 | Noa Shelef and Dorit de-Hund | Monotonicity over the cube | |
| 16.4 | Happy Passover | ||
| 23.4 | Eyal Rozenberg | Matrix testing | Guest talk |
| 7.5 | Alina Kremerov and Tami Dubrovnsky | Junta testing | |
| 14.5 | Yael Libis and Ephrat Cohen | Read-once branching programs | |
| 21.5 | Orly Yahalom | Testing tree colorings for convexity | Guest talk |
| 28.5 | Me | Lower bounds and adaptivity | |
| 4.6 | Anath Paskin | Testing and estimating dense graphs | |
| 11.6 | Raviv Weinik | Lower bound on testing sparse graphs | |
| Aviad Sagiv | Testing with geometrical queries | ||
| 18.6 | Michal Hashavit | Distribution-free monotonicity testing | |
| Eran Frank | Tolerant and intolerant testing | ||
| 25.6 | Oded Lachish | Testing of low complexity languages | Guest talk |
| 2.7 | Me | Current property testing research |
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. Topics that are marked by "mandatory" will be given priority over the other topics when assigning lectures.
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 field, with special attention given to some of those from which you can choose your talk.
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].
We deal here with the dense model of graphs. The input graph is given in terms of its adjacency matrix, so a query consists of finding out whether a given pair of vertices forms an edge, and two graphs over the same set of n vertices are considered ε-close if their edge sets differ by no more than εn2 edges. 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. Although in the dense model one can test properties which are NP-hard to decide, this does not affect the polynomial hierarchy.
This topic can easily hold 2-3 talks. From [GGR] there will be a talk containing a general survey and testing for bipartiteness, and then there will be a talk about testing for being k-colorable for any fixed k>2, and possibly another one about testing that a graph has a given max-cut. For the possibility of giving a talk concerning Szemerédi's Regularity Lemma, see below.
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 last paper is ideal for two talks prepared in cooperation. There is also a paper [FN1] proving in a sense the optimality of these results, but this is a topic for the lower bounds part.
This subject spans several topics, and can hold 4 talks or more. 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 not constant, it is still a slowly increasing function (note also that the model itself is different - here the input is not binary). I will present this particular result as one of the examples in the introduction that 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 concerning testing for monotonicity, such as the generalization in [DGLRRS] of the result of [GGLRS].
If we do not limit ourselves to cubes, there are several results concerning testing monotonicity over more general partially ordered sets [FLNRR]; there are also lower bounds in some cases (see below). Monotonicity testing is also the first topic in which there is a nontrivial results about testing in the weighted context [KH].
The idea here is to test that a Boolean function of n variables depends in fact on only k of them (where k is a constant). The test and its proof in [FKRS] use a mix of combinatorial theory and algebra; the old version of [FKRS] used Fourier analysis, and the newer one replaced it with careful use of expectation and variance.
There are properties which can be proven to require many queries to test. The proofs usually use a simple instance of Yao's method. It is likely that I will give the talk introducing Yao's method, an example for its use (the hardness of testing that two graphs are isomorphic), and perhaps also a talk about the issue of adaptive versus non-adaptive testing.
There are possibilities for several student talks on lower bounds. Examples are the proof in [EKRRV] of a lower bound for monotonicity testing of an integer sequence in a limited algorithmic model and its extension in [Fi1], as well as the proof in [FN1] that there exists hard to test properties that are decidable by read-twice constant width oblivious branching programs.
Apart from proving testability and non-testability of particular properties, there are efforts of proving general results that hold for whole classes of properties. The ultimate goal (which currently seems to be lying far in the future) is to provide a complete characterization of the testable properties, and currently there are some strong results in this direction.
In [GT] there are several results concerning graph property testing in the dense model. Mainly of interest to this seminar are the results about canonical testers, that state that all property testers in this model in a sense follow a nearly-identical algorithm.
In [CS1] there is a proof of a general method for proving testability of properties. Its potential lies in the fact that until now most positive results were proven by specialized methods, while general methods (such as Yao's method) mainly served for proving negative results.
This subject is hard to understand and hard to present well, but if there is a volunteer then it is an interesting subject to talk about. I am also considering giving the introductory talks myself followed by talks on more recent results by one of you.
The talks (it will certainly take more than one) should include a presentation of the concept of regularity and the Regularity Lemma of Szemerédi (with a sketch of the proof), and then the proof by N. Alon (found in [GGR]) that properties such as that of not containing triangle are testable. The full proof of the generalization of the above in [AFKS] is probably out of the scope of this seminar. However, some newer results are worth presenting, such as that of [Fi2] about how hard it is to test for isomorphism against a known graph, and that of [FN2] showing that for all testable graph properties one can actually estimate the distance of a given graph from the property (that last one is of the more advance topics here, so consider before volunteering). As an aside, the Regularity Lemma could easily take up a whole seminar by itself.
This deals with a different model of graph testing, that is more suitable for for testing properties of sparse graphs (the original dense 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) that determines the format of a valid query, and in the definitions of what it means to be close. The main paper on this topic is [GR].
The term "dense" above means that a k-SAT instance over n variables is said to be ε-far from being satisfiable if one has to remove from it at least εnk clauses to make it satisfiable (this is similar to the dense model of graph testing). The subject 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 of k-SAT instances is [AS] (the proof there is long enough for two talks).
This new endeavor asks the question of finding a property testing algorithm that in addition will accept (with high probability) all inputs that are δ-close to satisfying the property, where δ is usually dependent only on ε. It has recently started to attract attention; the results relevant to our seminar can be found in [PRR] (the paper that started this) and [FF].
This topic combines property testing and computational geometry. Some results are in [CSZ] and other papers by these authors (one should also consider the result of [ADPR] about testing for clustering). There are also results in [CS2] about a new querying model that is stronger than the usual one and may be more natural for geometrical properties. The best way to find about the results of Czumaj and Sohler is through their careful writeup in [So].
This is somewhat of a digression from property testing, as it deals with algorithms that receive samples (according to some input distribution) rather than make queries. Nevertheless this is related to property testing, 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 you may express in them, more topics may be available. For example, testing of properties defined by functional equations, as investigated in [Ru]. Other options are the algebraically motivated properties investigated in [EKRRV], or property testing in the quantum framework that was investigated in [BFNR].
Also, new advances in property testing are made all the time. I will be happy to supply an enterprising student with "hot from the press" articles (or even yet unpublished drafts) to give a talk about.
[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.
[ADPR] N. Alon, S. Dar, M. Parnas and D. Ron, Testing of clustering, Proceedings of the 41st IEEE FOCS (2000), 240-250. Availability: Noga Alon'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 Computing 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: Lance Fortnow'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 14th ACM-SIAM SODA (2003), 480-488. Availability: Lance Fortnow's homepage.
[CS1] A. Czumaj and C. Sohler, Abstract combinatorial programs and efficient property testers, Proceedings of The 43rd FOCS (2002), 83-92. Availability: Artur Czumaj's homepage.
[CS2] A. Czumaj and C. Sohler, Property testing with geometric queries, Proceedings of the 9th Annual European Symposium on Algorithms (2001), 266-277. Availability: Artur Czumaj'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.
[Fi1] E. Fischer, On the strength of comparisons in property testing, technical report. Availability: my homepage.
[Fi2] E. Fischer, The difficulty of testing for isomorphism against a graph that is given in advance, Siam Journal on Computing (2005), 391-397. Availability: my homepage.
[FF] E. Fischer and L. Fortnow, Tolerant versus intolerant testing for Boolean properties, Proceedings of The 20th CCC (2005). Availability: will appear shortly on my homepage.
[FKRS] E. Fischer, G. Kindler, D. Ron, S. Safra, and A. Samorodnitsky, Testing juntas, Proceedings of The 43rd FOCS (2002), 103-112. Availability: my homepage, or Guy Kindler's homepage for a fuller (but also more complex) version.
[FLNRR] E. Fischer, E. Lehman, I. Newman, S. Raskhodnikova, R. Rubinfeld and A. Samorodnitsky, Monotonicity testing over general poset domains, Proceedings of The 34th IEEE STOC (2002), 474-483. Availability: my homepage.
[FN1] E. Fischer and I. Newman, Functions that have read-twice constant width branching programs are not necessarily testable, Proceedings of The 17th CCC (2002), 73-79. Availability: Ilan Newman's homepage.
[FN2] E. Fischer and I. Newman, Testing versus estimation of graph properties, Proceedings of the 36th STOC (2005), Availability: my 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.
[GT] O. Goldreich and L. Trevisan, Three theorems regarding testing graph properties, Proceedings of the 42nd IEEE FOCS (2001); a full journal version should appear soon. Availability: Oded Goldreich's homepage.
[KH] E. Kushilevitz and S. Halevy, Distribution-free monotonicity testing, Proceedings of the 7th RANDOM and the 6th APPROX (2003). Availability: Eyal Kushilevitz's homepage (the last one in the publication list).
[Ne] I. Newman, Testing of functions that have small width branching programs, Proceedings of the 41st IEEE FOCS (2000), 251-258. Availability: Ilan Newman's homepage.
M. Parnas, D. Ron and R. Rubinfeld, Tolerant property testing and distance approximation, manuscript. Availability: Dana Ron's homepage.
[Ru] R. Rubinfeld, Robust functional equations and their applications to program testing, SIAM Journal on Computing 28 (1999), 1972-1997. Availability: Ronitt Rubinfeld's homepage.
[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.
[So] C. Sohler, Property testing and geometry, Dissertation, HNI-Verlagsschriftenreihe, Vol. 119, Heinz-Nixdorf Institute and University of Paderborn (2003). Availability: Christian Sohler's homepage.