11th workshop of the Center of Modern Computer Science
11. seminář Centra moderní informatiky
The seventh workshop of the Center of Modern Computer Science will take place on June 30—July 1, 2017 in the Mala Strana building.
Centrum moderní informatiky zve na sedmý seminář. Přednášky juniorů centra se konají v průběhu programu v pátek 30. června a sobotu 1. července 2017 v budově MFF UK na Malé Straně. Seminář se koná v rámci STTI 2017.
| Páteční přednášky | |
|---|---|
| 9:00 | Jan Kynčl: Jak naporcovat diskrétní kořeněné kuře |
| 14:00 | Pavel Hubáček: Kryptografické předpoklady a bariéry algoritmické teorie her |
| Sobotní přednášky | |
| 11:25 | Marek Krčál: Malware classification of executable files by deep nets |
Abstracts
Jan Kynčl: Jak naporcovat diskrétní kořeněné kuře
Mějme nk červených nebo modrých bodů v rovině v obecné poloze, od každé barvy aspoň n bodů. Ukážeme, že pak jdou tyto body rozdělit do n disjunktních konvexních množin tak, že každá obsahuje přesně k bodů, aspoň jeden červený a aspoň jeden modrý. Dokonce počty červených bodů v různých množinách rozkladu se budou lišit maximálně o 1.
Dále ukážeme, že pokud P je množina n(d+1) bodů v obecné poloze v R^d obarvená d barvami tak, že od každé barvy máme aspoň n bodů, pak existuje n disjunktních d-rozměrných simplexů s vrcholy v P takových, že každý obsahuje aspoň jeden bod od každé barvy.
Tyto výsledky se dají považovat za speciální případy diskrétní verze věty o kořeněném kuřeti. Zformulujeme hypotézu, která zobecňuje tuto diskrétní větu a dalších několik dřívějších výsledků týkajících se konvexních rozkladů barevných množin bodů.
Pavel Hubáček: Kryptografické předpoklady a bariéry algoritmické teorie her
Jedním z hlavních výsledků teorie her je Nashova věta, která zaručuje, že každá konečná hra má alespoň jedno rovnovážné řešení. Všechny důkazy této věty jsou však existenciální a žádný efektivní algoritmus pro nalezení takového řešení není momentálně znám. Vysvětlením tohoto stavu by bylo například vyloučení existence efektivních algoritmů pro řešení konečných her. Bitansky, Paneth a Rosen (FOCS'15) ukázali, že moderní kryptografické metody jako secure program obfuscation lze použít ke konstrukcím her, pro které dokazatelně nelze nalézt Nashovo rovnovážné řešení v polynomiálním čase. Tyto prvotní výsledky nabízejí přirozenou otázku, zda je možné dokázat obdobné výsledky za použití základních kryptografických předpokladů, jakým je například existence jednosměrných funkcí.
Ve své přednášce představím naše výsledky, které ilustrují souvislosti mezi výpočetní třídou TFNP (problémů, pro které řešení vždy existuje) a hierarchií kryptografických předpokladů od jednosměrných funkcí až po secure program obfuscation. Jako hlavní tvrzení ukáži, že existence náročných TFNP problémů vyplývá z existence distribucí NP problémů, které nelze řešit v polynomiálním čase.
Marek Krčál: Malware classification of executable files by deep nets
I give a concise overview of deep neural nets including some of their successful applications. Then I present preliminary results on how well can be deep nets trained in malware detection when supplied by Windows executable files without any domain-specific preprocessing or feature engineering.
