Smoothed analysis for the condition number of structured real polynomial systems
From MaRDI portal
Publication:4999472
DOI10.1090/mcom/3647zbMath1482.14062arXiv1809.03626OpenAlexW3162324574MaRDI QIDQ4999472
J. Maurice Rojas, Alperen Ali Ergur, Grigoris Paouris
Publication date: 7 July 2021
Published in: Mathematics of Computation (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1809.03626
Numerical computation of matrix norms, conditioning, scaling (65F35) Complexity and performance of numerical algorithms (65Y20) Real algebraic and real-analytic geometry (14P99) Geometric aspects of numerical algebraic geometry (14Q65)
Related Items (3)
Functional norms, condition numbers and numerical algorithms in algebraic geometry ⋮ On the complexity of the Plantinga-Vegter algorithm ⋮ A polyhedral homotopy algorithm for real zeros
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- On sharp bounds for marginal densities of product measures
- A numerical algorithm for zero counting. III: Randomization and condition
- Computing the homology of real projective sets
- Two observations regarding embedding subsets of Euclidean spaces in normed spaces
- A numerical algorithm for zero counting. I: Complexity and accuracy
- Mathematical problems for the next century
- A deterministic algorithm to compute approximate roots of polynomial systems in polynomial average time
- Probabilistic condition number estimates for real polynomial systems. I: A broader family of distributions
- Approximate zeros and condition numbers
- Computing the homology of semialgebraic sets. I: Lax formulas
- Randomized isoperimetric inequalities
- A numerical algorithm for zero counting. II: Distance to ill-posedness and smoothed analysis
- The Littlewood-Offord problem and invertibility of random matrices
- Tail bounds via generic chaining
- Empirical processes and random projections
- On a condition number of general random polynomial systems
- Condition
- Smale’s 17th problem: Average polynomial time to compute affine and projective solutions
- Small Ball Probabilities for Linear Images of High-Dimensional Distributions
- Smallest singular value of a random rectangular matrix
- Complexity of Bezout's Theorem I: Geometric Aspects
- Computing the Homology of Basic Semialgebraic Sets in Weak Exponential Time
- High-Dimensional Probability
- The Mathematics of Data
- The Generic Chaining
- Plantinga-Vegter Algorithm takes Average Polynomial Time
- A Simple Tool for Bounding the Deviation of Random Matrices on Geometric Sets
- Probability Inequalities for Sums of Bounded Random Variables
This page was built for publication: Smoothed analysis for the condition number of structured real polynomial systems
