09:00 AM  09:15 AM


Final Presentations: Opening Remarks
J. Maurice Rojas (Texas A & M University)

 Location
 MSRI: Baker Board Room
 Video


 Abstract
 
 Supplements



09:15 AM  09:50 AM


Counting the roots of a polynomial modulo p2
trajan hammonds (Carnegie Mellon University), Jeremy Johnson (Humboldt State University), Angela Patini (University of Pennsylvania)

 Location
 MSRI: Baker Board Room
 Video

 Abstract
Until recently, the only known method of finding the roots of polynomials over prime power rings, other than fields, was brute force. One reason for this is the lack of a division algorithm, thus obstructing the use of greatest common divisors. Suppose f is any nonzero univariate polynomial of degree d in Z/p^nZ[x]. For the case n=2, we prove a new efficient algorithm to count the roots in Z/p^2Z within time polynomial in d + log p. The key idea is to partition the roots via their image under reduction modulo p, and then carefully use Hensel's Lemma. This builds upon recent work of Cheng, Gao, Rojas, and Wan.
 Supplements



10:00 AM  11:20 AM


On the maximal number of roots of a trinomial over a prime field
Jeshu Dastidar (San Francisco State University), Viviana Peña Márquez (Konrad Lorenz Fundación Universitaria), Ryan Pugh (University of California, Santa Cruz)

 Location
 MSRI: Baker Board Room
 Video

 Abstract
Canetti, Friedlander, et al. (2002) studied the randomness of powers over finite fields and along the way derived an analogue of Descartes’™ rule over the finite field F_q with q elements: They showed that the number of roots of any univariate tnomial, with exponents {0,a_2,...,a_t} and the differences a_ia_j all relatively prime to q1, is O(q^{(t2)/(t1)}). The correct optimal bounds remain a mystery for prime fields, even in the case of polynomials with three terms. Following the work of Kelley (2016), we seek to prove the conjecture that the number of roots in F_p of a trinomial with a linear middle term is always O(log p). We expand current evidence by using a supercomputer to determine the number of roots of these trinomials for 139,571 < p 191,491. We also prove that the search can be restricted to trinomials with a middle linear term when p1 has less than three distinct prime factors.
 Supplements



10:45 AM  11:20 AM


Applying discriminant chambers to structured polynomials
Amy Adair (Louisiana State University), Alex Mendez (University of Illinois at UrbanaChampaign), Diane Tchuindjo (University of Maryland)

 Location
 MSRI: Baker Board Room
 Video

 Abstract
One way to prove the algorithmic hardness of a function is to consider its circuit complexity: the minimal size of a circuit computing the function. Recent work in circuit complexity has revealed that it is enough to restrict to depth4 circuits, inspiring the study of certain structured polynomials called sumofproductsofsparse (SPS) polynomials. In particular, showing sufficiently good upper bounds for the number of real roots of SPS polynomials would imply the hardness of the permanent. If f and g are univariate polynomials with real coefficients and t terms, then does fg1 have a number of real roots that grows at most linearly in t? We consider the first nontrivial approach towards such a bound via Adiscriminants, leading to interesting questions involving sparse polynomial systems.
 Supplements



11:30 AM  01:00 PM


Lunch

 Location
 MSRI: Baker Board Room
 Video


 Abstract
 
 Supplements



01:00 PM  01:35 PM


Using lower binomials to approximate roots of trinomials
Harold Jimenez Polo (University of California, Berkeley), Esteban Madrigal (Harvard University), Carlos Osco Huaricapcha (San Francisco State University)

 Location
 MSRI: Baker Board Room
 Video

 Abstract
Given a univariate trinomial f in R[x], we analyze the Archimedean Newton polytope of f and the corresponding lower binomials. The roots of these lower binomials conjecturally provide high quality approximations of the roots of f. We implement Smale's alphacriterion to analyze whether our approximations converge quickly under Newton iteration. We know that under certain conditions every root of a lower binomial is an approximate root of a trinomial. We expect to determine when at least one root of a lower binomial is an approximate root. Moreover, for roots that are not approximate, we examine when Newton's method yields approximate roots.
 Supplements



01:45 PM  02:20 PM


Topology of positive zero sets of bivariate pentanomials
Malachi Alexander (University of California, Santa Cruz), Ashley De Luna (California State Polytechnic University, Pomona), Christian McRoberts (Iowa State University)

 Location
 MSRI: Baker Board Room
 Video

 Abstract
A fundamental problem in many applications is determining the real solutions of a polynomial. In recent years, the Adiscriminant variety of Gelfand, Kapranov and Zelevinsky has proved to be a valuable tool. Its complement over the real numbers defines regions of coefficient values called chambers. We implement an algorithm in MATLAB that draws Adiscriminant curves for families of bivariate pentanomials where the topology of the underlying zero set is constant. Our program graphs the discriminant curve with all of its chambers and automatically computes the topology of all smooth zero set for the given families of bivariate pentanomials. We hope automated topology computation for high degree polynomials will prove useful for the algebraic geometry community.
 Supplements



02:30 PM  03:05 PM


Topology of positive zero sets of nvariate (n+4)nomials
Davina Boykin (Valparaiso University), Sabrina Enriquez (University of Southern California), Noemi Valdez (Harvard University)

 Location
 MSRI: Baker Board Room
 Video

 Abstract
Let f be a polynomial of degree d with exactly n+4 monomial terms in R[x_1,…,x_n]. We show that one can efficiently compute an explicit polyhedral complex with the same isotopy type as the positive zero set of f. In particular, the complexity of our construction is polynomial in u + log d with high probability. Along the way, we derive and implement an algorithm that, given an nvariate (n+4)nomial f, outputs a plot of the reduced Adiscriminant contour in R^3.
 Supplements



03:05 PM  03:15 PM


Closing Remarks
Federico Ardila (San Francisco State University)

 Location
 MSRI: Baker Board Room
 Video


 Abstract
 
 Supplements



03:15 PM  04:00 PM


Afternoon Tea

 Location
 MSRI: Baker Board Room
 Video


 Abstract
 
 Supplements


