Témata prací (Výběr práce)Témata prací (Výběr práce)(verze: 368)
Detail práce
   Přihlásit přes CAS
Constructions of Bounded-depth Superconcentrators
Název práce v češtině: Konstrukce superkoncentrátorů omezené hloubky
Název v anglickém jazyce: Constructions of Bounded-depth Superconcentrators
Klíčová slova: superkoncentrátory|expandery
Klíčová slova anglicky: superconcentrators|expanders
Akademický rok vypsání: 2021/2022
Typ práce: bakalářská práce
Jazyk práce: angličtina
Ústav: Informatický ústav Univerzity Karlovy (32-IUUK)
Vedoucí / školitel: prof. Mgr. Michal Koucký, Ph.D.
Řešitel: skrytý - zadáno a potvrzeno stud. odd.
Datum přihlášení: 04.05.2021
Datum zadání: 04.05.2021
Datum potvrzení stud. oddělením: 13.05.2021
Datum a čas obhajoby: 02.07.2021 09:00
Datum odevzdání elektronické podoby:21.05.2021
Datum odevzdání tištěné podoby:27.05.2021
Datum proběhlé obhajoby: 02.07.2021
Oponenti: doc. Mgr. Robert Šámal, Ph.D.
 
 
 
Zásady pro vypracování
Superkonkcentrátory jsou grafy specifických vlastností s nejrůznějším využitím v informatice. Proto je důležitá otázka jejich konstrukce. Práce by měla podat přehled o znamých konstrukcích a důkazech existence superkoncentrátorů se zaměřením na souhru různých jejich parametrů a naleznout tzv. explicitní konstrukce a jejich předpoklady.
Seznam odborné literatury
[1] Nicholas Pippenger. Self-routing superconcentrators. Journal of Computer and System Sciences, 52(1):53–60, 1996.

[2] Jaikumar Radhakrishnan and Amnon Ta-Shma. Bounds for dispersers, extractors, and depth-two superconcentrators. SIAM J. Discret. Math., 13(1):2–24, 2000.

[3] Anna Gál, Kristoffer Arnsfelt Hansen, Michal Koucký, Pavel Pudlák, and Emanuele Viola. Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates. IEEE Trans. on Information Theory, 59(10):6611–6627, 2013.

[4] Amnon Ta-Shma and Christopher Umans. Better condensers and new extractors from Parvaresh-Vardy codes. In 2012 IEEE 27th Conference on Computational Complexity, pages 309–315, 2012.
 
Univerzita Karlova | Informační systém UK