- Series
- Algebra Seminar
- Time
- Monday, December 5, 2022 - 1:30pm for 1 hour (actually 50 minutes)
- Location
- Clough 125 Classroom
- Speaker
- J. Maurice Rojas – TAMU – pdey33@gatech.edu – https://www.math.tamu.edu/~rojas/
- Organizer
- Papri Dey

Around 1997, Shub and Smale proved that sufficiently good upper bounds

on the number of integer roots of polynomials in one variable --- as a function

of the input complexity --- imply a variant of P not equal to NP. Since then,

later work has tried to go half-way: Trying to prove that easier root counts

(over fields instead) still imply interesting separations of complexity

classes. Koiran, Portier, and Tavenas have found such statements over the real

numbers.

We present an analogous implication involving p-adic valuations:

If the integer roots of SPS polynomials (i.e., sums of products of sparse polynomials) of size s never yield more than s^{O(1)} distinct p-adic

valuations, then the permanents of n by n matrices cannot be computed by constant-free, division-free arithmetic circuits of size n^{O(1)}. (The

implication would be a new step toward separating VP from VNP.) We also show that this conjecture is often true, in a tropical geometric sense (paralleling a similar result over the real numbers by Briquel and Burgisser). Finally, we prove a special case of our conjectured valuation bound, providing a p-adic analogue of an earlier real root count for polynomial systems supported on circuits. This is joint work with Joshua Goldstein, Pascal Koiran, and Natacha Portier.