Testing Surface Area

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 ∊, satisfies: if surf( F ) ≤ A then the algorithm accepts (whp); if F is not ∊-close to some set G with surf ( G ) ≤ κA, then the algorithm rejects (whp). We call κ ≥ 1 the “approximation factor” of the testing algorithm. The n = 1 case (in which “surf( F ) = 2 m ” means F is a disjoint union of m intervals) was introduced by Kearns and Ron [KR98], who solved the problem with κ = 1/∊ and O (1/∊) oracle queries. Later, Balcan et al. [BBBY12] solved it with with κ = 1 and O (1/∊ 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 κ > we give a test that uses O (1/∊) queries. For small n we have improved bounds. For n = 1 we can achieve κ = 1 with O (1/∊ 3. 5 ) queries (slightly improving [BBBY12]), or any κ > 1 with O (1/∊) queries (improving [KR98]). For n = 2, 3 we obtain κ ≈ 1. 08, 1. 125 respectively, with O (1/∊) queries. Getting an arbitrary κ > 1 for n > 1 remains an open problem.

Authors

• Pravesh K. Kothari
• Amir Nayyeri
• Ryan O'Donnell
• Chenggang Wu 0003

Keywords

No keywords are indexed for this paper.