AG 1, AG 2, AG 3, AG 4, AG 5, SWS, RG1, MMCI   Info

Public Audience

English

120 Minutes

Saarbrücken

We present a deterministic algorithm to interpolate an m-sparse n-variate polynomial which uses poly(n,m,log H,log d) bit operations. Our algorithm works over the integers. Here H is a bound on the magnitude of the coefficient values of the given polynomial. This running time is polynomial in the output size. Our algorithm only requires black box access to the given polynomial, albeit in a special form. To our knowledge, this is the first algorithm in which number of bit operations have logarithmic dependence on the degree. As an easy consequence, we obtain an algorithm to interpolate polynomials represented by arithmetic circuits.

Aaron Alsancak

068193251800

--email hidden

passcode not visible

logged in users only