PhD Seminar • Algorithms and Complexity • Interactive Proofs for Primality Testing of Special Classes of Ideals

Please note: This PhD seminar will take place in DC 1302 and online.

Abhibhav Garg, PhD candidate
David R. Cheriton School of Computer Science

Supervisor: Professor Rafael Oliveira

Given a set of polynomials as an algebraic circuit, we study the problem of testing if the ideal generated by these polynomials is prime. This is a generalization of the problem of testing if the polynomials have a common solution. It is also a generalization of the problem of testing if a polynomial is absolutely irreducible. Assuming GRH, we show that for certain classes of ideals, namely radical ideals and complete intersection ideals, the problem of testing primality lies in the third level of the polynomial hierarchy. This is almost optimal, since the problems are NP-hard. Previously, the best known bound for these problems was PSPACE.

Our method is a vast generalization of the method used by Koiran to show that satisfiability of polynomials is in PH. We study how algebraic and geometric properties of ideals such as irreducibility and dimension behave under mod p reduction of coefficients. We give new effective versions of classical results from algebraic geometry and commutative algebra that may have independent applications.

This is joint work with Rafael Oliveira and Nitin Saxena.

To attend this PhD seminar in person, please go to DC 1302. You can also attend virtually using Zoom.