BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Isaac Newton Institute Seminar Series
SUMMARY:Correlation testing for affine invariant propertie
s on F_p^n - Lovett\, S (IAS Princeton)
DTSTART;TZID=Europe/London:20110504T140000
DTEND;TZID=Europe/London:20110504T150000
UID:TALK31118AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/31118
DESCRIPTION:Recently there has been much interest in Gowers un
iformity norms from the perspective of theoretical
computer science. This is mainly due to the fact
that these norms provide a method for testing whet
her the maximum correlation of a function $f:F_p^n
\nightarrow F_p$ with polynomials of degree at mo
st $d le p$ is non-negligible\, while making only
a constant number of queries to the function. This
is an instance of {m correlation testing}. In th
is framework\, a fixed test is applied to a functi
on\, and the acceptance probability of the test is
dependent on the correlation of the function from
the property. This is an analog of {m proximity
oblivious testing}\, a notion coined by Goldreich
and Ron\, in the high error regime.\n\nIn this wor
k\, we study general properties which are affine i
nvariant and which are correlation testable using
a constant number of queries. We show that any suc
h property (as long as the field size is not too s
mall) can in fact be tested by Gowers uniformity t
ests\, and hence having correlation with the prope
rty is equivalent to having correlation with degre
e $d$ polynomials for some fixed $d$. We stress th
at our result holds also for non-linear properties
which are affine invariant. This completely class
ifies affine invariant properties which are correl
ation testable.\n\nThe proof is based on higher-or
der Fourier analysis. Another ingredient is an ext
ension of a graph theoretical theorem of Erd"os\,
Lov'asz and Spencer to the context of additive num
ber theory.\n\nJoint work with Hamed Hatami.\n\n
LOCATION:Seminar Room 1\, Newton Institute
CONTACT:Mustapha Amrani
END:VEVENT
END:VCALENDAR