A következő szeminárium helye a Szőkefalvi-Nagy terem. Ideje

Október 3. (péntek), !!! 10:45 !!!

(a pesti vonat esetleg egy kicsit beleszól)

Tardos Gábor (Rényi Intézet): Kommunikációs komplexitás, kis halmazok diszjunktsága

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.

Minden érdeklődőt szeretettel várunk,

Péter

Supported by TÁMOP-4.2.2.A-11/1/KONV-2012-0073 projekt, "Telemedicina fókuszú kutatások Orvosi, Matematikai és Informatikai tudományterületeken"