Please use this identifier to cite or link to this item: doi:10.22028/D291-26647
Title: Why are certain polynomials hard? : A look at non-commutative, parameterized and homomorphism polynomials
Other Titles: Warum sind bestimmte Polynome schwer?
Author(s): Engels, Christian
Language: English
Year of Publication: 2015
SWD key words: Average-case-Komplexität
Komplexität
Parametrisierte Komplexität
Multivariates Polynom
Free key words: arithmetic circuits
arithmetic complexity
circuit complexity
fixed parameter complexity
average case complexity
computational complexity
DDC notations: 004 Computer science, internet
Publikation type: Doctoral Thesis
Abstract: In this thesis we will try to answer the question why specific polynomials have no small suspected arithmetic circuits. We will look at this general problem in three different ways. First, we study non-commutative computation. Here we show matching upper and lower bounds for the non-commutative permanent for various restricted graph classes. Our main result gives algebraic branching program upper and lower bounds for graphs with connected component size 6 as well as a #P hardness result. We introduce a measure that characterizes this complexity on these instances. Secondly, we introduce a new framework for arithmetic circuits, similar to fixed parameter tractability in the boolean setting. This framework shows that specific polynomials based on graph problems have the expected complexity as in the counting FPT case. We introduce classes BVW[t] which are close to the boolean setting but hardly use the power of arithmetic circuits. We then introduce VW[t] with modified problems to remedy this situation. Thirdly, we study polynomials defined by graph homomorphisms and show various dichotomy theorems. This shows that even restrictions on the graphs can already give us hard instances. Finally, we stray from our main continuous thread and handle simple heuristics for metric graphs. Insteadof studying specific metrics we look at a randomized process giving us shortest path metric instances.
In dieser Thesis versuchen wir die Frage zu beantworten, warum allgemein vermutet wird dass bestimmte Polynome keine kleinen arithmetischen Schaltkreise haben. Wir untersuchen dieses Problem in drei verschiedene Richtungen. Erstens, untersuchen wir nicht kommutative Berechnungen. Wir zeigen hier, obere und untere Schranken für die nicht kommutative Permanente auf verschiedenen eingeschränkten Graphen. Unser Hauptresultat zeigt Schranken für Graphen mit Komponenten der Größe höchstens 6 sowie ein #P-härte Resultat. Wir führen ein Maß ein, dass die Komplexität solcher Instanzen charakterisiert. Zweitens, führen wir ein neue theoretischen Rahmen für arithmetische Schaltkreise ein, ähnlich der parametrisierten Komplexität. Dieses zeigt das bestimmte Polynome die auf Graphproblemen basieren, die erwartete Komplexität haben. Die von uns eingeführten Klassen sind ähnlich zu der boolschen Situation und benutzen die Kraft der arithmetischen Schaltkreise kaum. Um dies zu beheben führen wir Klassen VW[t] ein, die modifizierte Probleme beinhalten. Drittens, untersuchen wir Polynome definiert durch Graphhomomorphismen und beweisen Dichotomie Theoreme die zeigen, dass selbst Restriktionen auf den Graphen uns harte Instanzen geben. Zum Schluss weichen wir von unserem roten Faden ab und untersuchen einfache Heuristiken auf metrischen Graphen. Anstatt eine bestimmte Metrik zu untersuchen, schauen wir uns einen randomisierten Prozess an der uns eine kürzeste Pfade Metrik erzeugt.
Link to this record: urn:nbn:de:bsz:291-scidok-64387
hdl:20.500.11880/26703
http://dx.doi.org/10.22028/D291-26647
Advisor: Bläser, Markus
Date of oral examination: 27-Jan-2016
Date of registration: 1-Apr-2016
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 
thesis.pdf1,69 MBAdobe PDFView/Open


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