Interpolation in Valiant's theory

DOI10.1007/s00037-011-0002-8zbMath1246.68120arXiv0710.0360OpenAlexW1970085887MaRDI QIDQ451113

Sylvain Perifel, Pascal Koiran

Publication date: 21 September 2012

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

Full work available at URL: https://arxiv.org/abs/0710.0360

zbMATH Keywords

interpolationcomputational complexitypolynomialsalgebraic complexityBlum-Shub-Smale modelValiant's model

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Dual VP classes ⋮ On the complexity of algebraic numbers, and the bit-complexity of straight-line programs1 ⋮ Towards a tight hardness-randomness connection between permanent and arithmetic circuit identity testing ⋮ Permanent Does Not Have Succinct Polynomial Size Arithmetic Circuits of Constant Depth ⋮ Weighted First-Order Model Counting in the Two-Variable Fragment With Counting Quantifiers ⋮ Monomials in arithmetic circuits: complete problems in the counting hierarchy

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On defining integers and proving arithmetic circuit lower bounds
• VPSPACE and a transfer theorem over the reals
• Turing machines that take advice
• VPSPACE and a transfer theorem over the complex field
• The complexity of combinatorial problems with succinct input representation
• Completeness and reduction in algebraic complexity theory
• The complexity of factors of multivariate polynomials
• On the complexity of computing determinants
• Valiant's model and the cost of computing integers
• On the intractability of Hilbert's Nullstellensatz and an algebraic version of ``\(NP\neq P\)?
• On the Complexity of Numerical Analysis
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• Valiant’s Model: From Exponential Sums to Exponential Products

This page was built for publication: Interpolation in Valiant's theory