Polynomial-time computing over quadratic maps i: sampling in real algebraic sets
From MaRDI portal
Publication:1781114
DOI10.1007/s00037-005-0189-7zbMath1082.14065arXivcs/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
complexitysymbolic computationsemialgebraic setinfinitesimal deformationquadratic mapunivariate representation
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
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