Randomized Algorithms Seminar

We first review some basic complexity results for detecting roots of univariate polynomials over various fields. We then focus on the real case, revealing new families of sparse polynomials, of degree d, whose real roots can be approximated in time polynomial in log(d). Along the way, we recall Smale's alpha-invariant and its connection to the convergence of Newton iteration.

This is the first meeting of the Randomized Algebraic Algorithms Seminar this spring 2012 semester. Future talks will develop the connection between complexity theory and polynomial system solving over various fields.

We show that NP-hardness for detecting roots of polynomials already appears in one variable, over F_p, for p prime. Such a result was previously only known for F_q with q a power of 2 [Kipnis & Shamir, 1999].

The proof of our new result involves 3 main tricks: (A) reducing a classical NP-complete problem to deciding whether a system of sparse polynomials in one variable vanishes at a Dth root of unity, (B) efficiently constructing small primes in arithmetic progressions, and (C) efficiently building random linear combinations to reduce systems of equations to a pair of equations.

In Part I, we reviewed (A). For Part II, we review the distribution of primes in arithmetic progression, and why they are relevant to building finite fields with special properties.

A-discriminants can be thought of as polynomials describing regions of constant topology for families of real algebraic sets. They are also notoriously difficult to compute, but the Horn-Kapranov Uniformization gives us a remarkably simple description of the underlying boundaries where the topology of the family changes. We review some basics of the Horn-Kapranov Uniformization, with an eye toward applications and algorithms.

In particular, we'll start with the case where A is a set of n+2 points in Z^n and, in the coming lectures, we'll see how Hermite normal form, hyperplane plane arrangements, and linear programming (among many other ideas) arise in the application of A-discriminants.

This will be the first in a series of lectures, ultimately culminating in a new algorithm for counting real roots of polynomial systems.

Today, we'll see a small demo of some matlab code that helps us easily visualize certain A-discriminant varieties. We'll also learn about the Cayley Trick and Archimedean Newton polytopes.

This is the third in a series of lectures, ultimately culminating in a new algorithm for counting real roots of polynomial systems.

We present a deterministic 4^t-1q^{(t-2)/(t-1) +o(1)} algorithm to decide whether a univariate polynomial f, with exactly t monomial terms, has a root in F_q. A corollary of our method - the first with complexity sub-linear in q when t is fixed --- is that the nonzero roots must lie within a union of at most 2 √ t-1   q^(t-2)(t-1) cosets of a proper subgroup of F_q^*. Another corollary is the first randomized sub-linear algorithm for detecting common degree one factors of k-tuples of t-nomials in F_q[x].

This is joint work with Jingguo Bi and Qi Cheng.