Back to search

University of Waterloo

Algebraic geometric methods for algorithms in satisfiability, irreducibility of varieties, and identity testing

Abstract

dc:description.abstract

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 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 × 2

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/10012/22745

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Garg, Abhibhav. Algebraic geometric methods for algorithms in satisfiability, irreducibility of varieties, and identity testing. University of Waterloo, 2025. https://hdl.handle.net/10012/22745