Computing the isotopy type of a hypersurface, defined as the positive real zero set of a multivariate polynomial, is a challenging problem in real algebraic geometry. We focus on the case where the defining polynomial has combinatorially restricted exponent vectors and fixed coefficient signs, enabling faster computation of the isotopy type. In particular, Viro's patchworking provides a polyhedral complex that has the same isotopy type as the hypersurface, for certain choices of the coefficients. So we present properties of the signed support, focusing mainly on the case of n-variate (n+3)-nomials, that ensure all possible isotopy types can be obtained via patchworking. To prove this, we study the signed reduced A-discriminant and show that it has a simple structure if the signed support satisfies some combinatorial conditions.

Suppose f is a polynomial in n variables with real coefficients and exactly n + k monomial terms. Estimating the number of connected components of the zero set of f in the positive orthant is a fundamental problem in real algebraic geometry, and tight estimates have applications in computational complexity and topology. We prove that, for generic coefficients and exponent vectors, the number of connected components is at most 3 when k = 3, settling an open question from Fewnomial Theory. Our results also extend to exponential sums with real exponents. A key contribution is a deeper analysis of the underlying \(\mathcal {A}\)-discriminant contours, which should be useful for other quantitative geometric problems.

Suppose f is a polynomial in n variables with degree d, exactly n + k monomial terms, coefficients in { ± 1, …, ±H} for some <?TeX $H\!\in \!\mathbb {N}$?> Math 1 , and Newton polytope of positive volume. Testing real feasibility of such an f is a fundamental task whose bit-complexity remains a mystery, even in the first non-trivial case k = 2: The fastest algorithms so far have deterministic bit-complexity (nlog (dH))O(n). We prove a significant speed-up that holds for all but a small collection of inputs in the k = 2 case: Bit complexity (nlog (dH))O(1) for all but a <?TeX $O\!\left(\frac{1}{2^n H}\right)$?> Math 2 -fraction of the f above, for any fixed support. Our result follows by combining a connection to diophantine approximation with a more recent anti-concentration result. In particular, we show that for random inputs, Baker’s famous theorem on linear forms in logarithms can be significantly sharpened. We also consider extensions beyond feasibility such as counting connected components and systems of circuit polynomials.

We reveal a complexity chasm, separating the trinomial and tetranomial cases, for solving univariate sparse polynomial equations over certain local fields. First, for any fixed field K∈ Q2,,Q3,Q5, …, we prove that any polynomial f Z [x] with exactly 3 monomial terms, degree d, and all coefficients having absolute value at most H, can be solved over K within deterministic time logO(1) (dH) in the classical Turing model. (The best previous algorithms were of complexity exponential in log d, even for just counting roots in Qp.) In particular, our algorithm generates approximations in Q with bit-length log O(1) (dH) to all the roots of f in K, and these approximations converge quadratically under Newton iteration. On the other hand, we give a unified family of tetranomials requiring Ω(d log H) digits to distinguish the base-p expansions of their roots in K.

Suppose F:=(f_1,łdots,f_n) is a system of random n-variate polynomials with f_i having degree łeq\!d_i and the coefficient of x^a_1 _1\cdots x^a_n _n in f_i being an independent complex Gaussian of mean 0 and variance \fracd_i! a_1!\cdots a_n!łeft(d_i-\sum^n_j=1 a_j \right)! . Recent progress on Smale's 17þth Problem by Lairez --- building upon seminal work of Shub, Beltran, Pardo, Bü rgisser, and Cucker --- has resulted in a deterministic algorithm that finds a single (complex) approximate root of F using just N^O(1) arithmetic operations on average, where N\!:=\!\sum^n_i=1 \frac(n+d_i)! n!d_i! (=n(n+\max_i d_i)^O(\min\n,\max_i d_i)\ ) is the maximum possible total number of monomial terms for such an F. However, can one go faster when the number of terms is smaller, and we restrict to real coefficient and real roots? And can one still maintain average-case polynomial-time with more general probability measures? We show the answer is yes when F is instead a binomial system --- a case whose numerical solution is a key step in polyhedral homotopy algorithms for solving arbitrary polynomial systems. We give a deterministic algorithm that finds a real approximate root (or correctly decides there are none) using just O(n^3łog^2(n\max_i d_i)) arithmetic operations on average. Furthermore, our approach allows real Gaussians with arbitrary variance. We also discuss briefly the obstructions to maintaining average-case time polynomial in nłog \max_i d_i when F has more terms.

