Theory Seminar on 04/09: Testing Low Degree Ploynomials

From: Atri Rudra (atri@cs.washington.edu)
Date: Thu Apr 08 2004 - 00:10:25 PDT

  • Next message: Kelli McGee \(Kelly Services Inc\): "FW: 4-13-2004 - Khovanov Homology for Tangles and Cobordisms; Dror Bar-Natan, University of Toronto"

    Title: Testing low degree polynomials over prime fields
    Speaker: Atri Rudra
    Room: EE1 045
    Time: 11:30 am (Apr 9)

    Abstract
    --------

    Efficient low degree tests have been investigated in detail over the last
    decade or so, the interest stemming largely from their applications to
    PCPs and Reed Muller Codes. Tests for the case when the field size is
    greater than the degree being tested have been given in a series of work
    starting from the classic Blum-Luby-Rubinfeld linearity test. The case
    when the field size is smaller than then degree being tested has been
    open for some time. Alon et al in RANDOM 03 gave a test for GF(2). We
    extend their results to all prime fields.

    I will focus more on the background stuff (in particular the Alon et al
    paper) in this talk and conclude with a broad overview of the current
    work.

    This is joint work with Charanjit S. Jutla of IBM Watson Research Lab and
    Anindya C. Patthak & David Zuckerman of UT Austin.

    _______________________________________________
    Theory-talks mailing list
    Theory-talks@cs.washington.edu
    http://mailman.cs.washington.edu/mailman/listinfo/theory-talks
    _______________________________________________
    Theory-group mailing list
    Theory-group@cs.washington.edu
    http://mailman.cs.washington.edu/mailman/listinfo/theory-group

  • Next message: Kelli McGee \(Kelly Services Inc\): "FW: 4-13-2004 - Khovanov Homology for Tangles and Cobordisms; Dror Bar-Natan, University of Toronto"

    This archive was generated by hypermail 2.1.6 : Thu Apr 08 2004 - 00:10:51 PDT