Home › Conference Program

Sparse Polynomial Interpolation

  • warning: Parameter 1 to drutex_pdf_nodeapi() expected to be a reference, value given in /irmacs/drupal/drupal-6x/sites/jonfest2011.irmacs.sfu.ca/modules/drutex/drutex.module on line 829.
  • warning: Parameter 1 to drutex_pdf_nodeapi() expected to be a reference, value given in /irmacs/drupal/drupal-6x/sites/jonfest2011.irmacs.sfu.ca/modules/drutex/drutex.module on line 829.
  • warning: Parameter 1 to drutex_pdf_nodeapi() expected to be a reference, value given in /irmacs/drupal/drupal-6x/sites/jonfest2011.irmacs.sfu.ca/modules/drutex/drutex.module on line 829.
  • The directory /tmp/drutex-636729f7727faf92a6922be0a3a9c01f-1 has been created.
  • The directory /tmp/drutex-636729f7727faf92a6922be0a3a9c01f-2 has been created.
  • The directory /tmp/drutex-636729f7727faf92a6922be0a3a9c01f-3 has been created.
  • The directory /tmp/drutex-636729f7727faf92a6922be0a3a9c01f-4 has been created.
  • The directory /tmp/drutex-636729f7727faf92a6922be0a3a9c01f-5 has been created.
  • The directory /tmp/drutex-636729f7727faf92a6922be0a3a9c01f-6 has been created.
  • The directory /tmp/drutex-636729f7727faf92a6922be0a3a9c01f-7 has been created.
  • The directory /tmp/drutex-636729f7727faf92a6922be0a3a9c01f-8 has been created.
  • The directory /tmp/drutex-636729f7727faf92a6922be0a3a9c01f-9 has been created.
  • The directory /tmp/drutex-636729f7727faf92a6922be0a3a9c01f-10 has been created.
  • The directory /tmp/drutex-636729f7727faf92a6922be0a3a9c01f-11 has been created.
  • The directory /tmp/drutex-636729f7727faf92a6922be0a3a9c01f-12 has been created.
  • The directory /tmp/drutex-636729f7727faf92a6922be0a3a9c01f-13 has been created.
  • The directory /tmp/drutex-636729f7727faf92a6922be0a3a9c01f-14 has been created.
  • The directory /tmp/drutex-636729f7727faf92a6922be0a3a9c01f-15 has been created.
Speaker: 

Monagan, Michael

Affiliation: 
Simon Fraser University

Abstract

We consider the problem of interpolating a sparse multivariate polynomial
TeX Embedding failed! of degree TeX Embedding failed! with TeX Embedding failed! non-zero terms over a ring.
Newton interpolation needs TeX Embedding failed! points to interpolate TeX Embedding failed! which is
exponential in TeX Embedding failed!. Our goal is an algorithm whose time complexity
is polynomial in TeX Embedding failed!, TeX Embedding failed! and TeX Embedding failed!. Our motivation is polynomial GCD computation.
Here one normally works modulo a prime TeX Embedding failed! and hence interpolates
over the ring of integers modulo TeX Embedding failed!.

In the talk we will present Ben-Or and Tiwari's algorithm from 1988 for
interpolation over the integers. Many authors have tried to modify
this algorithm to interpolate over finite fields. We present one beautiful
modification by Huang and Rao and then our own attempt which we have
implemented and parallelized. Currently we are trying another approach
which assumes the characteristic TeX Embedding failed! is TeX Embedding failed! and also that TeX Embedding failed! is "smooth" so
that discrete logarithms in TeX Embedding failed! are efficient.

Video: 

Details

Date & Time: 
Thursday, May 19, 2011 - 14:45 - 15:15
Venue/Room: 
ASB 10900