Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Waring Problem:
TR12-081 | 26th June 2012
Neeraj Kayal

An exponential lower bound for the sum of powers of bounded degree polynomials

Revisions: 1

In this work we consider representations of multivariate polynomials in $F[x]$ of the form $ f(x) = Q_1(x)^{e_1} + Q_2(x)^{e_2} + ... + Q_s(x)^{e_s},$ where the $e_i$'s are positive integers and the $Q_i$'s are arbitary multivariate polynomials of bounded degree. We give an explicit $n$-variate polynomial $f$ of degree $n$ ... more >>>

TR17-162 | 26th October 2017
Klim Efremenko, Ankit Garg, Rafael Mendes de Oliveira, Avi Wigderson

Barriers for Rank Methods in Arithmetic Complexity

Arithmetic complexity, the study of the cost of computing polynomials via additions and multiplications, is considered (for many good reasons) simpler to understand than Boolean complexity, namely computing Boolean functions via logical gates. And indeed, we seem to have significantly more lower bound techniques and results in arithmetic complexity than ... more >>>

ISSN 1433-8092 | Imprint