Please use this identifier to cite or link to this item: doi:10.22028/D291-29880
Title: On approximate polynomial identity testing and real root finding
Author(s): Jindal, Gorav
Language: English
Year of Publication: 2019
Free key words: algebraic complexity theory
computing real roots of sparse polynomials
commutative rank of matrix spaces
computer algebra
DDC notations: 510 Mathematics
Publikation type: Doctoral Thesis
Abstract: In this thesis we study the following three topics, which share a connection through the (arithmetic) circuit complexity of polynomials. 1. Rank of symbolic matrices. 2. Computation of real roots of real sparse polynomials. 3. Complexity of symmetric polynomials. We start with studying the commutative and non-commutative rank of symbolic matrices with linear forms as their entries. Here we show a deterministic polynomial time approximation scheme (PTAS) for computing the commutative rank. Prior to this work, deterministic polynomial time algorithms were known only for computing a 1/2-approximation of the commutative rank. We give two distinct proofs that our algorithm is a PTAS. We also give a min-max characterization of commutative and non-commutative ranks. Thereafter we direct our attention to computation of roots of uni-variate polynomial equations. It is known that solving a system of polynomial equations reduces to solving a uni-variate polynomial equation. We describe a polynomial time algorithm for (n,k,\tau)-nomials which computes approximations of all the real roots (even though it may also compute approximations of some complex roots). Moreover, we also show that the roots of integer trinomials are well-separated. Finally, we study the complexity of symmetric polynomials. It is known that symmetric Boolean functions are easy to compute. In contrast, we show that the assumption VP \neq VNP implies that there exist hard symmetric polynomials. To prove this result, we use an algebraic analogue of the classical Newton iteration.
In dieser Dissertation untersuchen wir die folgenden drei Themen, welche durch die (arithmetische) Schaltkreiskomplexität von Polynomen miteinander verbunden sind: 1. der Rang von symbolischen Matrizen, 2. die Berechnung von reellen Nullstellen von dünnbesetzten (“sparse”) Polynomen mit reellen Koeffizienten, 3. die Komplexität von symmetrischen Polynomen. Wir untersuchen zunächst den kommutativen und nicht-kommutativen Rang von Matrizen, deren Einträge aus Linearformen bestehen. Hier beweisen wir die Existenz eines deterministischem Polynomialzeit-Approximationsschemas (PTAS) für die Berechnung des kommutative Ranges. Zuvor waren polynomielle Algorithmen nur für die Berechnung einer 1/2-Approximation des kommutativen Ranges bekannt. Wir geben zwei unterschiedliche Beweise für den Fakt, dass unser Algorithmus tatsächlich ein PTAS ist. Zusätzlich geben wir eine min-max Charakterisierung des kommutativen und nicht-kommutativen Ranges. Anschließend lenken wir unsere Aufmerksamkeit auf die Berechnung von Nullstellen von univariaten polynomiellen Gleichungen. Es ist bekannt, dass das Lösen eines polynomiellem Gleichungssystems auf das Lösen eines univariaten Polynoms zurückgeführt werden kann. Wir geben einen Polynomialzeit-Algorithmus für (n, k, \tau)-Nome, welcher Abschätzungen für alle reellen Nullstellen berechnet (in manchen Fallen auch Abschätzungen von komplexen Nullstellen). Zusätzlich beweisen wir, dass Nullstellen von ganzzahligen Trinomen stets weit voneinander entfernt sind. Schließlich untersuchen wir die Komplexität von symmetrischen Polynomen. Es ist bereits bekannt, dass sich symmetrische Boolesche Funktionen leicht berechnen lassen. Im Gegensatz dazu zeigen wir, dass die Annahme VP \neq VNP bedeutet, dass auch harte symmetrische Polynome existieren. Um dies zu beweisen benutzen wir ein algebraisches Analog zum klassischen Newton-Verfahren.
Link to this record: urn:nbn:de:bsz:291--ds-298805
hdl:20.500.11880/28320
http://dx.doi.org/10.22028/D291-29880
Advisor: Bläser, Markus
Date of oral examination: 11-Nov-2019
Date of registration: 19-Nov-2019
Faculty: MI - Fakultät für Mathematik und Informatik
Department: MI - Informatik
Collections:SciDok - Der Wissenschaftsserver der Universität des Saarlandes

Files for this record:
File Description SizeFormat 
GoravThesis.pdfThe complete thesis973,72 kBAdobe PDFView/Open


Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.