Randomization, Relaxation, and Complexity (10w5119)

Objectives

In applications from ranging from string theory [DSZ04] to control
theory to phylogenetics, the need for ultra-fast equation solving algorithms
--- beyond the limits of computational algebra --- continues to grow.
Computational algebra has, in the past two decades, found the
asymptotic complexity limits of deterministic algorithms for polynomial
system solving (see, e.g., [Roj07] and the references therein). To surpass
present complexity barriers, it is thus clear that a new perspective
for algorithmic real algebraic geometry is necessary. Randomization and
relaxation stand as two of the most promising new sources for
fast algorithms, and this workshop aims to unite the diverse group of
researchers who can most rapidly advance and unite such tools.

To illustrate some background, let us begin with the feasibility
problem: Given polynomials $f_1,...,f_k$ in $Z[x_1,...,x_n]$, and a ring $K$
containing the integers, what is the complexity of deciding whether the
system of equations $f_1=cdots=f_n=0$ has a root in $K^n$? We call this
problem $FEAS_K$, and we will focus on the special case $Kin{mathbb{R},
mathbb{C}}$: real and complex feasibility. It is worth
noting that $FEAS_Z$ is undecidable (thanks to famous work of
Davis, Putnam, Robinson, and Matiyasevich in the 1970s), and that the
decidability of $FEAS_R$ was first proved by Tarski around 1939 (without a
realistic complexity bound).

While modern algorithmic algebraic geometry has since given us powerful
tools for computing invariants such as sheaf cohomology of algebraic
sets, it is important to observe that a full, complexity-theoretic
understanding of the basic problems $FEAS_C$ and $FEAS_R$ is still nascent. This
is particularly vexing, since one must understand feasibility
before settling harder problems such as counting or approximating real
solutions, and the latter problems are centrally important in industrial
applications. Note also that the main algorithms in real
algebraic geometry (such as those behind quantifier elimination [BPR07]) are
still heavily based on the same tools as those for complex algebraic geometry:
Grobner bases, homotopy-based methods, and resultants. Powerful as
these tools may be, recent quantitative results (such as those from
Fewnomial Theory [Kho91,LRW03,BRS07,DRRS07]) indicate that the true algorithmic
complexity of real algebraic sets may be far lower than that of complex
algebraic sets.

From different points of view, this complexity gap has been
begun to be addressed by, among others, the organizers of this proposed
workshop. For instance, if one considers the special case of $FEAS_R$
with input a single $n$-variate polynomial with exactly $m$ monomial terms,
Rojas (in joint work with Bihan and Stella [BRS07]) has recently given a sharp
complexity threshold between P and NP-hardness, as a function of $(n,m)$.
Combined with earlier joint work of Rojas and Ye [RY05], and recent results on
real discriminant complements [DRRS07], this suggests that deterministic
algorithms for $FEAS_R$ will likely not admit any sub-exponential speed-ups.

Enter randomization and approximation. Smale's 17th Problem
suggest a natural method to maintain polynomial-time complexity for
high-dimensional equation solving: Specifically, Smale asked whether one can
find a single approximate (complex) root of a random polynomial system, in
polynomial time, on average. (The notion of approximate root has a precise
definition that allows an elegant unification of approximation and
bit-complexity [BCSS98].) This question is particularly natural from the point
of view of numerical conditioning, which began with early 20th century work of
Turing and Wilkinson in numerical linear algebra, and has since been extended
to general nonlinear problems via the work of Cucker, Smale, and other authors
(see, e.g., [CS99]). Indeed, it has been observed in recent years that random
sparse polynomial systems exhibit
excellent quantitative and algorithmic behavior on average [Roj96,MR04,SZ04,
BCL06,AR07]. More recently, Beltran and Pardo made a significant advance
by providing a positive answer to Smale's 17th Problem [BP08a,BP08b]. The
clarification and refinement of this theory in the context of real
solutions is one of the primary focusses of this workshop.

