# Randomization, Relaxation, and Complexity in Polynomial Equation Solving

Share this page *Edited by *
*Leonid Gurvits; Philippe Pébay; J. Maurice Rojas; David Thompson*

This volume corresponds to the Banff
International Research Station Workshop on Randomization, Relaxation,
and Complexity, held from February 28–March 5, 2010 in Banff,
Alberta, Canada.

This volume contains a sample of advanced algorithmic techniques
underpinning the solution of systems of polynomial equations. The
papers are written by leading experts in algorithmic algebraic
geometry and touch upon core topics such as homotopy methods for
approximating complex solutions, robust floating point methods for
clusters of roots, and speed-ups for counting real solutions. Vital
related topics such as circuit complexity, random polynomials over
local fields, tropical geometry, and the theory of fewnomials,
amoebae, and coamoebae are treated as well. Recent advances on Smale's
17th Problem, which deals with numerical algorithms that approximate a
single complex solution in average-case polynomial time, are also
surveyed.

# Table of Contents

## Randomization, Relaxation, and Complexity in Polynomial Equation Solving

- Contents v6 free
- Preface vii8 free
- Multivariate Ultrametric Root Counting 110 free
- A Parallel Endgame 2534
- Efficient Polynomial System Solving by Numerical Methods 3746
- Symmetric Determinantal Representation of Formulas and Weakly Skew Circuits 6170
- Mixed Volume Computation in Solving Polynomial Systems 97106
- A Search for an Optimal Start System for Numerical Homotopy Continuation 113122
- Complex Tropical Localization, and Coamoebas of Complex Algebraic Hypersurfaces 127136
- 1. Introduction 127136
- 2. Preliminaries 129138
- 3. Complex tropical hypersurfaces with a simplex Newton polytope 131140
- 4. Tropical mirror hypersurfaces 132141
- 5. Coamoebas of complex tropical hypersurfaces 136145
- 6. Coamoebas of complex algebraic hypersurfaces 139148
- 7. Examples of complex algebraic plane curves coamoebas 141150
- References 143152

- Randomization, Sums of Squares, Near-Circuits, and Faster Real Root Counting 145154
- Dense Fewnomials 167176
- The Numerical Greatest Common Divisor of Univariate Polynomials 187196