Contributions to structural communication complexity [Elektronische Ressource] / von Henning Wunderlich

Description

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.

Sujets

• Informatik

Informations

• Publié par: technische_universitat_ilmenau
• Publié le: 01 janvier 2009
• Nombre de lectures: 20
• Langue: English

Extrait

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 Wunderlich c 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 cycleC 2n , 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

.