An approach that fits into the paradigm of approximation is
the notion of relaxation. For example, in the Ph.D. thesis of one of
the organizers (Parrilo), it was shown that one can use semidefinite
programming to efficiently approximate the minima of certain nonnegative
multivariate polynomials. In particular, this method is provably fast for
polynomials that are sums of squares (SOS), and thus quantitative results for
SOS polynomials can be translated into quantitative results for the complexity
of $FEAS_R$ in certain cases. More recently, independent work of Blekherman,
Nie, and Sethuraman has clarified how often one can expect to use
semidefinite programming to efficiently solve equations over the
real numbers. Extending this to general polynomials can
then be accomplished, at least in principle, by constructing a deformation of
one's input polynomials to SOS polynomials --- a technique known as
semidefinite programming relaxation. In a complementary direction, recent
advances in the theory of hyperbolic polynomials, due to Gurvits, have
provided an attractive generalization and unification of efficient randomized
approximation schemes for hard combinatorial problems. (See also
his work on conjectures of van der Waerden and Valiant-Schrijver [Gur06].)

However, despite their practical success in certain applications
[Las01,Par03,Ren06,Gur06], the algorithmic complexity of these methods
is still not yet fully understood, particularly for sparse polynomial systems.
Furthermore, it is important to remember that if we are to achieve practical
speed-ups for polynomial system solving beyond what is attainable in symbolic
algebra, we must respect the underlying notions of numerical conditioning and
probability of success [MR04]. In particular, the smoothed complexity
[ST02,BCL06] of the methods we have mentioned is an open problem we can
realistically hope to solve through this workshop.

We are thus interested in strengthening and solidifying the emerging
connections between algorithmic complexity, real algebraic geometry, and
advanced numerical methods. In closing, let also point out that this workshop
unites, and strives to extend considerably, the theories underlying earlier
successful workshops at various institutions: In particular,

``Complexity, Coding, and Communication'' (at IMA, co-organized
by Burgisser, Rojas, Rosenthal, and Sudan)
``Random Analytic Surfaces"
(at AIM, co-organized by Dembo, Rojas, Shiffman, and Zelditch),
``Theory and Algorithms of Linear Matrix Inequalities"
(at AIM co-organized by Helton, Parrilo, and Putinar),
``Positive Polynomials and Optimization''
(at BIRS, co-organized by Kuhlmann, Lall, Powers, and Sottile)
Well before the workshop, the organizers will solicit, and later
select and refine, open problems from the participants. The talks will
then begin with background and overview, so everyone can speak the same
language. The focus will then be on a distillation of the contributed
problems.

Bibliography

[AR08] Avenda~no, Mart'in and Rojas, J. Maurice,
{it ``A Critical Radius for Low Complexity,''} in progress.

[BP08a] Beltr'an, Carlos and Pardo, Luis M., {it "On Smale's
17th Problem: A Probabilistic Positive Answer,''} Foundations of
Computational Mathematics, no. 1, pp. 1--43.

[BP08b] Beltr'an, Carlos and Pardo, Luis Miguel, {it ``Smale's 17$thth$:
Average Polynomial Time to Compute Affine and Projective Solutions,''}
J. AMS, to appear.

[BCSS98]{bcss} Blum, Lenore; Cucker, Felipe; Shub, Mike; and
Smale, Steve, {it Complexity and Real Computation,} Springer-Verlag, 1998.

[BCL06] Burgisser, P.; Cucker, F., and Lotz, M., {it ``General
Formulas for the Smoothed Analysis of Condition Numbers,''}
C. R. Acad. Sci. Paris, Ser. I 343, pp. 145--150 (2006).

[BRS08] Bihan, Frederic; Rojas, J. Maurice; Stella, Casey;
``First Steps in Algorithmic Real Fewnomial Theory,'' submitted for
publication, also downloadable from
http://www.math.tamu.edu/~{}rojas/list2.html

