Kommunikationskomplexität und Interaktive Kommunikation
| Talking persons: |
| Dr. Ulrich Tamm |
| Abstract: |
| 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. |
| Times: |
| Wednesday 15th May 2002, 11.00 am, room 1/367A |
