Lower Bounds for Sums of Powers of Low Degree Univariates

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

zbMATH Keywords

Wronskian; lower bounds; sums of powers; arithmetic circuits; shifted derivatives

Mathematics Subject Classification ID

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