Wednesday, October 11
Milner 317, 12:30 PM
Title: New complexity thresholds for sparse polynomials in one variable
Abstract: Consider a
degree d polynomial f, in one variable, with exactly m monomial terms,
and coefficients in the finite field with p elements. When m=2,
it is a nice exercise to show that one can always decide if f has a
root using just polynomial bit operations in log d + log p.
However, already for m=3, all known algorithms have complexity
exponential in log d or log p. (Indeed, the multivariate analogue is
one of the most basic NP-complete problems, and counting solutions for
curves is central in cryptography.)
We prove that for general m, it is UNlikely to find any better algorithms: For if we could find even a randomized algorithm with complexity polynomial in log d + log p, then we would be able to simulate NP with randomization. This would cause a collapse of several important complexity classes, nearly as dramatic as what P=NP would imply.
Independent of complexity theory, the underlying techniques reveal another interesting connection between analytic number theory and polynomial systems. Our results also improve earlier observations of von zur Gathen, Karpinski, and Shparlinski, and Kaltofen and Koiran. We also discuss more positive results involving sparse polynomials in many variables, and analogous statements over the p-adic rationals.
We assume no background in complexity