Bonyolultságelmélet szeminárium

2017 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


1. alkalom (III. 8.) Király Csaba

"Lokális expanderek"
Viola és Wigderson cikke.

Egy f:{0,1}^n->{0,1}^n leképezés lokalitása t, ha minden kimeneti bitje t input bittől függ. Arora, Steurer és Widgerson olyan expanderek létezéséről érdeklődött 2^n csúcson, melyben minden x {0,1}^n-beli csúcs szomszédai konstans lokalitással számolhatóak. A kérdést egy lokalitású gráfok explicit konstrukciójával oldjuk meg. Alkalmazásként veszteségmentes expandereket mutatunk konstans lokalitással, továbbá hatékonyabb hiba redukciót mutatunk randomizált algoritmusokra. Ezeken kívül olyan 3-reguláris Ramanujan gráfokra is adunk explicit konstrukciót, melyeknek 2(2^n-1) csúcsa van, ahol n=4*3^t alakú, és minden {0,1}^n-{0}^n-beli csúcs szomszédai konstans lokalitással számolható, vagy konstans időben Omega(n) hosszú szavakon végzett standard műveletekkel.


2. alkalom III. 29.) Papp László

"Gyors, polinomiális tárat használó randomizált algoritmusok a részhalmaz-összeg és hátizsák problémákra"
Bansal, Garg, Nederlof és Vyas cikke.

Nyitott kérdés, hogy a részhalmaz összeg és a hátizsák problémák megoldhatóak-e poly(n)*2^((1-eps)n) időben poly(n) tárhelyet használva. Jelen cikkben olyan Monte Carlo algoritmusokat mutatnak ezen problémák megoldására, melyek poly(n) darab tetszőlegesen hozzáférhető véletlen bitet, poly(n) tárat és poly(n)*2^0,86n lépést használnak.

Ehhez megmutatják, hogy egy gyorsan számolható véletlen függvényt fehasználva két darab pozitív egész számokat tartalmazó tömbről gyorsan el lehet dönteni, hogy tartalmaznak-e közös elemet, ha ugyanaz az elem kevésszer fordul elő a tömbökben, illetve egyik elem sem túl nagy a tömbök hosszához képest. Ezen eredmények felhasználásával kevés helyet használó randomizált algoritmusokat adnak a bináris programozásra és a k-sum problémára.


TERV:


3. alkalom IV. 19.) Tóthmérész Lilla

"Az izoláció derandomizálása"
Melkebeek és Prakriya cikke.

Izolációnak nevezik azt az eljárást, amikor egy sok megoldással rendelkező problémából egy megoldással rendelkezőt csinálunk. Ez sokszor hasznos dolog, például algebrai jellegű algoritmusoknál, ahol az egyetlen megoldás létezése megakadályozza hogy megoldások kiejtsék egymást, vagy párhuzamos algoritmusoknál, ahol az egy megoldás létezése biztosítja hogy minden futás ugyanazt a megoldást próbálja kiszámolni. Izolációt legegyszerűbben véletlen algoritmussal szoktak csinálni, például egy véletlen súlyfüggvényt rendelnek a problémához, majd e szerint minimális súlyú megoldást keresnek. A cikkben az irányított gráfokbeli elérhetőségi kérdés izolációjának derandomizációjáról van szó.


4. alkalom V. 3.) Miklós István

""
cikke.