Please note: This PhD defence will take place online.
Abhibhav Garg, PhD candidate
David R. Cheriton School of Computer Science
Supervisor: Professor Rafael Oliveira
In this thesis we study three problems that lie in the intersection of abstract algebra and theoretical computer science. The first of these is the polynomial identity testing problem, which is the task of determining if an algebraic circuit computes the identically zero polynomial. We give the first polynomial time deterministic algorithm for the special case of depth four algebraic circuits, with constant top and bottom fan-in. Our methods involve studying higher degree generalisations of classical incidence configurations known as Sylvester–Gallai configurations. The second of these is the problem of checking if a system of equations is satisfiable. In the regime when the number of variables in the system is a constant, we show that satisfiability can be checked in constant depth by algebraic circuits. In particular, we show that the multivariate resultant has a constant depth in this regime, independent of the degrees. The previous best known constructions of the resultant required depth that was logarithmic in the degrees. The final problem we consider is the problem of deciding if an ideal theoretically defined variety is irreducible in characteristic $0$. We show that this task can be solved in the polynomial hierarchy assuming the generalized Riemann hypothesis. This improves the previous best known bound of PSPACE.