Fall 2013

Testing Surface Area

Tuesday, Aug. 27, 2013 1:45 pm2:30 pm

Add to Calendar

We give an O(1/epsilon)-query property testing algorithm which distinguishes whether an unknown set has surface area at most A or (is epsilon-far from) surface area at least (4/pi) A. Our result works under n-dimensional Lebesgue measure or n-dimensional Gaussian measure. Previous work only treated the 1-dimensional case.