Why are certain polynomials hard? : A look at non-commutative, parameterized and homomorphism polynomials

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.