Témata prací (Výběr práce)Témata prací (Výběr práce)(verze: 336)
Detail práce
  
On the Complexity of Search Problems with a Unique Solution
Název práce v češtině: Složitost Vyhledávacích Problémů s Jednoznačným Řešením
Název v anglickém jazyce: On the Complexity of Search Problems with a Unique Solution
Klíčová slova: Black-Box Separace|Jednosměrné Funkce|TFNP|CLS|ARRIVAL
Klíčová slova anglicky: Black-Box Separations|One-Way Functions|TFNP|CLS|ARRIVAL
Akademický rok vypsání: 2016/2017
Typ práce: disertační práce
Jazyk práce: angličtina
Ústav: Informatický ústav Univerzity Karlovy (32-IUUK)
Vedoucí / školitel: Mgr. Pavel Hubáček, Ph.D.
Řešitel: skrytý - zadáno a potvrzeno stud. odd.
Datum přihlášení: 20.09.2017
Datum zadání: 20.09.2017
Datum potvrzení stud. oddělením: 05.10.2017
Datum a čas obhajoby: 25.08.2021 14:00
Datum odevzdání elektronické podoby:17.06.2021
Datum odevzdání tištěné podoby:29.05.2021
Datum proběhlé obhajoby: 25.08.2021
Oponenti: Christopher Brzuska
  Nir Bitansky
 
 
Zásady pro vypracování
Cílem práce je studium souvislostí mezi výpočetní složitostí strukturovaných problémů a kryptografickými předpoklady. Metody mohou zahrnovat konstrukce dolních odhadů pro totální problémy na základě kryptografických předpokladů či konstrukce středně težkých funkcí na základě strukturovaných problémů.

The goal of this thesis is to study the relationships between computational complexity of structured problems and various cryptographic assumptions. The methods might include constructions of lower bounds for total search problems based on general cryptographic assumptions or constructions of moderately hard functions based on structured problems.
Seznam odborné literatury
Aktuální konferenční a časopisecké články
 
Univerzita Karlova | Informační systém UK