SUBSCRIBE tárgyú levéllel lehet. Érdemes
feliratkozni, minden alkalom előtt szétküldjük az absztaktot!
"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.
"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.
"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ó.
"Leszámolások és mintavételezések bonyolultságelmélete"
Valiant, Jerrum-Valiant-Vazirani,
Jerrum-Sinclair cikkek alapján.
Az alábbi cikkek eredményeiről adunk áttekintést:
"A permanens számolás bonyolultsága" -
Leslie Valiant cikke
"Megbízhatósági és enumerációs problémák bonyolultsága" -
Leslie Valiant cikke
"Kombinatorikus struktúrák mintavételezése egyenletes eloszlásból" -
Mark Jerrum, Leslie Valiant és Vijay Vazirani cikke
"Közelítő leszámolás, egyenletes generálás és gyorsan konvergáló Markov láncok"
- Mark Jerrum és Alastair Sinclair cikke
Egy bevezető, de átfogó előadást tartok a leszámolások és mintavételezések bonyolultságának az elméletéről. Ismertetésre kerülnek a #P, #P-teljes, FPRAS és FPAUS osztályok, valamint az önhasonló leszámolási problémák, melyeknek a közel egyenletes mintavételezésének és közelítő leszámolásának a bonyolultsága azonos. A megadott négy cikk alapvető fontosságú a témában, de más cikkekről is fogok beszélni.