Algorithmic Regularity for Polynomials and Applications

Speaker: Arnab Bhattacharyya

Date: Friday, December 13, 2013

Time: 1:30 PM to 2:30 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: G882

Event Type:

Room Description:

Host: Prof. Ronitt Rubinfeld

Contact: Joanne Talbot Hanley, 3-6054, joanne@csail.mit.edu

Relevant URL:

Speaker URL: None

Speaker Photo:
None

Reminders to: theory-seminars@csail.mit.edu, seminars@csail.mit.edu, compalgsem@csail.mit.edu, seminars@csail.mit.edu, compalgsem@csail.mit.edu

Reminder Subject: TALK: Algorithms and Complexity Seminar: Arnab Bhattacharyya "Algorithmic regularity for polynomials and applications"

In analogy with the regularity lemma of Szemerédi, regularity lemmas for polynomials given by Green and Tao and Kaufman and Lovett give a way of modifying a collection of polynomials F={P1,...,Pm} to a new collection F?, so that the polynomials in F? are “pseudorandom”. These lemmas have various applications, such as (special cases) of Reed-Muller testing and worst-case to average-case reductions for polynomials. However, the transformation from F to F? is not algorithmic for either regularity lemma. We define new notions of regularity for polynomials, which are analogous to the above, but which allow for an efficient algorithm to compute the pseudorandom collection F?. In particular, when the field is of high characteristic, we can refine F into F? where every nonzero linear combination of polynomials in F? has desirably small Gowers norm.

Using the algorithmic regularity lemmas, we show that if a polynomial P of degree d is within (normalized) Hamming distance 1?1/p?? of some unknown polynomial of degree k over a prime field of order p (for k

Research Areas:

Impact Areas:

See other events that are part of the Algorithms and Complexity Series Fall 2013 / Spring 2014.

Created by Joanne Talbot Hanley at Wednesday, December 04, 2013 at 1:08 PM.