We present a deterministic $2^{O(t)}q^{\frac{t-2}{t-1}+o(1)}$ algorithm to decide whether a univariate polynomial $f$, with $t$ monomial terms and degree $

We present a deterministic 2O(t)qt-2/t-1 +o(1) algorithm to decide whether a univariate polynomial f, with exactly t monomial terms and degree

Relative to the sparse encoding, we show that deciding whether a univariate polynomial has a p-adic rational root can be done in NP for most inputs. We also prove a sharper complexity upper bound of P for polynomials with suitably generic p-adic Newton polygon. The best previous complexity upper bound was EXPTIME. We then prove an unconditional complexity lower bound of NP-hardness with respect to randomized reductions, for general univariate polynomials. The best previous lower bound assumed an unproved hypothesis on the distribution of primes in arithmetic progression. We also discuss analogous results over R.

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 nn. The best previous complexity bounds were exponential in the sparse encoding, even for n fixed. We then give a characterization of those functions k(n) such that the complexity of detecting real roots for n-variate(n+k(n))-nomials transitions from P to NP-hardness as n → ∞. Our proofs follow in large part from a new complexity threshold for deciding the vanishing of A-discriminants of n-variate (n+k(n))-nomials. Diophantine approximation, through linear forms in logarithms, also arises as a key tool.

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 polynomials f/sub 1/,...,f/sub m//spl isin/Z[x/sub 1/,...,x/sub n/] defining a variety of dimension /spl les/0 in C/sup n/, find all solutions in Z/sup n/ of f/sub 1/=/spl middot//spl middot//spl middot/=f/sub m/=0. II. For a given polynomial f/spl isin/Z[v,x,y] defining an irreducible nonsingular non-ruled surface in C/sup 3/, decide the sentence /spl exist/v /spl forall/x /spl exist/y f(v, z, y)=/sup ?/0, quantified over N. Better still, we show that the truth of the Generalized Riemann Hypothesis (GRH) implies that detecting roots in Q/sup n/ for the polynomial systems in problem (I) can be done via a two-round Arthur-Merlin protocol, i.e., well within the second level of the polynomial hierarchy. (Problem (I) is, of course, undecidable without the dimension assumption.) The decidability of problem (II) was previously unknown. Along the way, we also prove new complexity and size bounds for solving polynomial systems over C and Z/pZ. A practical point of interest is that the aforementioned Diophantine problems should perhaps be avoided in the construction of cryptosystems.

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. II.Given polynomials fl, , f,,, E iZ[zi, , zn] defining a variety of dimension < 0 in V' , find all solutions in ?Zn of fi = =fm = 0.For a given polynomial f E Z[v, 2, y] defining an irreducible nonsingular non-ruled surface in @, decide the sentence 3v t/x 3y f(v, z, y) LO, quantified over I% Better still, we show that the truth of the Generalized Riemann Hypothesis (GRH) implies that detecting roots in @' for the polynomial systems in problem (I) can be done via a two-round Arthur-Merlin protocol, i.e., well within the second level of the polynomial hierarchy.(Problem (I) is, of course, undecidable without the dimension assumption.)The decidability of problem (II) was previously unknown.Along the way, we also prove new complexity and size bounds for solving polynomial systems over @ and Z/pZ.A practical point of interest is that the aforementioned Diophantine problems should perhaps be avoided in the construction of crypto-systems.

The trickle-down of useful computational techniques from algebraic geometry to the applied world is notoriously slow. So the author remedies this in a small way by giving a simple introduction to some powerful new techniques for solving equations. The methods presented lead to the fastest known algorithms for real-solving-finding the real (as opposed to complex) solutions of a system of polynomial equations.

It was shown in ~er75]that the number of roots in (C") n of a polynomial system depends only on the Newton polytopes of the system, for almost all specializations of the coefficients.