Advertisement
Published in:
2015 | OriginalPaper | Chapter
Lower Bounds for Sums of Powers of Low Degree Univariates
Authors : Neeraj Kayal, Pascal Koiran, Timothée Pecatte, Chandan Saha
Published in: Automata, Languages, and Programming
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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
$$\Omega \left( \sqrt{\frac{d}{t}} \right) $$
Ω
d
t
for writing an explicit univariate degree-
d
polynomial
f
(
x
) as a sum of powers of degree-
t
polynomials.