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.