edoc-Server der Humboldt-Universität zu Berlin

Dissertation

Autor(en): Kord Eickmeyer
Titel: Randomness in complexity theory and logics
Gutachter: Martin Grohe; Nicole Schweikardt; Peter Bro Miltersen
Erscheinungsdatum: 01.09.2011
Volltext: pdf (urn:nbn:de:kobv:11-100192373)
Fachgebiet(e): Informatik
Schlagwörter (ger): Randomisierung, deskriptive Komplexitätstheorie, Derandomisierung, Logik, endliche Modelltheorie
Schlagwörter (eng): descriptive complexity theory, randomisation, derandmisation, logics, finite model theory
Einrichtung: Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II
Lizenz: Namensnennung - Keine kommerzielle Nutzung - Keine Bearbeitung (CC BY NC ND)
Zitationshinweis: Eickmeyer, Kord: Randomness in complexity theory and logics; Dissertation, Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II , publiziert am 01.09.2011, urn:nbn:de:kobv:11-100192373
Metadatenexport: Um den gesamten Metadatensatz im Endnote- oder Bibtex-Format zu speichern, klicken Sie bitte auf den entsprechenden Link. Endnote   Bibtex  
print on demand: Wenn Sie auf dieses Icon klicken, können Sie ein Druckexemplar dieser Publikation bestellen.
Diese Seite taggen: Diese Icons führen auf so genannte Social-Bookmark-Systeme, auf denen Sie Lesezeichen anlegen, persönliche Tags vergeben und Lesezeichen anderer Nutzer ansehen können.
  • connotea
  • del.icio.us
  • Furl
  • RawSugar

Abstract (ger):
Die vorliegende Dissertation besteht aus zwei Teilen, deren gemeinsames Thema in der Frage besteht, wie mächtig Zufall als Berechnungsressource ist. Im ersten Teil beschäftigen wir uns mit zufälligen Strukturen, die -- mit hoher Wahrscheinlichkeit -- Eigenschaften haben können, die von Computeralgorithmen genutzt werden können. In zwei konkreten Fällen geben wir bis dahin unbekannte deterministische Konstruktionen solcher Strukturen: Wir derandomisieren eine randomisierte Reduktion von Alekhnovich und Razborov, indem wir bestimmte unbalancierte bipartite Expandergraphen konstruieren, und wir geben eine Reduktion von einem Problem über bipartite Graphen auf das Problem, den minmax-Wert in Dreipersonenspielen zu berechnen. Im zweiten Teil untersuchen wir die Ausdrucksstärke verschiedener Logiken, wenn sie durch zufällige Relationssymbole angereichert werden. Unser Ziel ist es, Techniken aus der deskriptiven Komplexitätstheorie für die Untersuchung randomisierter Komplexitätsklassen nutzbar zu machen, und tatsächlich können wir zeigen, dass unsere randomisierten Logiken randomisierte Komlexitätsklassen einfangen, die in der Komplexitätstheorie untersucht werden. Unter Benutzung starker Ergebnisse über die Logik erster Stufe und die Berechnungsstärke von Schaltkreisen beschränkter Tiefe geben wir sowohl positive als auch negative Derandomisierungsergebnisse für unsere Logiken. Auf der negativen Seite zeigen wir, dass randomisierte erststufige Logik gegenüber normaler erststufiger Logik an Ausdrucksstärke gewinnt, sogar auf Strukturen mit einer eingebauten Additionsrelation. Außerdem ist sie nicht auf geordneten Strukturen in monadischer zweitstufiger Logik enthalten, und auch nicht in infinitärer Zähllogik auf beliebigen Strukturen. Auf der positiven Seite zeigen wir, dass randomisierte erststufige Logik auf Strukturen mit einem unären Vokabular derandomisiert werden kann und auf additiven Strukturen in monadischer Logik zweiter Stufe enthalten ist.
Abstract (eng):
This thesis is comprised of two main parts whose common theme is the question of how powerful randomness as a computational resource is. In the first part we deal with random structures which possess -- with high probability -- properties than can be exploited by computer algorithms. We then give two new deterministic constructions for such structures: We derandomise a randomised reduction due to Alekhnovich and Razborov by constructing certain unbalanced bipartite expander graphs, and we give a reduction from a problem concerning bipartite graphs to the problem of computing the minmax-value in three-player games. In the second part we study the expressive power of various logics when they are enriched by random relation symbols. Our goal is to bridge techniques from descriptive complexity with the study of randomised complexity classes, and indeed we show that our randomised logics do capture complexity classes under study in complexity theory. Using strong results on the expressive power of first-order logic and the computational power of bounded-depth circuits, we give both positive and negative derandomisation results for our logics. On the negative side, we show that randomised first-order logic gains expressive power over standard first-order logic even on structures with a built-in addition relation. Furthermore, it is not contained in monadic second-order logic on ordered structures, nor in infinitary counting logic on arbitrary structures. On the positive side, we show that randomised first-order logic can be derandomised on structures with a unary vocabulary and is contained in monadic second-order logic on additive structures.
Zugriffsstatistik: Die Daten für die Zugriffsstatistik der einzelnen Dokumente wurden aus den durch AWStats aggregierten Webserver-Logs erstellt. Sie beziehen sich auf den monatlichen Zugriff auf den Volltext sowie auf die Startseite. Die Zugriffsstatistik wird nicht standardisiert erfasst und kann maschinelle Zugriffe enthalten.
 
