Název: Kombinatorický Gap Label Cover
Překlad názvu: Combinatorial Gap Label Cover
Autoři: Bialas, Filip ; Barto, Libor (vedoucí práce) ; Kompatscher, Michael (oponent)
Typ dokumentu: Diplomové práce
Rok: 2022
Jazyk: eng
Abstrakt: [eng] [cze]
Theorems about probabilistically checkable proofs (PCP) are famous hard-to-prove results from the theoretical computer science. They provide constructions of PCP sys- tems with interesting surprising properties and serve as a starting point for proofs of NP-hardness of many approximation problems. Recently, a weaker combinatorial version of one of these theorems (Gap Label Cover) was proved using only combinatorial tools. After summarizing the main results in the classical PCP theory, I explore the combina- torial version thoroughly. Original results of this thesis consist of counterexamples to the expected behavior of two concepts from the classical theory in the combinatorial setting - probabilistic version and parallel repetition. 1 Věty o pravděpodobnostně ověřitelných důkazech (PCP) jsou známé těžké výsledky z teoretické informatiky. Konstruují pravděpodobnostně ověřitelné důkazové systémy se zajímavými a překvapivými vlastnostmi a jsou využívány k důkazům NP-těžkosti mnoha aproximačních problémů. Slabší kombinatorická verze jedné z vět této teorie (Gap La- bel Cover) byla nedávno dokázána s použitím pouze kombinarických postupů. Po shrnutí hlavních výsledků klasické PCP teorie se důkladně zaobírám touto kombinatorickou verzí. Originálními výsledky této práce jsou protipříklady k očekávanému chování dvou kon- ceptů z klasické teorie v kombinatorickém světě - pravděpodobnostní verze a paralelního opakování. 1
Klíčová slova: PCP|paralelní opakování|kombinatorický|Gap Label Cover; PCP|Parallel Repetition|Combinatorial|Gap Label Cover

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/175477

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-508839


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Diplomové práce