Events

CIS SIGTheory

Andrew Arnold, U Waterloo

A recursive, Las Vegas algorithm for the interpolation of sparse polynomials given by straight-line programs

Abstract:
We present a recursive algorithm to interpolate a t-sparse univariate polynomial of degree d given by a straight-line program. We show, in addition, how this algorithm may be used to interpolate black-box polynomials with real or complex-valued coefficients using soft-O( t log^3 d) probes. This work builds on ideas from previous algorithms by Garg and Schost, and by Giesbrecht and Roche.

Monday, January 21, 2013 at 2:00pm to 3:00pm

Smith Hall, Room 426
Smith Hall, University of Delaware, Newark, DE 19716, USA

Event Type

Lectures & Programs, Students, College of Engineering, Academics, Lectures and Programs, Community

Calendar

Group

ENGR - Computer & Information Sciences

Hashtag

#cis_sigtheory_2814

Contact Email

saunders@udel.edu

Contact Name

Dr. David Saunders

Contact Phone

302-831-6238

Subscribe

Recent Activity