University of Waterloo
Algebraic geometric methods for algorithms in satisfiability, irreducibility of varieties, and identity testing
Abstract
dc:description.abstractIn 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 top fan-in three, and constant bottom fan-in. We also give the first such algorithm for circuits with bottom fan-in two, and constant top 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 circuit 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.
Degree
thesis:*- Grantor dc:publisher
- University of Waterloo
- Year dc:date.issued
- 2025
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Garg, Abhibhav
Subjects
dc:subject × 2Rights
- Language dc:language.iso
- en
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- https://hdl.handle.net/10012/22745