Testing surface area with arbitrary accuracy

Recently, Kothari et al. gave an algorithm for testing the surface area of an arbitrary set A ⊂ [0,1] n . Specifically, they gave a randomized algorithm such that if A 's surface area is less than S then the algorithm will accept with high probability, and if the algorithm accepts with high probability then there is some perturbation of A with surface area at most κ n S . Here, κ n is a dimension-dependent constant which is strictly larger than 1 if n ≥ 2, and grows to 4/ π as n → ∞.

Authors

• Joe Neeman

Keywords

• noise sensitivity
• property testing
• surface area