|
|
|
|
|
|
|
|||
| Év szerint | Hónap szerint | Ugrás a hónaphoz | |||||||
Tardos Gábor (Rényi Intézet): Kommunikációs komplexitás, kis halmazok diszjunktsága |
|
|||
|
|
||||
|
||||
| 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 | ||||
Esemény exportálása JEvents v3.1.8 Stable Copyright © 2006-2013
