Bonyolultságelmélet szeminárium

2014 Tavasz

Vezetők: Grolmusz Vince, Friedl Katalin, Pálvölgyi Dömötör, Király Zoltán

Minden második héten, Szerda 10:15-13:00
Pázmány Péter sétány 1/C. 3.607


Hirdetmények


Ajánlott irodalom


1. alkalom (II. 19.) CIKKOSZTÁS


2. alkalom (III. 5.) Mészáros András

"Yao-Hastad tétel"

Fő célunk annak megmutatása lesz, hogy a paritás nem számítható ki konstans mélységű polinomiális méretű hálózattal. (Vagy, hogy minél jobb alsó korlátot adjunk egy konstans mélységű hálózat méretére.)

Az egyik fontos ötlet az, hogy az alsó két szint kapuit cseréljük meg valahogy anélkül, hogy a méret nagyon nőne. Ha a csere előtt a 2. szinten ÉS kapuk voltak, akkor a csere után VAGY kapuk lesznek, így a 2. és a 3. szint VAGY kapui összeolvaszthatóak, így csökken a szintek száma.

Egy ilyen megcserélés általában exponenciálisan felnövelheti a kapuk számát. Azonban, ha néhány változónak lefixáljuk az értékét, akkor lehet, hogy már végrehajtható a csere jelentős méretnövekedés nélkül, persze az is kell, hogy elég sok szabad változónk maradjon. Ilyen jó megszorításnak a létét véletlen módszerrel fogjuk megmutatni. Mindennek azért tudjuk majd hasznát venni, mert a paritás megszorítása is paritás vagy annak negáltja.


3. alkalom (III. 19.) Kisfaludi-Bak Sándor

"Razborov-féle exponenciális alsó becslések többségre, paritásra és klikkre"

Az előadáson áttekintjük Razborov 80-as évek második felében publikált alsó becslési módszereit, illetve ezek több szerző által javított változait Boole-hálózatok méretére. Először a többség és paritás feladatokra adott módszert vizsgáljuk: látni fogjuk, hogy bizonyos nehezen számítható függvényeket - PARITY ill MOD_3 - kapuként megengedve is exponenciális méretű hálózat kell a kiszámoláshoz (konstans mélység esetén).

Ezután rátérünk a monoton Boole-függvényekre és Boole-hálózatokra. Az (n,k)-klikk feladatban az input egy n csúcsú gráf adjacencia mátrixa, és a válasz 1, ha a gráf tartalmaz k méretű klikket. Belátjuk, hogy k


4. alkalom (IV. 2.) Tóthmérész Lilla

"Kriptogenográfia"
Brody, Jakobsen, Scheder és Winkler cikke.

A kriptográfia klasszikus kérdése hogy hogyan tud néhány játékos úgy kommunikálni, hogy ők megtudják az egyikük által ismert titkot, de egy hallgatózó fél ne tudja meg. A cikk egy új típusú (de szintén a való élet által motivált) kérdést tesz fel: Tudnak-e a játékosok úgy kommunikálni, hogy mindnyájan megtudják a titkot, de egy hallgatózó fél ne tudja kitalálni hogy ki volt eredetileg a titok őrzője. Azaz szeretnénk titokban tartani hogy ki szivárogtatta ki a titkot. (És hogy a hallgatózó fél megtudja-e a titkot magát, azzal nem is foglalkozunk.) A cikk protokollokat mutat, aminek segítségével 2 játékos esetén a hallgatózó fél 1/3 eséllyel hibásan tippel a kiszivárogtató személyére, több játékos esetén pedig 0.5644 valószínűséggel. Másrészt megmutatják, hogy 2 játékos esetén az ellenséget nem lehet 3/8 -nál nagyobb valószínűséggel hibára kényszeríteni, és több játékos esetén pedig 3/4-nél nagyobbra.


TERV:


5. alkalom (IV. 23.) Pálvölgyi Dömötör

"Gyenge Paritás"
Aaronson, Ambainis, Balodis és Bavarian cikke.


6. alkalom (V. 7.) Király Csaba

"Lokális redukció"
Jahanjou, Miles és Viola cikke.