TY - GEN

T1 - Testing surface area

AU - Kothari, Pravesh

AU - Nayyeri, Amir

AU - O'Donnell, Ryan

AU - Wu, Chenggang

PY - 2014

Y1 - 2014

N2 - We consider the problem of estimating the surface area of an unknown n-dimensional set F given membership oracle access. In contrast to previous work, we do not assume that F is convex, and in fact make no assumptions at all about F. By necessity this means that we work in the property testing model; we seek an algorithm which, given parameters A and e, satisfies: if surf(F) ≤ A then the algorithm accepts (whp); if F is not e-close to some set G with surf(G) ≤ KA, then the algorithm rejects (whp). We call k ≥ 1 the "approximation factor" of the testing algorithm. The n - 1 case (in which "surf(F) = 2m" means F is a disjoint union of to intervals) was introduced by Kearns and Ron [KR98], who solved the problem with k = 1/ε and O(1/ε) oracle queries. Later, Balcan et al. [BBBY12] solved it with with k = 1 and 0(l/ε4) queries. We give the first result for higher dimensions n. Perhaps surprisingly, our algorithm completely evades the "curse of dimensionality": for any n and any k > 4/π ≈ 1.27 we give a test that uses O( 1/ε) queries. For small n we have improved bounds. For n = 1 we can achieve k = 1 with O( 1/ε3.5) queries (slightly improving [BBBY12]), or any K > 1 with 0( 1/ε) queries (improving [KR98]). For n = 2,3 we obtain K ≈ 1.08,1.125 respectively, with 0( 1/ε) queries. Getting an arbitrary k > 1 for n > 1 remains an open problem.Finally, motivated by the learning results from [KOSO8], we extend our techniques to obtain a similar tester for Gaussian surface area for any n, with query complexity O( 1/ε) and any approximation factor k > 4/π ≈ 1.27.

AB - We consider the problem of estimating the surface area of an unknown n-dimensional set F given membership oracle access. In contrast to previous work, we do not assume that F is convex, and in fact make no assumptions at all about F. By necessity this means that we work in the property testing model; we seek an algorithm which, given parameters A and e, satisfies: if surf(F) ≤ A then the algorithm accepts (whp); if F is not e-close to some set G with surf(G) ≤ KA, then the algorithm rejects (whp). We call k ≥ 1 the "approximation factor" of the testing algorithm. The n - 1 case (in which "surf(F) = 2m" means F is a disjoint union of to intervals) was introduced by Kearns and Ron [KR98], who solved the problem with k = 1/ε and O(1/ε) oracle queries. Later, Balcan et al. [BBBY12] solved it with with k = 1 and 0(l/ε4) queries. We give the first result for higher dimensions n. Perhaps surprisingly, our algorithm completely evades the "curse of dimensionality": for any n and any k > 4/π ≈ 1.27 we give a test that uses O( 1/ε) queries. For small n we have improved bounds. For n = 1 we can achieve k = 1 with O( 1/ε3.5) queries (slightly improving [BBBY12]), or any K > 1 with 0( 1/ε) queries (improving [KR98]). For n = 2,3 we obtain K ≈ 1.08,1.125 respectively, with 0( 1/ε) queries. Getting an arbitrary k > 1 for n > 1 remains an open problem.Finally, motivated by the learning results from [KOSO8], we extend our techniques to obtain a similar tester for Gaussian surface area for any n, with query complexity O( 1/ε) and any approximation factor k > 4/π ≈ 1.27.

UR - http://www.scopus.com/inward/record.url?scp=84902108768&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84902108768&partnerID=8YFLogxK

U2 - 10.1137/1.9781611973402.89

DO - 10.1137/1.9781611973402.89

M3 - Conference contribution

AN - SCOPUS:84902108768

SN - 9781611973389

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 1204

EP - 1214

BT - Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014

PB - Association for Computing Machinery

T2 - 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014

Y2 - 5 January 2014 through 7 January 2014

ER -