Lower bounds for polynomial evaluation and interpolation problems

DOI10.1007/BF01270384zbMath0895.68075MaRDI QIDQ1386175

Roman Smolensky, Victor Shoup

Publication date: 20 September 1998

Published in: Computational Complexity (Search for Journal in Brave)

zbMATH Keywords

polynomial evaluationarithmetic circuits

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Interpolation in approximation theory (41A05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Computing Frobenius maps and factoring polynomials ⋮ A nonlinear lower bound for constant depth arithmetical circuits via the discrete uncertainty principle ⋮ Hay from the haystack: explicit examples of exponential quantum circuit complexity ⋮ Improving \(3N\) circuit complexity lower bounds ⋮ Entropy of operators or why matrix multiplication is hard for depth-two circuits ⋮ A new method to obtain lower bounds for polynomial evaluation ⋮ Lower bounds for matrix factorization ⋮ A super-quadratic lower bound for depth four arithmetic circuits ⋮ On the rigidity of Vandermonde matrices ⋮ Lower bounds for matrix factorization ⋮ Efficient Construction of Rigid Matrices Using an NP Oracle ⋮ Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity

Cites Work

• A note on matrix rigidity
• Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten
• Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform
• Unnamed Item
• Unnamed Item
• Unnamed Item