Please help transcribe this video using our simple transcription tool. You need to be logged in to do so.


We initiate the study of testing properties of images that correspond to {em sparse/} $0/1$-valued matrices of size $n imes n$. Our study is related to but different from the study initiated by Raskhodnikova ({em Proceedings of RANDOM, 2003/}), where the images correspond to {em 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.

Questions and Answers

You need to be logged in to be able to post here.