Constructions of Bounded-depth Superconcentrators

• Thesis title in Czech: Konstrukce superkoncentrátorů omezené hloubky
• Thesis title in English: Constructions of Bounded-depth Superconcentrators
• Key words: superkoncentrátory|expandery
• English key words: superconcentrators|expanders
• Academic year of topic announcement: 2021/2022
• Thesis type: Bachelor's thesis
• Thesis language: angličtina
• Department: Computer Science Institute of Charles University (32-IUUK)
• Supervisor: prof. Mgr. Michal Koucký, Ph.D.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 04.05.2021
• Date of assignment: 04.05.2021
• Confirmed by Study dept. on: 13.05.2021
• Date and time of defence: 02.07.2021 09:00
• Date of electronic submission: 21.05.2021
• Date of submission of printed version: 27.05.2021
• Date of proceeded defence: 02.07.2021
• Opponents: doc. Mgr. Robert Šámal, Ph.D.

Guidelines

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.

References

[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.