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