Feasibility of Circuit Polynomials without Purple Swans: Feasibility without Purple Swans

Suppose f is a polynomial in n variables with degree d, exactly n + k monomial terms, coefficients in { ± 1, …, ±H} for some <Formula format="inline"><TexMath><?TeX H\!∈ \!N?></TexMath><AltText>Math 1</AltText><File name="issac24-46-inline1" type="svg"/></Formula>, 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 <Formula format="inline"><TexMath><?TeX O\!(1/2ⁿ H)?></TexMath><AltText>Math 2</AltText><File name="issac24-46-inline2" type="svg"/></Formula>-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.