Bonyolultságelmélet szeminárium

2016 Ősz

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


TERV:

1. alkalom (IX. 28.) Pálvölgyi Dömötör

"Bevezetés a PPA osztályba"

Papadimitriou 94-es cikkében számos új TFNP-beli (keresési) bonyolultsági osztályt definiált, melyekről itt lehet olvasni: https://complexityzoo.uwaterloo.ca/Complexity_Zoo:P#ppa

A legfontosabbnak a PPAD tűnt, kiderült, hogy PPAD-teljes a SPERNER, a BORSUK-ULAM, a NASH és még sok más fontos keresési probléma. Aztán tavaly kiderült, hogy a BORSUK-ULAM mégsem, mert az eredeti cikkbe csúszott egy kis hiba, ez így PPA-teljes lett. Most emiatt kicsit a PPA került előtérbe, egy friss eredmény alapján ebben van a faktorizáció is (ha igaz az általánosított RH).

Előadásom célja, hogy bemutassam az alapokat, majd a legújabb eredményeket a gráfokhoz kapcsolódó problémákról, például a 2D-SPERNER PPAD-teljességének bizonyítását. A 2D-SPERNER keresési feladatban egy 2^n x 2^n méretű rács csúcsai vannak három színnel színezve úgy, hogy a bal-alsó sarok 1-es, a többi alsó oldali pont 2-es és a többi oldalsó pont 3-as szinű. A keresési feladat egy, a Sperner-lemma által garantált, háromszínű kisnégyzet megkeresése. Ezután azt is megnézzük, hogy a 2D-TUCKER miért lesz viszont csak PPA-teljes, meg mondok pár nyitott kérdést.


2. alkalom (X. 12.) Aleksziev Rita

"Testing Equality in Communication Graphs"
Alon, Efremenko és Sudakov cikke.


3. alkalom (XI. 9.)

""
cikke.


4. alkalom (XI. 23.)

""
cikke.


5. alkalom (XII. 7.)

""
cikke.