Bei Formatversionen eines Dokuments, die aus mehreren Dateien bestehen (insbesondere HTML), wird jeweils der monatlich höchste Zugriffswert auf eine der Dateien (Kapitel) des Dokuments angezeigt.
 
Um die detaillierten Zugriffszahlen zu sehen, fahren Sie bitte mit dem Mauszeiger über die einzelnen Balken des Diagramms.
Startseite: 1 Zugriffe PDF: 4 Zugriffe Startseite: 3 Zugriffe PDF: 4 Zugriffe PDF: 9 Zugriffe PDF: 14 Zugriffe PDF: 13 Zugriffe PDF: 13 Zugriffe PDF: 16 Zugriffe Startseite: 3 Zugriffe PDF: 14 Zugriffe PDF: 8 Zugriffe PDF: 7 Zugriffe PDF: 8 Zugriffe PDF: 10 Zugriffe PDF: 9 Zugriffe PDF: 24 Zugriffe Startseite: 2 Zugriffe PDF: 33 Zugriffe Startseite: 3 Zugriffe PDF: 28 Zugriffe Startseite: 3 Zugriffe PDF: 31 Zugriffe Startseite: 1 Zugriffe PDF: 23 Zugriffe Startseite: 1 Zugriffe PDF: 29 Zugriffe Startseite: 2 Zugriffe PDF: 21 Zugriffe Startseite: 6 Zugriffe PDF: 24 Zugriffe Startseite: 3 Zugriffe PDF: 12 Zugriffe Startseite: 5 Zugriffe PDF: 26 Zugriffe PDF: 18 Zugriffe Startseite: 1 Zugriffe PDF: 39 Zugriffe Startseite: 1 Zugriffe PDF: 33 Zugriffe PDF: 40 Zugriffe Startseite: 1 Zugriffe PDF: 62 Zugriffe PDF: 34 Zugriffe Startseite: 1 Zugriffe PDF: 23 Zugriffe Startseite: 3 Zugriffe PDF: 27 Zugriffe
Oct
11
Nov
11
Dec
11
Feb
12
Apr
12
May
12
Jun
12
Jul
12
Aug
12
Sep
12
Oct
12
Nov
12
Dec
12
Jan
13
Feb
13
Mar
13
Apr
13
May
13
Jun
13
Jul
13
Aug
13
Sep
13
Oct
13
Nov
13
Dec
13
Jan
14
Feb
14
Mar
14
Apr
14
May
14
Jun
14
Monat Oct
11
Nov
11
Dec
11
Feb
12
Apr
12
May
12
Jun
12
Jul
12
Aug
12
Sep
12
Oct
12
Nov
12
Dec
12
Jan
13
Feb
13
Mar
13
Apr
13
May
13
Jun
13
Jul
13
Aug
13
Sep
13
Oct
13
Nov
13
Dec
13
Jan
14
Feb
14
Mar
14
Apr
14
May
14
Jun
14
Startseite 1 3           3             2 3 3 1 1 2 6 3 5   1 1   1   1 3
PDF 4 4 9 14 13 13 16 14 8 7 8 10 9 24 33 28 31 23 29 21 24 12 26 18 39 33 40 62 34 23 27

Gesamtzahl der Zugriffe seit Oct 2011:

  • Startseite – 40 (1.29 pro Monat)
  • PDF – 656 (21.16 pro Monat)
 
 
Generiert am 10.07.2014, 08:26:33