L p -testing
Piotr Berman, Sofya Raskhodnikova, Grigory Yaroslavtsev · 2014
We initiate a systematic study of sublinear algorithms for approximately testing properties of real-valued data with respect to Lp distances for p = 1, 2. Such algorithms distinguish datasets which either have (or are close to having) a certain property from datasets which are far from having it with respect to Lp distance. For applications involving noisy real-valued data, using Lp distances allows algorithms to withstand noise of bounded Lp norm. While the classical property testing framework developed with respect to Hamming distance has been studied extensively, testing with respect to Lp distances has received little attention.