Kommunikationskomplexität und Interaktive Kommunikation
| Vortragende(r): |
| Dr. Ulrich Tamm |
| Inhalt: |
| Kommunikationskomplexität ist die Anzahl Bits, die zwei Personen zur Berechnung einer Funktion f(x,y) austauschen müssen, wenn Person 1 nur das Argument x und Person 2 nur das Argument y kennt. Die Kommunikationskomplexität hat wichtige Anwendungen bei der Herleitung unterer Schranken zum verteilten Rechnen, VLSI-Layout und zur Schaltkreistiefe. Im Orlitski's Modell zur Interaktiven Kommunikation sind zusätzlich Einschränkungen an den Wertebereich gegeben. Ein wichtiges Hilfsmittel zur Herleitung unterer Schranken sind hier Färbungen von Hypergraphen. |
| Zeiten: |
| Mittwoch, der 15.05.2002, 11:00 Uhr, Raum 1/367A |
