Tardos Gábor (Rényi Intézet): Kommunikációs komplexitás, kis halmazok diszjunktsága |
|
|
|
Péntek, 3. Október 2014, 10:45 - 12:00
|
|
Absztrakt. A kommunikációs komplexitás rég óta használt bonyolultsági mérték. Eredményei remekül alkalmazhatóak az elméleti számítástudomány legkülönfélébb részein. Használható alsó becslések is vannak rá, nem úgy, mint a számítási bonyolultságra, de (főleg a véletlent használó modellben) távolról sincs minden fontos kérdés lezárva. Az előadás a témában leginkább vizsgált két probléma változatairól szól. Míg a halmaz-diszjunktság bonyolultsága már évtizedek óta ismert, a KIS halmazok diszjunktságára Hastad és Wigderson csak 2007-ben adott optimális hosszú véletlen protokolt. Mert Saglammal ezt tavaly tovább javítottuk optimális trade-offot elérve a hossz és az üzenetek száma között. Plusz a mi protokolunk nem csak a IGEN/NEM választ ad a diszjunktságra, hanem (minden extra költség nélkül) a két halmaz pontos metszetét találja meg. Egy meglepő következmény: korlátos üzenet-szám mellett n egyenlőség-teszthez (ez a másik leginkább vizsgált probléma kommunikációs komplexitásban) szigorúan több mint n-szer annyi kommunikáció kell, mint egyhez. |
Hely : Bolyai Intézet, Aradi Vértanúk tere, Szőkefalvi terem |
Vissza
JEvents v3.1.8 Stable
Copyright © 2006-2013