*Algebraic Property Testing: The Role of Invariance*(with*Tali Kaufman*, ECCC TR07-111): In this work we considered properties of functions that formed a linear vector space over some field F, where the domain of the functions were of the form K^n where K was a (small) field extending F, and where the property was invariant under linear transformations of K^n. We gave necessary and sufficient conditions for such properties to be testable with constant queries (when K was of constant size). While the motivation for these families were low-degree polynomials, we showed not all properties here were low-degree polynomials and the degree did not characterize the locality of the test. Paper available here [1].*2-Transitivity is insufficient for Property Testing*(with*Elena Grigorescu*and*Tali Kaufmann*, ECCC TR08-033): In this work we used some of the functions explored in paper [1] above, but over large fields K, to get a counterexample to the AKKLR conjecture (this clearly shows that affine/linear-invariance is not just syntactic variations on polynomials, which were well0-understood by AKKLR). Paper available here [2].*Testing Linear-Invariant Non-Linear Properties*(with*Arnab Bhattacharyya*,*Victor Chen*, and*Ning Xie*, ECCC TR08-088): In this work we explored some properties that were not vector spaces (so functions that were not closed under addition), but still linear invariant. This led to a nice bridge between combinatorial property testing and algebraic property testing. Paper available here [3].*Succinct Representation of Codes with Applications to Testing*(with*Elena Grigorescu*and*Tali Kaufmann*, ECCC TR09-043): The paper [1] showed that if some properties were characterized by a*single*local constraint and its rotations under the group of affine transformations, then it was locally testable by the natural test. In this work we showed that many codes, including sparse affine-invariant codes over fields of the form 2^prime have this property. Paper available here [4].*Limits on the rate of locally testable affine-invariant codes*(with*Eli Ben-Sasson*, unpublished): In this work we show that (despite its richness) affine-invariance is not going to lead to much denser locally testable codes than already known. While the result is disappointing, if one cares about property testing beyond just the construction of locally testable codes, then this results adds to the body of knowledge on algebraic property testing.

- Shapira - STOC 2009
- Kaufman and Wigderson - ICS 2010
- Bhattacharyya, Kopparty, Schoenebeck, Sudan, and Zuckerman - ECCC TR09-086

Back to list of Oded's choices.