Ph.D Thesis

Ph.D StudentGoldhirsh Yonatan
SubjectAlgorithms for Property Testing and Related Problems
DepartmentDepartment of Computer Science
Supervisor ASSOCIATE PROF. Eldar Fischer
Full Thesis textFull thesis text - English Version



In this thesis we study property testers from an algorithmic point of view. Namely, property testers with a substantial algorithmic component, and the power of algorithmic approaches to property testing problems.

First we study property testing in the massively parametrized model. The first problem we study in this model is testing read once formula satisfaction, in several flavors. For general formulas with gates of bounded arity we give a constant query property tester. For formulas with monotone gates of bounded arity we give a constant query complexity distance estimator. Finally, for and/or formulas we give a property tester with query complexity which is quasi-polynomial in the distance parameter. On the lower bound front, lower bounds against testing read once formula satisfaction over an alphabet of size 4, and against testing read once formula satisfaction for formulas with monotone gates over an alphabet of size 5. We proceed to study tree coloring properties, specifically those defined by freeness from a forbidden family of colored topological subtrees. We give constant query complexity algorithms for this problem, as well as a super constant lower bound for the case of freeness from a forbidden family of colored induced subtrees.

Then we introduce the notion of partial property testing, and the decomposition of a property into partially testable subproperties. A property P is P'-partially testable if there is a property tester that accepts inputs in P' and rejects inputs far from P. We show that there exists a property which is untestable, but has a decomposition into a few subproperties, for each it is partially testable. On the other hand we show that there exist untestable properties for which any decomposition into partially testable subproperties has an exponential number of sets. For this we develop new, entropy based techniques for proving property testing lower bounds. To complete the picture, we show that if we have a decomposition into a few subsets for which we have proximity oblivious testers then we can obtain a sublinear query complexity tester for the entire property. We do this by developing a ``universal tester'' and prove it tests such properties. This also resolves an open question regarding ``sample based testers'' posed by Goldreich and Ron.

Distribution testers are always non-adaptive, since all samples are obtained in the same manner and there is no place for an algorithmic decision. This is changed by introducing the model of distribution testing with conditional samples. In this model, the testing algorithm may obtain samples conditioned on any subset of the universe. This creates a much richer model, and in particular enables adaptive algorithms. We show that many problems are easier to test with conditional samples, such as uniformity, testing closeness to a known distribution, and any label invariant property of distributions. On the other hand, we show that there still exist problems in this model which require a linear number of samples. Finally, we also show a separation between adaptive and non-adaptive distribution testing algorithms with conditional samples.