[BPR06] Basu, Saugata; Pollack, Ricky; and Roy, Marie-Francoise,
{it Algorithms in Real Algebraic Geometry,} Algorithms and Computation
in Mathematics Series (A. M. Cohen, H. Cohen, D. Eisenbud, M. F. Singer,
B. Sturmfels, eds.), vol. 10 (2nd ed.), Springer-Verlag, 2006.

[CS99] Cucker, Felipe and Smale, Steve, {it ``Complexity estimates depending
on condition and round-off error,''}
J. ACM 46 (1999), no. 1, pp. 113--184.

[DRRS07] Dickenstein, Alicia; Rojas, J. Maurice; Rusek, Korben;
Shih, Justin, ``Extremal Real Algebraic Geometry and $A$-discriminants,''
Moscow Mathematical Journal, vol. 7, no. 3, July-September 2007, pp. 425-452.

[DSZ04] Douglas, Michael R.; Shiffman, Bernard; and Steve
Zelditch, ``Critical points and supersymmetric vacua,''}
to appear in Dyson issue of Comm. Math. Phys. (math.CV/0402326).

[Gur06] Gurvits, Leonid, {it ``Hyperbolic polynomials approach to Van der
Waerden/Schrijver-Valiant like conjectures: sharper bounds, simpler
proofs and algorithmic applications,''} Proceedings STOC 2006,
ACM Press.

[Las01] Lasserre, J.-B., {it ``Global optimization with polynomials and the
problem of moments,''} {em SIAM J. Optim.}, 11(3):796--817, 2001.

[LRW03] Li, Tien-Yien; Rojas, J. Maurice; and Wang,
Xiaoshen, ``Counting Real Connected Components of Trinomials Curve
Intersections and m-nomial Hypersurfaces,'' Discrete and
Computational Geometry, 30 (2003), no. 3, pp. 379--414.

[MR04] Malajovich, Gregorio and Rojas, J. Maurice,
``High Probability Analysis of the Condition Number of Sparse
Polynomial Systems,'' Theoretical Computer Science, special issue on
algebraic and numerical algorithms, Vol. 315, no. 2--3 (May 6,
2004), pp. 525--555.

[Par03] Parrilo, Pablo,
{it ``Semidefinite programming relaxations for semialgebraic problems,''}
Mathematical Programming Ser. B, Vol. 96, No.2, pp. 293-320, 2003.

[Ren06]
J.~Renegar, Hyperbolic programs, and their derivative relaxations.
Foundations of Computational Mathematics, Vol.~6, No~.1, pp 59-79, 2006.

[Roj96] Rojas, J. Maurice, ``On the Average
Number of Real Roots of Certain Random Sparse Polynomial System,''}
Lectures in Applied Mathematics, Vol. 32 (1996), pp. 689--699,
American Mathematical Society.

[Roj07] Rojas, J. Maurice, ``Efficiently Detecting
Subtori and Torsion Points,'' proceedings of MAGIC 2005 (Midwest Algebra,
Geometry, and their Interactions Conference, Oct. 7-11, 2005, Notre Dame
University, Indiana), edited by A. Corso, J. Migliore, and C. Polini), pp.
213--233, Contemporary Mathematics, vol. 448, AMS Press, 2007.

[RY05] Rojas, J. Maurice and Ye, Yinyu, ``On
Solving Univariate Sparse Polynomials in Logarithmic Time,'' Journal of
Complexity, Volume 21, Issue 1 (Foundations of Computational Mathematics
Conference 2002 special issue), February 2005, pp. 87-110.

[SZ04] Shiffman, Bernard and Zelditch, Steve, {it ``Random polynomials with
prescribed Newton polytope,''} J. Amer. Math. Soc. 17 (2004), pp. 49--108.

[ST02] Spielman, Daniel A. and Teng, Shang-Hua, {it
``Smoothed Analysis of Algorithms,''} Proceedings of the 2002
International Congress of Mathematicians, Vol. I, pp. 597--606,
Higher Ed. Press, Beijing, 2002.