Fall 2013

Testing for Affine Invariant Properties of Algebraic Functions

Thursday, August 29th, 2013 9:00 am9:45 am

Add to Calendar

Let F be a prime field. An affine-invariant property is a property of functions on F^n that is closed under taking affine transformations of the domain. We prove that every affine-invariant property with a local characterization is testable. In fact, we show that for any such property, there is a test that, given an input function, makes a constant number of queries, always accepts if it satisfies the property, and otherwise rejects with a positive probability depending only on the distance of the function from the property.