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.

In this note we study a conjecture of Madiman and Wang which predicted that the generalized Gaussian distribution minimizes the Rényi entropy of the sum of independent random variables. Through a variational analysis, we show that the generalized Gaussian fails to be a minimizer for the problem.

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.