This lists the theses of the students that I have supervised. Much of the research presented in the theses also appears in individual articles, but I try to mention whenever a thesis contains otherwise unpublished work.
Arie Matsliah, Property testing and combinatorial approximation (Ph.D. thesis, 2008).
As its name suggest, this thesis explores diverse topics in the area of Property Testing. The highlights include graph isomorphism testing in the dense model, hypergraph partition properties, Two properties of orientations of graphs (in the massively parameterized model where the unordered “infrastructure graph” is fixed and its orientation is tested), and a trade-off result for 3-query Probabilistically Checkable Proofs of Proximity (PCPPs).
Orly Yahalom, Topics in property testing over massively parameterized models (Ph.D. thesis, 2008).
This thesis deals with the massively parameterized model, where part of the input is fixed and known to the algorithm in advance, while the other part needs to be queried, and the number of queries needs to be minimized. A large part of the thesis deals with properties of tree colorings, where the tree is fixed, and its vertex-coloring needs to be tested for certain properties, such as convexity (meaning that all color classes correspond to connected subtrees). Testing of orientations of graphs for being Eulerian (that is, all vertices having their in-degree equal to their out-degree) is also explored. Somewhat surprisingly, this property also exhibits some non-trivial lower bounds.
Sagi Ben Moshe, Using property testing for efficient detection of nearly-sorted relations (M.Sc. thesis, 2010).
This thesis suggests a way to speed up database operations, based on the intuition that large database files, even when they are no longer completely sorted due to prior modifications and operations, still retain some measure of “sortedness” from the last time they were sorted. Algorithms are given both for sorting a file satisfying this assumption, as well as testing (with a small number of queries) whether such an assumption indeed holds.
Eyal Rozenberg, Lower bounds and structural results in property testing of dense combinatorial structures (Ph.D. thesis, 2012).
This thesis strives for general results about property testing algorithms (such as hierarchy theorems) rather than results about specific properties, although there are also some results about specific properties, including a superpolynomial in ε lower bound on testing a matrix over {0,1,2} for not containing a forbidden submatrix.
Notably this thesis contains several results not published anywhere else, such as a result about sort-of-testing for an extension of hypergraph partition properties (which in particular cannot be “properly” tested).
Yonatan Goldhirsh, Algorithms for property testing and related problems (Ph.D. thesis, 2015).
Also here (as per its name) the thesis deals with diverse topics. These include results about massively parameterized testing (note in particular the unpublished result about tree colorings), partial testing (see below), and one of the founding works on the conditional distribution testing model.
Partial testing is where a tester needs to reject an input far from a given property, but must accept only inputs satisfying a smaller sub-property of the one used for rejection. A general lower bound proved in the thesis provides also a lower bound example on the “testing with proofs” model.