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

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.