
Upload Video
videos in mp4/mov/flv
close
Upload video
Note: publisher must agree to add uploaded document 
Upload Slides
slides or other attachment
close
Upload Slides
Note: publisher must agree to add uploaded document 
Feedback
help us improve
close
Feedback
Please help us improve your experience by sending us a comment, question or concern
Description
Our proof works by induction on $n$ and yields a new analysis of even the classical BlumLubyRubinfeld~cite{BLR} linearity test, for the setting of functions mapping $F_2^n$ to $F_2$. The optimality follows from a tighter analysis of counterexamples to the ``inverse conjecture for the Gowers norm'' constructed by cite{GT07,LMS}.
Our result has several implications. First, it shows that the Gowers norm test is tolerant, in that it also accepts close codewords. Second, it improves the parameters of an XOR lemma for polynomials given by Viola and Wigderson~cite{VW}. Third, it implies a ``query hierarchy'' result for property testing of affineinvariant properties. That is, for every function $q(n)$, it gives an affineinvariant property that is testable with $O(q(n))$queries, but not with $o(q(n))$queries, complementing an analogous result of cite{GKNR08} for graph properties.