Lower Bounds for Sums of Powers of Low Degree Univariates
From MaRDI portal
Publication:3448839
DOI10.1007/978-3-662-47672-7_66zbMath1440.12002MaRDI QIDQ3448839
Chandan Saha, Timothée Pecatte, Neeraj Kayal, Pascal Koiran
Publication date: 27 October 2015
Published in: Automata, Languages, and Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-662-47672-7_66
12E05: Polynomials in general fields (irreducibility, etc.)
Related Items
Sums of Read-Once Formulas: How Many Summands Suffice?, Lower bounds by Birkhoff interpolation, Sums of read-once formulas: how many summands are necessary?, On the linear independence of shifted powers, Reconstruction algorithms for sums of affine powers
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Arithmetic circuits: the chasm at depth four gets wider
- A Wronskian approach to the real \(\tau\)-conjecture
- Non-commutative arithmetic circuits: depth reduction and size lower bounds
- On maximum, typical and generic ranks
- Arithmetic Circuits: A Chasm at Depth 3
- Improved Bounds for Reduction to Depth 4 and Depth 3
- An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas
- Fast Parallel Computation of Polynomials Using Few Processors
- On the Waring problem for polynomial rings
- Lower bounds for depth 4 formulas computing iterated matrix multiplication
- The limits of depth reduction for arithmetic formulas
- A super-polynomial lower bound for regular arithmetic formulas
- Approaching the Chasm at Depth Four