Contributions to structural communication complexity [Elektronische Ressource] / von Henning Wunderlich
91
pages
English
Documents
2009
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
91
pages
English
Documents
2009
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
Publié par
Publié le
01 janvier 2009
Nombre de lectures
20
Langue
English
Contributions to Structural Communication ComplexityContributions toStructural CommunicationComplexityDissertation zur Erlangung des akademischen GradesDoctor rerum naturalium (Dr. rer. nat.)vorgelegt der Fakultät für Informatik und Automatisierungder Technischen Universität IlmenauvonDipl.-Inf. Henning WunderlichVorgelegt am: 25.05.2009Gutachter:1. Univ.-Prof. Dr.(USA) habil. Martin Dietzfelbinger,Technische Universität Ilmenau2. Univ.-Prof. Dr. rer. nat. habil. Georg Schnitger,Goethe-Universität Frankfurt3. Univ.-Prof. Dr. rer. nat. habil. Uwe Schöning,Universität Ulmurn:nbn:de:gbv:ilm1-2009000312Copyrightc 2009 by Henning Wunderlichdedicated to Siegrid SyguschContents1 Summary 11.1 Information complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Structural communication complexity . . . . . . . . . . . . . . . . . . . 11.3 Cover-structure graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 Preliminaries 33 Communication complexity 53.1 Yao’s model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53.1.1 Deterministic protocols . . . . . . . . . . . . . . . . . . . . . . . 53.1.2 Randomized protocols . . . . . . . . . . . . . . . . . . . . . . . . 93.1.3 Counting protocols . . . . . . . . . . . . . . . . . . . . . . . . . . 123.1.4 Alternating protocols . . . . . . . . . . . . . . . . . . . . . . . . 153.2 Covers and partitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153.
Voir
Contributions to Structural Communication Complexity
Contributions to Structural Communication Complexity
Dissertation zur Erlangung des akademischen Grades Doctor rerum naturalium (Dr. rer. nat.)
vorgelegt der Fakultät für Informatik und Automatisierung der Technischen Universität Ilmenau
Vorgelegt am:
Dipl.-Inf.
25.05.2009
von
Henning Wunderlich
Gutachter: 1. Univ.-Prof. Dr.(USA) habil. Martin Dietzfelbinger, Technische Universität Ilmenau 2. Univ.-Prof. Dr. rer. nat. habil. Georg Schnitger, Goethe-Universität Frankfurt 3. Univ.-Prof. Dr. rer. nat. habil. Uwe Schöning, Universität Ulm
urn:nbn:de:gbv:ilm1-2009000312
Copyright by Henning Wunderlichc 2009
dedicated to Siegrid Sygusch
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . .
21 21 22 26 27
3
Information complexity 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Average case deterministic information complexity . . . . . . . . . . . 4.3 Lower bounds for public coin Las Vegas communication complexity . . 4.4 Concluding remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
Structural communication complexity 5.1 Introduction . . . . . . . . . . . . . . . . 5.2 Complexity class operators . . . . . . . 5.3 Valiant-Vazirani-Lemma . . . . . . . . . 5.4 A protocol with few alternations forIP. 5.5 Toda’s Theorems . . . . . . . . . . . . . 5.6 Approximate rank . . . . . . . . . . . . 5.7 Matrix rigidity . . . . . . . . . . . . . . 5.8 Quasi-random graphs . . . . . . . . . . . 5.8.1 Basic definitions . . . . . . . . . 5.8.2 Almost superregular problems . . 5.8.3 Lower bounds . . . . . . . . . . . 5.9 Concluding remarks . . . . . . . . . . .
. . . . . . . . . . . .
1 Summary 1.1 Information complexity . 1.2 Structural communication 1.3 Cover-structure graphs . .
. . . . . . complexity . . . . . .
. .
. . .
5 5 5 9 12 15 15 17 17 18 18
Communication complexity 3.1 Yao’s model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.1 Deterministic protocols . . . . . . . . . . . . . . . . . . . . . . . 3.1.2 Randomized protocols . . . . . . . . . . . . . . . . . . . . . . . . 3.1.3 Counting protocols . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.4 Alternating protocols . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Covers and partitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Lower bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.1 Rectangle size method . . . . . . . . . . . . . . . . . . . . . . . . 3.3.2 Lower bound methods for randomized communication complexity 3.3.3 Rank method . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
Preliminaries
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
1 1 1 2
. . .
. . .
. . . . . . . . . . . .
29 29 32 36 37 38 41 43 45 45 46 48 49
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
Cover-structure graphs 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . 6.1.1 Cover-structure graphs . . . . . . . . . . . 6.1.2 Perfect graphs . . . . . . . . . . . . . . . 6.1.3 A problem in communication complexity . 6.2 Cover-structure graphs . . . . . . . . . . . . . . . 6.2.1 Definition and easy observations . . . . . 6.2.2 Graphs that are not cs-graphs . . . . . . .
. . . . . . .
5
51 51 51 51 52 52 52 53
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
4
6
vii
Contents
3
viii
6.3
6.4
Beautiful graphs . . . . . . . . . . . . . . . . . . . . . . . . . 6.3.1 All square-free bipartite graphs are beautiful . . . . . 6.3.2 Characterization of beautiful line graphs of square-free graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . Concluding remarks . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . bipartite . . . . . . . . . .
. .
. .
57 58
58 64
List
6.2.1 6.2.2 6.2.3 6.3.1 6.3.2
of
Figures
Representation of an even cycleC2n, Cross and spade situations . . . . . . Gem, watch and star . . . . . . . . . Path-or-Even-Cycle-of-Clique graphs Representation of a cycle of cliques .
n . . . .
≥ . . . .
3 . . . .
. . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
54 54 55 61 62
ix
x
Tables
of
xi
29 30 30
. . .
.
. . .
.
Standard inclusions . . . . . . . Unknown inclusion relationships Known inclusion relationships .
List
5.1.1 5.1.2 5.1.3
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
.
classes
.
.
.
.
.
.
. . .
. . .
. . .
. . .
Comparisons
6.3.1
graph
of
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
58
.
