On approximate polynomial identity testing and real root finding

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.