Lower Bounds for Sums of Powers of Low Degree Univariates

DOI10.1007/978-3-662-47672-7_66zbMath1440.12002OpenAlexW2400227845MaRDI 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

Wronskianlower boundssums of powersarithmetic circuitsshifted derivatives

Mathematics Subject Classification ID

Polynomials in general fields (irreducibility, etc.) (12E05)

Related Items (5)

Sums of read-once formulas: how many summands are necessary? ⋮ On the linear independence of shifted powers ⋮ Lower bounds by Birkhoff interpolation ⋮ Sums of Read-Once Formulas: How Many Summands Suffice? ⋮ 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

This page was built for publication: Lower Bounds for Sums of Powers of Low Degree Univariates