Polynomial-time computing over quadratic maps i: sampling in real algebraic sets

DOI10.1007/s00037-005-0189-7zbMath1082.14065DBLPjournals/cc/GrigorievP05arXivcs/0403008OpenAlexW3100802811WikidataQ56874379 ScholiaQ56874379MaRDI QIDQ1781114

Dima Yu. Grigoriev, Dimitrii V. Pasechnik

Publication date: 16 June 2005

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

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

zbMATH Keywords

complexitysymbolic computationsemialgebraic setinfinitesimal deformationquadratic mapunivariate representation

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Semialgebraic sets and related spaces (14P10) Effectivity, complexity and computational aspects of algebraic geometry (14Q20)

Related Items (17)

On the reduction of multivariate quadratic systems to best rank-1 approximation of three-way tensors ⋮ When a system of real quadratic equations has a solution ⋮ On Obtaining the Convex Hull of Quadratic Inequalities via Aggregations ⋮ Bit complexity for multi-homogeneous polynomial system solving -- application to polynomial minimization ⋮ On the equivalence of two post-quantum cryptographic families ⋮ Geodesic diameter of sets defined by few quadratic equations and inequalities ⋮ Computing the top Betti numbers of semialgebraic sets defined by quadratic inequalities in polynomial time ⋮ A sharper estimate on the Betti numbers of sets defined by quadratic inequalities ⋮ Deciding Koopman's qualitative probability ⋮ On projections of semi-algebraic sets defined by few quadratic inequalities ⋮ Bounding the Betti numbers and computing the Euler-Poincaré characteristic of semi-algebraic sets defined by partly quadratic systems of polynomials ⋮ The inverse moment problem for convex polytopes ⋮ A Note on Polynomial Solvability of the CDT Problem ⋮ A Two-Variable Approach to the Two-Trust-Region Subproblem ⋮ Computing the Betti numbers of semi-algebraic sets defined by partly quadratic systems of polynomials ⋮ An Evolutionary Approach to the Automatic Classification of Automorphisms of Lower-Dimensional Lie Algebras ⋮ Narrowing the difficulty gap for the Celis-Dennis-Tapia problem

This page was built for publication: Polynomial-time computing over quadratic maps i: sampling in real algebraic sets