MPI-INF Logo
Campus Event Calendar

Event Entry

What and Who

Lower bounds for sums of powers of low degree univariates

Pascal Koiran
ENS Lyon
Talk
AG 1  
AG Audience
English

Date, Time and Location

Friday, 20 March 2015
11:00
60 Minutes
E2.1
001
Saarbrücken

Abstract

We consider the problem of representing a univariate polynomial f(x) as a sum of powers of low degree polynomials. We prove a lower bound of Ω((√d/t) for writing an explicit univariate degree d polynomial f(x) as a sum of powers of degree-t polynomials.


Joint work with Neeraj Kayal, Timothée Pecatte and Chandan Saha.

Contact

Karteek Sreenivasaiah
--email hidden
passcode not visible
logged in users only

Karteek Sreenivasaiah, 03/12/2015 13:46 -- Created document.