Talks
Fall 2013
![](https://old.simons.berkeley.edu/sites/default/files/styles/workshop_main/public/programs/images/real_analysis_green_0.jpg?itok=tRAYtSkn)
Testing for Affine Invariant Properties of Algebraic Functions
Thursday, August 29th, 2013, 9:00 am–9:45 am
Speaker:
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.
Attachment | Size |
---|---|
![]() | 1.07 MB |