Videos

Speeding Up Real Root Counting for Most Circuit Systems via a Randomized Version of Baker's Theorem

August 7, 2025
Abstract
A fundamental problem harder for real polynomial systems than complex polynomial systems is root counting: All classical algorithms have worst-case exponential-time complexity. Restricting to sparse polynomial reduces the number of real roots and, for very sparse systems, enables significant speed-ups (although the problem is NP-hard for sufficiently many monomial terms). We consider the case of n polynomials in n variables where the total number of distinct exponent vectors is n+2, the coefficients are integers of absolute value at most H, and the exponent vectors do not lie in a common affine hyperplane: The so-called circuit case. We outline an approach to attaining polynomial-time real root counting for circuit systems, for a fraction of coefficient values tending to 1 as H tends to infinity. The key idea is to prove a new, randomized version of a classical Diophantine approximation result of Baker and Wustholz. This builds upon recent joint work with Weixun Deng, Alperen Ergur, and Grigoris Paouris.