Bonyolultságelmélet szeminárium

2018 Tavasz

Vezetők: 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 (II. 28.) Pálvölgyi Dömötör

"PPA és PPAD update"

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

Többek között ide tartozik a SPERNER, a BORSUK-ULAM, a NASH, eps-GCIRCUIT, NECKLACE SPLITTING és még sok más fontos keresési probléma. Azóta fény derült pár hibára az eredeti cikkben és született pár új pozitív eredmény is. Ezeket fogjuk áttekinteni mindenki számára érthető módon, tehát az alapdefinícióktól kezdve.


TERV:

2. alkalom (IV. 18.) Antal Ádám

"A kvantumszínezés tulajdonságai"
Mancinska és Roberson cikke.

A gráfszínezések egy jól ismert terület a gráfelméletben. Eredetileg interaktív protokollon keresztül értelmezett kvantum analogonja a kvantumkromatikus szám - a cikk ezt a témát járja körbe.

Jelenleg nem ismert algoritmus ami nemtriviális kvantumszínezést adna egy gráfhoz - a legtöbb ismert algoritmus a gráf d-dimenziós ortogonális reprezentációján alapul. Ez igen limitált hozzáállás, mivel a gráf ortogonális rangja és a kvantum kromatikus szám között nem feltétlenül van kapcsolat, erre példákat is fogunk látni.

Egy nemrég felfedezett példa demonstrál majd ehhez hasonló jelenségeket: például ha a gráfhoz egy új csúcsot adunk, amit minden korábbival összekötünk, akkor nem biztos, hogy nő a kvantum-kromatikus száma a gráfnak, továbbá ez a gráf a legkisebb tanú, hogy a kvantum és a klasszikus kromatikus szám nem mindig egyenlő.


3. alkalom (V. 2.) Kis Ágnes

"Turing-gépes algoritmusok titkosított adatokra"
Goldwasser, Kalai, Popa, Vaikuntanathan és Zeldovich cikke.

A titkosított adatokra szinte minden ismert kriptográfiai konstrukciót Turing gépek helyett áramkörökre modelleznek. Ennek hátrányai vannak a gyorsaságra nézve.

A cikk elsősorban arra irányul, hogy a polinomiális Turing gépekhez kriptográfiai sémákat konstruáljon, melyek futásideje jobb, például
1. ABE (attribútum-alapú titkosítás),
2. egy kulcsú (succint) FE (funkcionális titkosítás),
3. újrafelhasználható garbling séma,
4. és egy FHE (teljesen homomorf kódolási séma).

Ezután bizonyítjuk néhány jó tulajdonságát a fenti sémáknak, amelyek jobb teljesítményt eredményeznek, ezzel egyben két lehetőséget adva a felhasználóknak:
- elérhetik a legjobb teljesítményt, de ez szükségszerűen egy kevés információ kiszivárgásával jár,
VAGY
- csak egy kicsit gyorsabb algoritmust ad, ami cserébe nem kevésbé biztonságos, mintha áramköröket használnánk.



4. alkalom (V. 16.) Király Csaba

""
cikke.