In der Dissertation werden strukturelle Probleme in YaosKommunikationsmodell untersucht, die sich thematisch dreiBereichen dieses Gebietes zuordnen lassen:Der erste Teil der Arbeit beschäftigt sich mit dem fundamentalenProblem der Herleitung unterer Schranken für die randomisierteKommunikationskomplexität. Hauptergebnis ist die folgendeCharakterisierung, die auch als nicht-triviale Verallgemeinerungvon Shannons "Noiseless Coding Theorem" angesehen werden kann:die durchschnittliche deterministische Informationskomplexitätstimmt bis auf einen konstanten Faktor mit der durchschnittlichendeterministischen Kommunikationskomplexität überein, und zwar fürjede Funktion und jede Verteilung auf den Eingaben.Ein weiteres Ergebnis sind untere Schranken für die public coinLas Vegas Kommunikationskomplexität, die um einen konstantenFaktor besser sind, als die bis dahin bekannten.Der zweite Teil beschäftigt sich mit der 30 Jahre altenPH-vs.-PSPACE-Frage in der Kommunikationskomplexität. Wir übertragendazu die Todaschen Sätze aus der klassischen Komplexitätstheorie inYaos Modell und entwickeln ein Maß für die Klasse BP-Parität-P, denapproximativen GF(2)-Rang. Über eine enge Beziehung zu dem Konzept"matrix rigidity" erhalten wir ein Maßkonzentrationsresultat:die meisten Funktionen haben eine fast lineare BP-Parität-P-Komplexität.Wir entwickeln außerdem ein Protokoll für die innere Produktfunktionmod 2 mit wenigen Alternierungen. Dies könnte darauf hinweisen, dassdie Klasse BP-Parität-P "klein" ist im Vergleich zu PSPACE.Des Weiteren leiten wir für auf dünnen quasi-zufälligen Graphfamilienbasierenden Adjazenzproblemen eine hohe Parität-P-Komplexität her,die dem Logarithmus des Kehrwerts der Kantendichte entspricht.Im dritten Teil untersuchen wir Überdeckungsstrukturgraphen. Diesesind definiert als Schnittgraphen von maximalen monochromatischenUntermatrizen einer Matrix. Wir zeigen, dass nicht jeder Graph einÜberdeckungsstrukturgraph ist. Danach betrachten wir die Teilklasseder "schönen" Graphen und charakterisieren schöne quadratfreiebipartite und schöne Kantengraphen quadratfreier bipartiter Graphen.