A következő szeminárium helye a Szőkefalvi-Nagy terem. Ideje
(a pesti vonat esetleg egy kicsit beleszól)
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"