Algorithms and Complexity Seminar
Testing Properties of Sparse Images
Gilad Tsur (Tel-Aviv University)
We initiate the study of testing properties of images that
correspond to sparse 0/1-valued matrices of size n x n.
Our study is related to but different from the study initiated by
Raskhodnikova (Proceedings of RANDOM, 2003), where the images
correspond to dense 0/1-valued matrices. Specifically,
while distance between images in the model studied by
Raskhodnikova is the fraction of entries
on which the images differ taken with respect to
all n^2 entries, the distance measure in our model is defined by
the fraction of such entries taken with respect to the
actual number of 1's in the matrix.
We study several natural properties: connectivity, convexity, monotonicity,
and being a line. In all cases we give testing algorithms
with sublinear complexity, and in some of the cases we also provide
corresponding lower bounds.
Joint work with Dana Ron.