3rd workshop of the Center for Foundations of Modern Computer Science

3. workshop Centra základů moderní informatiky

The third workshop of the Center for Foundations of Modern Computer Science took place on Monday June 10, 2019, in Prague as a part of STTI 2019.

Abstracts

Pavel Hubáček: Implikace bezpečnosti Fiatovy-Shamirovy heuristiky pro hledání Nashova equilibria

Fiatova-Shamirova heuristika transformuje interaktivní důkazové systémy s veřejnými náhodnými bity (public-coin) na neinteraktivní argumenty nahrazením ověřovatelových zpráv výstupem kryptografické hašovací funkce vyhodnocené na aktuálním transkriptu protokolu. Konstrukce hašovacích funkcí, pro které by byla tato transformace dokazatelně bezpečná je centrálním otevřeným problémem teoretické kryptografie.

V mé přednášce ukáži, že pokud je Fiatova-Shamirova heuristika bezpečná při použití na specifický standardní interaktivní protokol, pak libovolný výpočetně obtížný problém ve třídě #P indukuje distribuci výpočetně obtížných problémů ve třídě CLS; speciálně také pro problém nalezení Nashova equilibria.

Hlavní technickou částí našeho výsledku je inkrementálně ověřitelná procedura, která umožňuje nalézt počet splňujících ohodnocení pro SAT instance s $n$ proměnnými. Naše procedura provádí exponenciální počet kroků, kde každý jednotlivý krok je efektivní (tj. běží v polynomiálním čase v n). Inkrementální ověřitelnost zaručuje, že každý jednotlivý krok obsahuje důkaz korektnosti výpočtu, jenž lze efektivně ověřit a také efektivně transformovat na důkaz pro následující krok výpočtu.

Společná práce s A. R. Choudhurim, C.Kamathem, K.Pietrzakem, A.Rosenem a G.N.Rothblumem.

Martin Koutecký: Algoritmicka teorie celočíselného programování

Teorie celočíselného programování v omezené dimenzi se rozvíjí již od 80. let 20. století na základě technik a idejí z teorie čísel. Pomocí zcela jiných technik a idejí rozvineme teorii celočíselného programování v proměnné dimenzi, která zobecňuje a sjednocuje téměř dvě dekády předchozích výsledků. Naše hlavní věta říká, že celočíselné programy se separovatelně konvexní účelovou funkcí lze vyřešit v čase g(a,d) poly(n) pro vyčíslitelnou funkci g, kde n je dimenze programu, a je největší absolutní hodnota koeficientu matice omezujících podmínek, a d je minimum mezi primární a duální stromovou hloubkou matice A. Stromová hloubka je zásadní pojem z teorie řidkých grafů a zachycuje jistou kombinatorickou složitost matice A. Naše výsledky jsou v jistém smyslu ``těsné'': nelze je zobecnit na jiné účelové funkce, nelze odstranit závislost na koeficientech matice, a stromová hloubka nelze nahradit obecnější stromovou šířkou.

Klíčový pojem naší teorie je Graverova báze, která představuje množinu "elementárních'' zlepšujících kroků. Dalšími ingrediencemi jsou horní odhady na normy prvků Graverovy báze, dynamické programy pro výpočet prvků Graverovy báze, nové věty o blízkosti řešení zlomkové relaxace k celočíselným optimům, či silnější odhady na ekvivalentní účelové funkce. Tyto nástroje nám též umožňují zkonstruovat téměř lineární a silně polynomiální algoritmy.

Společná práce s Friedrichem Eisenbrandem, Christophem Hunkenschröderem, Kim-Manuelem Kleinem, Asafem Levinem a Shmuelem Onnem.

Tereza Klimošová: Vnoření náhodného bipartitního grafu do náhodného biregulárního grafu

Náhodný bipartitní graf G(n_1,n_2,m) je graf vybraný uniformně náhodně ze všech bipartitních grafů s partitami velikostí n_1 a n_2 a s m hranami. Náhodný biregulární bipartitní graf R(n_1,n_2,p) je graf uniformně náhodně vybraný ze všech bipartitních grafů s partitami velikostí n_1 a n_2, přičemž všechny vrcholy první partity mají stupeň pn_2 a všechny vrcholy druhé partity mají stupeň pn_1. Ukazujeme, že pro každé p\in (0,1) existuje \gamma=o(1) takové, že G(n_1,n_2,m) lze vnořit do R(n_1,n_2,p) pro m=\lfloor (1-\gamma)pn_1n_2\rfloor.

Společná práce s Christianem Reiherem, Andrzejem Rucinskim a Matasem Šileikisem.