Activity of the research group:

Kombinatorikus algoritmusok. Klasszikus és kvantumalgoritmusok, bonyolultságelméleti és paraméteres bonyolultságos megközelítések. Ezen belül pl. társadalmi választások, fair hozzárendelések, stabil és népszerű párosítások, hálózatok megbízhatóságának vizsgálata kombinatorikus és játékelméleti módszerekkel. Különböző kvantumos megközelítések (algoritmus, QUBO, kvantumbolyongás) vizsgálata. Logikai és deklaratív programozás.

Recent results:

Számos eredményünk született a fair hozzárendelés területén: többek között bizonyítottuk, hogy 3 ágens esetén az irigység-mentes allokáció keresése NP-teljes feladat (ezzel egy 5 évig nyitott kérdést megválaszolva), ugyanakkor arányos allokáció keresése polinom idejű algoritmussal megoldható; ez utóbbi kérdést általános számú ágens esetén is körbejártuk, feltérképeztük annak paraméteres bonyolultságát és approximálhatóságát. Vizsgáltuk a stabil párosítás probléma sok-paraméteres bonyolultságát abban az esetben, ahol bizonyos ágensek fedését írhatjuk elő: öt vizsgált paraméter minden kombinációjára sikerült a probléma bonyolultságát meghatározni. Foglalkoztunk még a népszerű fenyvesek problémájával is, hatékony egzakt és közelítő algoritmusok megadása mellett számos nehézségi eredményt is bizonyítottunk. Bizonyítottunk egy olyan új eredményt, aminek segítségével a hálózatok megbízhatóságának játékelméleti eszközökkel való mérésére vonatkozó korábban ismert, matroidelméleti módszereket sikerült a greedoidoknak egy, a matroidoknál bővebb osztályára kiterjeszteni. Kvantumalgoritmusok körében vizsgáltuk a Fourier-transzformáció alkalmazásanak határait bizonyos algebrai feladatokra. Foglalkoztunk a kvantumalgoritmusok egy fajta használatával a gépi tanulásban, megmutatva, hogy egy mások által javasolt módszer nem sok előnyt ad a klasszikus eljárásokhoz képest. Vizsgáljuk, hogyan lehet klasszikus problémákat a D-Wave (korábbi) kvantumszámítógépébe beágyazni, az ott használt QUBO (quantum unconstrained binary optimization) feladatra átfordítani.

Recent projects:

OTKA

International relations:

Hamburg University of Technology • University of Tübingen • Université Paris Diderot - Paris, Centre for Quantum Technologies • University of Singapore