-
Upload Video
videos in mp4/mov/flv
close
Upload video
Note: publisher must agree to add uploaded document -
Upload Slides
slides or other attachment
close
Upload Slides
Note: publisher must agree to add uploaded document -
Feedback
help us improve
close
Feedback
Please help us improve your experience by sending us a comment, question or concern
Please help transcribe this video using our simple transcription tool. You need to be logged in to do so.
Description
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.