Ph.D Thesis

Ph.D StudentRozenberg Eyal
SubjectLower Bounds and Structural Results in
Property Testing of Dense Combinatorial Structures
DepartmentDepartment of Computer Science
Supervisor ASSOCIATE PROF. Eldar Fischer
Full Thesis textFull thesis text - English Version


We study the dense model for testing properties of combinatorial structures such as graphs, hypergraphs, matrices and tensors. We develop several structural concepts regarding testing in this model, and use them to improve or formulate lower bounds on testing query complexity and to achieving hierarchy results including also upper bounds.

We first consider "natural" tests, which act entirely independently of the size of their input. We develop a technique for making any test natural, for properties which are almost hereditary and almost "inflatable" - closed under taking blowup. We apply this technique to derive several results regarding testing hereditary properties and triangle-freeness in particular. We explore the relations of the notion of inflatability with other features of properties and property tests in the dense graph model, such as one-sidedness, heredity, and proximity-oblivion. Finally, we generalize these results to dense structures other than graphs.

From natural testing we turn to tests are highly-dependent on the size of their input graph: We construct a property of dense graphs with maximal query complexity, but which can be efficiently decided, and whose test is time-efficient. Using this and other established constructions we prove several hierarchy theorems for the dense graph model, establishing that for every possible reasonable function of the input graph size, there exists properties with exactly this function as its query complexity --- and with certain desirable features: a time-efficient test. We prove a similar hierarchy theorem both for testing generic functions and graphs in the sparse testing model.

We next present several results regarding structures which are essentially different than general graphs.

We derive lower bounds for testing colored bipartite graphs and k-partite k-uniform hypergraphs (unordered matrices and tensors over fixed finite fields), refuting the possibility of extending a previous positive result regarding (two-colored) bipartite graphs. Two final results regard testing general multicolored hypergraphs, which are characterized by partitions of vertex tuples and density constraints. We show that such properties can be efficiently `pseudo-tested': one can distinguish whether there exist partitions which approximately satisfy the constraints. However, this 'pseudo-testing', is insufficient for an actual test: we demonstrate this by proving a lower bound on the query complexity of such hypergraph properties.