SUBSCRIBE tárgyú levéllel lehet.
Cikkosztás.
"3 kérdéssel lokálisan visszafejthető kódok"
Efremenko cikke (2008).
Egy kódot lokálisan visszafejthetőnek nevezünk, ha a kódolt üzenet bármely bitjét konstans sok bit lekérdezésével meg tudjuk mondani, és ha a kód konstans része megsérül, akkor is nagy valószínűséggel jót mondunk.
Sokáig csak az üzenet n hosszában exponenciális méretű kód volt ismert. Yekhakin egy szintén 2008-as cikkében megadott egy szubexponenciális, 3 kérdéssel lokálisan visszafejthető kódot, viszont felhasználta hozzá azt a sejtést, hogy végtelen sok Mersenne-prím létezik.
A jelen cikk ehelyett Vince szuperpolinomiális, korlátozott metszetű halmazrendszerekről szóló 2000-es eredményén alapul, és rövidebb kódot is ad.
A konkrét korlátok:
3 kérdéssel exp(exp(O(sqrt(log n * log log n))))
2^r kérdéssel exp(exp(O(sqrt_r(log n * log log^{r-1} n))))
"Ha az NP nyelvek nehezek, akkor könnyű találni nehéz esetet"
Verescsagin cikke.
Az előadás során Nikolay Vereshchagin "Improving on Gutfreund, Shaltiel, and Ta-Shma's paper 'If NP Languages are Hard on the Worst-Case, Then it is Easy to Find Their Hard Instances' " című cikkét ismertetem. A szerző a cikk nagy részében a címben is jelölt másik dolgozat eredményeit ismerteti, a maradékban javítja azokat.
Tegyük fel, hogy NP nem egyenlő RP-vel. Gutfreund, Shaltiel és Ta-Shma bebizonyította, hogy minden randomizált polinom idejű D algoritmushoz, ami a SAT eldöntési feladatot próbálja megoldani, (azaz eldönteni egy formuláról, hogy kielégíthető-e) létezik polinom idejű eljárás, mely olyan formulát ad, amin D legalább 1/6-epszilon valószínűséggel hibázik. A cikkben a szerző ezt az valószínűséget 1/3-epszilonra javította.
A dolgozatban a SAT keresési változatáról is van szó: minden randomizált polinom idejű S algoritmushoz, ami a SAT keresési feladatot próbálja megoldani, (azaz egy formulának keresi egy jó kiértékelését) létezik polinom idejű eljárás, mely olyan formulát ad, amin S legalább 1-epszilon valószínűséggel hibázik (azaz kielégíthető a formula, mégsem talál kiértékelést).
"Lehet-e erősíteni a Valiant-Vazirani izolációs lemmát?"
Kabanets és Watanabe cikke.
Legyen F egy algoritmus, ami egy n változós C Boole-hálózatból egy szintén n változós C' Boole-hálózatot generál. Azt mondjuk, hogy F egy izolációs algoritmus, ha minden C'=F(C) esetén
Az előadásban a Valiant-Vazirani lemma több természetes erősítését fogjuk vizsgálni, és megmutatjuk, hogy ezek léte a polinomiális hierarchia összeeséseihez vezetne. Belátjuk, hogy pontosan akkor létezik P/poly-ban kiszámítható determinisztikus izoláció, ha NP\subseteq P/poly. Egy másik fő eredmény szerint pedig \delta>2/3 valószínűségű randomizált izoláció léte azt implikálná, hogy co-NP\subseteq NP/poly. Fogunk még beszélni olyan izolációról is, melyben megengedjük, hogy az outputnak több változója legyen, mint az inputnak. Végül egy általánosabb szituációt vizsgálunk, amikor {0,1}^n részhalmazaiból akarunk izolálni egy-egy elemet, ebben az esetben be fogjuk látni, hogy a sikeres izoláció átlagos valószínűsége O(1/n), amit a Valiant-Vazirani lemma el is ér.
"Az összeadás kommunikációs bonyolultsága"
E. Viola cikke.
Tegyük fel, hogy k játékos mindegyike tart a kezében egy n-bites x_i számot. El akarják dönteni, hogy összegük egyenlő-e egy adott s számmal. A cikk ad egy O(k log k) bit kommunikációt használó protokollt, ami 1% hibával hibával eldönti a kérdést, amennyiben adott egy mindenki által ismert véletlen sztring.
A modulo m esetben is használható a protokoll, és néhány m esetében a feladatra \Omega(k log k) alsó korlátot is igazolnak.
Szerepelni fog egy protokoll ami 1% hibával eldönti a \sum x_i>s kérdést O(k log k) log n bit kommunikációval. A 2 játékos esetében bizonyítok egy \Omega(log n)-es alsó korlátot.
Egy f:{0,1}^n-->{0,1} függvény d-edfokú polinomiális küszöbfüggvény, ha van olyan legfeljebb d-edfokú n változós p polinom, melyre f=sign(p). Ilyen függvények kiszámítására használjuk az előző protokollt abban az esetben, amikor minden játékos homokán van az input, azaz x_i mindenki számára ismert az i-edik játékost leszámítva.
"Nincs polinomiális méretű LP a TSP-re, a MAXCUT-ra és a MAXSTABIL-ra"
Fiorini, Massar, Pokutta, Tiwary és de Wolf cikke.
1986-87 körül azzal próbálták a P=NP-t bizonyítani, hogy polinomiális LP-t adnak az utazóügynök feladatra (TSP). Yannakakis 1988-ban bizonyította, hogy nincs polinomiális méretű szimmetrikus LP a TSP-hez. Cikkében megjegyzi, hogy a szimmetria szerinte nem sokat számít. Kaibel, Pashkovich és Theis 2010-ben bizonyították, hogy van olyan politóp, melyre nincs polinomiális méretű szimmetrikus LP, de van polinomiális méretű LP.
Belátjuk, hogy a TSP-re adható összes LP szuperpolinomiális méretű, legalább Omega(2^{n/4}) egyenlőtlenségből áll. Sőt további alsó korlátot adunk a vágás politópra és a stabil halmaz politópra adható egyenlőtlenségek minimális számára.
A bizonyításhoz bemutatunk egy új kapcsolatot az LP-k szemidefinit programmozási átirata és az egyirányú kvantum kommunikációs protokollok közt.
""
cikke.