BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/527
DTSTAMP:20230914T125928Z
SUMMARY:Higher-order Fourier Analysis and Applications
DESCRIPTION:Speaker: Arnab Bhattacharyya (Indian Institute of Science\nDepa
rtment of Computer Science and Automation\nBangalore 560012)\n\nAbstract:
\nAbstract: Regularity is a notion of “pseudorandomness” that allows o
ne to decompose a given object into a collection of simpler objects which
appear random according to certain statistics. The famous regularity lemma
of Szemeredi [Sze75\, Sze78] says that any dense graph can be partitioned
into a collection of bounded number of “pseudorandom” bipartite graph
s. The Szemeredi regularity lemma has numerous applications in combinatori
cs and property testing.\nIn a sequence of developments stemming from Gowe
rs' proof of Szemeredi's theorem\, Green and Tao introduced a notion of re
gularity for a collection of polynomials. Variants of these ideas were fam
ously used by Green and Tao to prove that the primes contain arbitrarily l
ong arithmetic progressions. Over finite fields\, the theory extends previ
ously used concepts in theoretical computer science\, such as low-biased r
andom variables and Fourier analysis over finite fields.\nIn this talk\, w
e will survey recent developments in the area\, loosely termed "higher-ord
er Fourier analysis". In joint work with Fischer\, H. Hatami\, P. Hatami\,
and Lovett\, we developed certain bounds for exponential sums of polynomi
als [BFL13\, BFH+13] that are useful in the area of property testing. Thes
e results used a non-constructive form of the regularity lemma. Subsequent
ly\, in joint work with P. Hatami and Tulsiani [BHT13]\, we devised an alg
orithmic regularity lemma for polynomials. This can be used [B14] to give
new polynomial time algorithms for problems such as factoring low-degree m
ultivariate polynomials over prime order fields and deciding\, for fixed $
p\, d$ and $r$\, whether a given d-dimensional tensor over $F_p$ has rank
at most $r$.\n
URL:https://www.tcs.tifr.res.in/web/events/527
DTSTART;TZID=Asia/Kolkata:20140811T100000
DTEND;TZID=Asia/Kolkata:20140811T110000
LOCATION:D-405 (D-Block Seminar Room)
END:VEVENT
END:VCALENDAR