Speaker: |
Arnab Bhattacharyya (Indian Institute of Science Department of Computer Science and Automation Bangalore 560012) |

Organiser: |
Jaikumar Radhakrishnan |

Date: |
Monday, 11 Aug 2014, 10:00 to 11:00 |

Venue: |
D-405 (D-Block Seminar Room) |

(Scan to add to calendar)

In a sequence of developments stemming from Gowers' proof of Szemeredi's theorem, Green and Tao introduced a notion of regularity for a collection of polynomials. Variants of these ideas were famously used by Green and Tao to prove that the primes contain arbitrarily long arithmetic progressions. Over finite fields, the theory extends previously used concepts in theoretical computer science, such as low-biased random variables and Fourier analysis over finite fields.

In this talk, we will survey recent developments in the area, loosely termed "higher-order Fourier analysis". In joint work with Fischer, H. Hatami, P. Hatami, and Lovett, we developed certain bounds for exponential sums of polynomials [BFL13, BFH+13] that are useful in the area of property testing. These results used a non-constructive form of the regularity lemma. Subsequently, in joint work with P. Hatami and Tulsiani [BHT13], we devised an algorithmic regularity lemma for polynomials. This can be used [B14] to give new polynomial time algorithms for problems such as factoring low-degree multivariate 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$.