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
theory.