Bonyolultságelmélet szeminárium

2021 Tavasz

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

Minden második héten, Szerda 10:15-13:00
TEAMS


Hirdetmények


1. alkalom (II. 17.) Kun Gábor

"Expander spanning subgraphs with large girth"

We conjecture that finite graphs with positive Cheeger constant admit a spanning subgraph with positive Cheeger constant and girth proportional to the diameter. We prove this conjecture for regular expander graphs with large expansion. Our proof relies on the Local Lemma. Joint work with Benjamini and Fraczyk.

Az előadás magyarul lesz!


2. alkalom (II. 24.)

"A kiosztott cikk megbeszélése"
Papadimitriou cikke.

A "On the complexity of the parity argument and other inefficient proofs of existence" című 1994-es cikk átbeszélése. Utána cikkosztás!


3. alkalom (III. 17.) Csáji Gergely

"Az End-of-Line probléma általánosításai és bonyolultságuk"
Hollender és Goldberg cikke.

Az előadásomat Alexandros Hollender és Paul W. Goldberg, "The Complexity of Multi-source Variants of the End-of-Line Problem, and the Concise Mutilated Chessboard" című cikkéből tartom. Az előadás fő témája a PPAD-teljes End-of-Line probléma különböző általánosításainak és ezek bonyolultságának vizsgálata lesz. Az End-of-Line probléma a következő: Adott egy G irányított gráf, ahol minden csúcs befoka és kifoka is legfeljebb 1, továbbá adott egy forrás. A feladatunk egy másik forrás/nyelő keresése. Az előadás során ennek több verziójával is fogunk foglalkozni, például amikor több forrás és több nyelő is adott, vagy amikor több forrást/nyelőt kell keresnünk, illetve belátjuk ezekről is, hogy PPAD-teljesek.


4. alkalom (III. 24.) Pituk Sára

"Mennyire nehéz Tarski-fixpontot találni?"
Etessami, Papadimitriou, Rubinstein és Yannakakis cikke.

Tarski tétele egy fixponttétel, aminek fontos szerepe van a közgazdasági játékok elméletében, például ez a tétel garantálja a Nash-egyensúly létezését szupermoduláris játékokban. A tétel szerint ha adott egy f monoton növő függvény, ami a {1,2,...,N}^d rácsból önmagába képez, akkor f-nek van fixpontja. Ez rögtön látszik, ha tekintjük az 1, f(1), f(f(1), ... sorozatot, ami a monotonitás miatt legfeljebb dN lépésben stabilizálódik, vagyis ezt algoritmusként használva O(dN) lépésben tudunk találni egy Tarski-fixpontot. Ennél gyorsabb algoritmusok is ismertek, legutóbb Fearnley és Savani adott egy O((logN)^(d-1)) idejűt. Etessami és szerzőtársai a Tarski-fixpont keresésének bonyolultságát vizsgálták, és megmutatták, hogy a probléma benne van a PLS és a PPAD osztályok metszetében.


TERV:

5. alkalom (IV. 7.) Andó Szabolcs

"2-D Tucker PPA-teljes"
Aisenberg, Bonet és Buss cikke

Az előadás Aisenberg, Bonet és Buss: "2-D Tucker is PPA complete" című cikkét dolgozza fel. Tucker lemmája a híres Borsuk-Ulam topológiai tétel kombinatorikus változata. Az ehhez kapcsolódó számítási feladatról már Papadimitriou 1992-ben belátta, hogy a PPA bonyolultsági osztályban van. Ugyanebben a cikkben azt is állította, hogy a PPA-nál szűkebb PPAD osztálynak is tagja, ez azonban téves volt. Az előadás nagy részében megnézzük annak a bizonyítását, hogy 2-D Tucker PPA-nehéz, ezután megvizsgáljuk, hogy PPA-ban található, vagyis összefoglalva PPA-teljes. Ennek során arra is kitérünk, hogy miért nem működik a fenti gondolatmenet arra, hogy Tucker PPAD-ben lenne.