Optimization and NP_R-Completeness of Certain Fewnomials (2009)
Pebay, Philippe, Rojas, J. Maurice, Thompson, David C.
We give a high precision polynomial-time approximation scheme for the supremum of any honest n-variate (n+2)-nomial with a constant term, allowing real exponents as well as real coefficients. Our...
Faster Real Feasibility via Circuit Discriminants (2009)
Bihan, Frederic, Rojas, J. Maurice, Stella, Casey
We show that detecting real roots for honestly n-variate (n+2)-nomials (with integer exponents and coefficients) can be done in time polynomial in the sparse encoding for any fixed n. The best...
Refined Asymptotics for Sparse Sums of Squares (2009)
Rojas, J. Maurice, Sethuraman, Swaminathan
To prove that a polynomial is nonnegative on R^n one can try to show that it is a sum of squares of polynomials (SOS). The latter problem is now known to be reducible to a semidefinite programming...
Gregorio Malajovich, J. Maurice Rojas
Let F:=(f1,...,fn) be a random polynomial system with fixed n-tuple of supports. Our main result is an upper bound on the probability that the condition number of f in a region U is larger than 1/ε....
Gregorio Malajovich, Benjamin Diament, Klaus Meer, Pierre Priouret, J. Maurice Rojas, Mike Shub, ...
I summarized below the main results contained in each of my indexed publications. Pointers to the journal sites and the preprint versions may be found at
Gregorio Malajovich, J. Maurice Rojas
Let f: = (f 1,...,f n) be a polynomial system with an arbitrary fixed n-tuple of supports and random coefficients. Our main result is an upper bound on the probability that the condition number of f...
Contemporary Mathematics Why Polyhedra Matter in Non-Linear Equation Solving (2008)
J. Maurice Rojas, To My Sister, Clarissa Amelia
Abstract. We give an elementary introduction to some recent polyhedral techniques for understanding and solving systems of multivariate polynomial equations. We provide numerous concrete examples and...
Contemporary Mathematics Efficiently Detecting Torsion Points and Subtori (2008)
Abstract. Suppose X is the complex zero set of a finite collection of polynomials in Z[x1,..., xn]. We show that deciding whether X contains a point all of whose coordinates are d th roots of unity...
DIMACS Series in Discrete Mathematics and Theoretical Computer Science (2008)
John Keyser, J. Maurice Rojas, Koji Ouchi
Abstract. We describe a method, based on the rational univariate reduction (RUR), for computing roots of systems of multivariate polynomials with rational coefficients. Our method enables exact...
Additive Complexity and Roots of Polynomials (2008)
Over Number Fields, J. Maurice Rojas
Consider any nonzero univariate polynomial with rational coecients, presented as an elementary algebraic expression (using only integer exponents). Letting (f) denote the additive complexity of f ,...
Contemporary Mathematics Finiteness for Arithmetic Fewnomial Systems (2007)
J. Maurice Rojas, Monika Altho
Abstract. Suppose L is any nite algebraic extension of either the ordinary rational numbers or the p-adic rational numbers. Also let g 1; : : : ; g k be polynomials in n variables, with coecients in...
COUNTING ISOLATED ROOTS OF TRINOMIAL SYSTEMS IN THE PLANE AND BEYOND (2007)
Tien-yien Li, J. Maurice Rojas, Xiaoshen Wang
Abstract. We prove that any pair of bivariate trinomials has at most 5 isolated roots in the positive quadrant. The best previous upper bounds independent of the polynomial degrees counted only...
th birthday. Abstract. We show that the decidability of an amplication of Hilbert's Tenth Problem in three variables implies the existence of uncomputably large integral points on certain...
This paper is dedicated to the memory of Laxmi Patel. Abstract. This brief note corrects some errors in the paper quoted in the title, highlights a combinatorial result which may have been...
We propose a new resultant operator, providing a geometrically and computationally more intrinsic setting for elimination theory. The affine resultant extends the benefits the sparse resultant...
Abstract. Let f be a degree D univariate polynomial with real coe#cients and at most 3 monomial terms. We show that all the roots of f in any closed interval of length R can be approximated within an...
Abstract. Let f be a degree D univariate polynomial with real coecients and at most 3 monomial terms. We show that all the roots of f in any closed interval of length R can be approximated within an...
Contemporary Mathematics Algebraic Geometry Over Four Rings and the Frontier to Tractability (2007)
th birthday. Abstract. We present some new and recent algorithmic results concerning polynomial system solving over various rings. In particular, we present some of the best recent bounds on: (a) the...
An Improved Bound on the VC-Dimension of (2007)
Neural Networks With, M. Vidyasagar, J. Maurice Rojas
We derive an improved upper bound for the VC-dimension of neural networks with polynomial activation functions. This improved bound is based on a result of Rojas [Roj00] on the number of connected...
Algorithmic Arithmetic Fewnomial Theory I: One Variable (2007)
Ibrahim, Ashraf, Rojas, J. Maurice, Rusek, Korben
We show that deciding whether a sparse polynomial in one variable has a root in F_p (for p prime) is NP-hard with respect to randomized reductions. As a consequence, we answer open questions on the...
New Complexity Bounds for Certain Real Fewnomial Zero Sets (2007)
Gomez, Joel, Niles, Andrew, Rojas, J. Maurice
Consider real bivariate polynomials f and g, respectively having 3 and m monomial terms. We prove that for all m>=3, there are systems of the form (f,g) having exactly 2m-1 roots in the positive...
On the Sharpness of fewnomial bound and the number of components of a fewnomial hypersurface (2007)
Bihan, Frederic, Rojas, J. Maurice, Sottile, Frank
We show the existence of systems of n polynomial equations in n variables, with a total of n+k+1 distinct monomial terms, possessing [n/k+1]^k nondegenerate positive solutions. (Here, [x] is the...
New Complexity Bounds for Certain Real Fewnomial Zero Sets (Extended Abstract) (2007)
Frederic Bihan, Joel Gomez, Andrew Niles, J. Maurice Rojas
Rojas dedicates this paper to his friend, Professor Tien-Yien Li. Consider real bivariate polynomials f and g, respectively having 3 and m monomial terms. We prove that for all m≥3, there are...
Book Review: Algorithms in Real Algebraic Geometry (2007)
S. Basu, R. Pollack, J. Maurice Rojas
Much like physics, the study of algorithms leads us to beautiful ideas that would otherwise be overlooked by purely abstract reflection. Moreover, as engineers and computational scientists already...
Extremal Real Algebraic Geometry and A-Discriminants (2006)
Dickenstein, Alicia, Rojas, J. Maurice, Rusek, Korben, Shih, Justin
We present a new, far simpler family of counter-examples to Kushnirenko's Conjecture. Along the way, we illustrate a computer-assisted approach to finding sparse polynomial systems with maximally...
A Number Theoretic Interpolation Between Quantum and Classical Complexity Classes (2006)
We reveal a natural algebraic problem whose complexity appears to interpolate between the well-known complexity classes BQP and NP: (*) Decide whether a univariate polynomial with exactly m monomial...
First Steps in Algorithmic Real Fewnomial Theory (2006)
Frederic Bihan, J. Maurice Rojas, Casey E. Stella
Fewnomial theory began with explicit bounds — solely in terms of the number of variables and monomial terms — on the number of real roots of systems of polynomial equations. Here we take the next...
Efficiently Detecting Torsion Points and Subtori (2005)
Suppose X is the complex zero set of a finite collection of polynomials in Z[x_1,...,x_n]. We show that deciding whether X contains a point all of whose coordinates are d_th roots of unity can be...
First Steps in Algorithmic Fewnomial Theory (2004)
Bihan, Frederic, Rojas, J. Maurice, Stella, Casey E.
Fewnomial theory began with explicit bounds -- solely in terms of the number of variables and monomial terms -- on the number of real roots of systems of polynomial equations. Here we take the next...
Arithmetic multivariate Descartes' rule (2004)
Rojas, J. Maurice (Joseph Maurice)
American Journal of Mathematics - Volume 126, Number 1, February 2004
Attitude and position estimation from vector observations (2004)
Daniele Mortari, J. Maurice Rojas, John L. Junkins
This paper introduces three novel methods to evaluate attitude and position from vector observations using a vision-based technology camera. The first approach, called Linear Algebra Resection...
Arithmetic Multivariate Descartes’ Rule (2004)
J. Maurice Rojas, J. Maurice Rojas
Abstract. Let L be any number field or p-adic field and consider F: = (f 1,..., f k) where f i
Arithmetic Multivariate Descartes ’ Rule 1 (2004)
Let L be any number field or p-adic field and consider F: = (f1,...,fk) where f1,...,fk ∈ L[x1,...,xn] and no more than µ distinct exponent vectors occur in the monomial term expansions of the fi....
A Direct Ultrametric Approach to Additive Complexity and the Shub-Smale Tau Conjecture (2003)
The Shub-Smale Tau Conjecture is a hypothesis relating the number of integral roots of a polynomial f in one variable and the Straight-Line Program (SLP) complexity of f. A consequence of the truth...
Dedekind Zeta Functions and the Complexity of Hilbert's Nullstellensatz (2003)
Let HN denote the problem of determining whether a system of multivariate polynomials with integer coefficients has a complex root. It has long been known that HN in P implies P=NP and, thanks to...
Let HN denote the problem of determining whether a system of multivariate polynomials with integer coecients has a complex root. It has long been known that HN2P =) P=NP and, thanks to recent work of...
Why Polyhedra Matter in Non-Linear Equation Solving (2002)
We give an elementary introduction to some recent polyhedral techniques for understanding and solving systems of multivariate polynomial equations. We provide numerous concrete examples and...
Li, Tien-Yien, Rojas, J. Maurice, Wang, Xiaoshen
We prove that any pair of bivariate trinomials has at most 5 isolated roots in the positive quadrant. The best previous upper bounds independent of the polynomial degrees were much larger, e.g.,...
High Probability Analysis of the Condition Number of Sparse Polynomial Systems (2002)
Malajovich, Gregorio, Rojas, J. Maurice
Let F:=(f_1,...,f_n) be a random polynomial system with fixed n-tuple of supports. Our main result is an upper bound on the probability that the condition number of f in a region U is larger than...
Additive Complexity and the Roots of Polynomials Over Number Fields and p-adic Fields (2002)
Consider any nonzero univariate polynomial with rational coefficients, presented as an elementary algebraic expression (using only integer exponents). Letting sigma(f) denotes the additive complexity...
An Improved Bound on the VC-Dimension of Neural Networks with Polynomial Activation Functions (2001)
Rojas, J. Maurice, Vidyasagar, M.
In this note, we derive an improved upper bound for the VC-dimension of neural networks with polynomial activation functions. This improved bound is based on a result of Rojas on the number of...
Arithmetic Multivariate Descartes' Rule (2001)
Let L be any number field or $\mathfrak{p}$-adic field and consider F:=(f_1,...,f_k) where f_i is in L[x_1,...,x_n]\{0} for all i and there are exactly m distinct exponent vectors appearing in...
On Solving Fewnomials Over Intervals in Fewnomial Time (2001)
Let f be a degree D univariate polynomial with real coefficients and exactly m monomial terms. We show that in the special case m=3 we can approximate within eps all the roots of f in the interval...
Computational Arithmetic Geometry I: Sentences Nearly in the Polynomial Hierarchy (2001)
We consider the average-case complexity of some otherwise undecidable or open Diophantine problems. More precisely, consider the following: I Given a polynomial f 2Z[v;x; y], decide the sentence 9v...
Finiteness for arithmetic fewnomial systems (2001)
Abstract. Suppose L is any nite algebraic extension of the ordinary rational numbers, or any unrami ed algebraic extension of the p-adic rational numbers. Also let f 1; : : : ; f k be polynomials in...
Computational Arithmetic Geometry I: Sentences Nearly in the Polynomial Hierarchy (2001)
We consider the average-case complexity of some otherwise undecidable or open Diophantine problems. More precisely, consider the following: I Given a polynomial f ∈Z[v, x, y], decide the sentence...
Random Sparse Polynomial Systems (2000)
Malajovich, Gregorio, Rojas, J. Maurice
Let f:=(f^1,\...,f^n) be a sparse random polynomial system. This means that each f^i has fixed support (list of possibly non-zero coefficients) and each coefficient has a Gaussian probability...
Finiteness for Arithmetic Fewnomial Systems (2000)
Suppose L is any finite algebraic extension of either the ordinary rational numbers or the p-adic rational numbers. Also let g_1,...,g_k be polynomials in n variables, with coefficients in L, such...
Counting Isolated Roots of Trinomial Systems in the Plane and Beyond (2000)
Li, Tien-Yien, Rojas, J. Maurice, Wang, Xiaoshen
We prove that any pair of bivariate trinomials has at most 5 isolated roots in the positive quadrant. The best previous upper bounds independent of the polynomial degrees counted only non-degenerate...
Algebraic Geometry Over Four Rings and the Frontier to Tractability (2000)
We present some new and recent algorithmic results concerning polynomial system solving over various rings. In particular, we present some of the best recent bounds on: (a) the complexity of...
Computing Complex Dimension Faster and Deterministically (2000)
We give a new complexity bound for calculating the complex dimension of an algebraic set. Our algorithm is completely deterministic and approaches the best recent randomized complexity bounds. We...
Computational Arithmetic Geometry I: Sentences Nearly in the Polynomial Hierarchy (2000)
We consider the average-case complexity of some otherwise undecidable or open Diophantine problems. More precisely, consider the following: (I) Given a polynomial f in Z[v,x,y], decide the sentence...
Random sparse polynomial systems (2000)
This paper is dedicated to Sueli Rocha do Nascimento. Abstract. We derive an explicit formula for the expected number of real roots of certain random sparse polynomial systems. We propose (and use) a...
Random sparse polynomial systems (2000)
Gregorio Malajovich, J. Maurice Rojas
To Steve Smale on his 70 th birthday. Let f:=(f
Some speed-ups and speed limits for real algebraic geometry (2000)
some conditional, on speeding up computational algebraic geometry over the reals: 1. A new and sharper upper bound on the number of connected components of a semi-algebraic set. Our bound is novel in...
Descartes' Rule for Trinomials in the Plane and Beyond (2000)
We prove that any pair of bivariate trinomials has at most 16 roots in the positive quadrant, assuming there are only finitely many roots there. The best previous upper bound independent of the...
Computing Complex Dimension Faster and Deterministically (Extended Abstract) (2000)
We give a new complexity bound for calculating the complex dimension of an algebraic set. Our algorithm is completely deterministic and approaches the best recent randomized complexity bounds. We...
Computational Arithmetic Geometry I: Sentences Nearly In The Polynomial Hierarchy (2000)
We consider the average-case complexity of some otherwise undecidable or open Diophantine problems. More precisely, consider the following: I. Given a polynomial f 2Z[v; x; y], decide the sentence 9v...
Some Speed-Ups and Speed Limits for Real Algebraic Geometry (1999)
We give new positive and negative results (some conditional) on speeding up computational algebraic geometry over the reals: (1) A new and sharper upper bound on the number of connected components of...
Toric intersection theory for affine root counting (1999)
th birthday. Abstract. Given any polynomial system with xed monomial term structure, we give explicit formulae for the generic number of roots (over any algebraically closed eld) with specied...
Solving degenerate sparse polynomial systems faster (1999)
This paper is dedicated to my son, Victor Lorenzo. Abstract. Consider a system F of n polynomial equations in n unknowns, over an algebraically closed field of arbitrary characteristic. We present a...
Algebraic Geometry Over Four Rings and the Frontier to Tractability (1999)
We present some new and recent algorithmic results concerning polynomial system solving over various rings. In particular, we present some of the best recent bounds on: (a) the complexity of...
On the Complexity of Diophantine Geometry in Low Dimensions (Extended Abstract) (1999)
We consider the average-case complexity of some otherwise undecidable or open Diophantine problems. More precisely, we show that the following two problems can be solved within PSPACE: I. Given...
Solving degenerate sparse polynomial systems faster (1999)
This paper is dedicated to my son, Victor Lorenzo. Abstract. Consider a system F of n polynomial equations in n unknowns, over an algebraically closed field of arbitrary characteristic. We present a...
On the Complexity of Diophantine Geometry in Low Dimensions (1998)
We consider the average-case complexity of some otherwise undecidable or open Diophantine problems. More precisely, we show that the following two problems can be solved in the complexity class...
Solving Degenerate Sparse Polynomial Systems Faster (1998)
Consider a system F of n polynomial equations in n unknowns, over an algebraically closed field of arbitrary characteristic. We present a fast method to find a point in every irreducible component of...
Uncomputably Large Integral Points on Algebraic Plane Curves? (1998)
We show that the decidability of an amplification of Hilbert's Tenth Problem in three variables implies the existence of uncomputably large integral points on certain algebraic curves. We obtain this...
Intrinsic Near Quadratic Complexity Bounds for Real Multivariate Root Counting (1998)
We give a new algorithm, with three versions, for computing the number of real roots of a system of n polynomial equations in n unknowns. The first version is of Monte Carlo type and, neglecting...
Intrinsic Near Quadratic Complexity Bounds for Real Multivariate Root Counting (1998)
this paper): First, pick a U 2G
Uncomputably Large Integral Points On Algebraic Plane Curves? (1998)
. We show that the decidability of an amplification of Hilbert's Tenth Problem in three variables implies the existence of uncomputably large integral points on certain algebraic curves. We...
Some New Applications of Toric Geometry (1997)
This paper reexamines univariate reduction from a toric geometric point of view. We begin by constructing a binomial variant of the $u$-resultant and then retailor the generalized characteristic...
Toric Generalized Characteristic Polynomials (1997)
We illustrate an efficient new method for handling polynomial systems with degenerate solution sets. In particular, a corollary of our techniques is a new algorithm to find an isolated point in every...
Abstract. This paper reexamines univariate reduction from a toric geometric point of view. We begin by constructing a binomial variant of the u-resultant and then retailor the generalized...
Toric Generalized Characteristic Polynomials (1997)
. We illustrate an efficient new method for handling polynomial systems with degenerate solution sets. In particular, a corollary of our techniques is a new algorithm to find an isolated point in...
Some New Applications Of Toric Geometry (1997)
. This paper reexamines univariate reduction from a toric geometric point of view. We begin by constructing a binomial variant of the u-resultant and then retailor the generalized characteristic...
Toric Intersection Theory for Affine Root Counting (1997)
. Given any polynomial system with fixed monomial term structure, we give explicit formulae for the generic number of roots (over any algebraically closed field) with specified coordinate vanishing...
This brief note corrects some errors in the paper quoted in the title, highlights a combinatorial result which may have been overlooked, and points to further improvements in recent literature.
Toric Intersection Theory for Affine Root Counting (1996)
Given any polynomial system with fixed monomial term structure, we give explicit formulae for the generic number of roots with specified coordinate vanishing restrictions. For the case of affine...
Counting affine roots of polynomial systems via pointed Newton polytopes (1996)
J. Maurice Rojas, Xiaoshen Wang
This paper is dedicated to the hope of justice for Enrique Funez Florez and Alicia Sotero
. This brief note corrects some errors in the paper quoted in the title, highlights a combinatorial result which may have been overlooked, and points to further improvements in recent literature. 1....