Graph communication protocols
| Název práce v češtině: | Grafové komunikační protokoly |
|---|---|
| Název v anglickém jazyce: | Graph communication protocols |
| Klíčová slova: | komunikační složitost, booleovské funkce, booleovské obvody |
| Klíčová slova anglicky: | communication complexity, Boolean functions, Boolean circuits |
| Akademický rok vypsání: | 2017/2018 |
| Typ práce: | diplomová práce |
| Jazyk práce: | angličtina |
| Ústav: | Informatický ústav Univerzity Karlovy (32-IUUK) |
| Vedoucí / školitel: | prof. RNDr. Pavel Pudlák, DrSc. |
| Řešitel: | Mgr. Lukáš Folwarczný - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 15.06.2018 |
| Datum zadání: | 27.06.2018 |
| Datum potvrzení stud. oddělením: | 18.07.2018 |
| Datum a čas obhajoby: | 13.09.2018 00:00 |
| Datum odevzdání elektronické podoby: | 18.07.2018 |
| Datum odevzdání tištěné podoby: | 20.07.2018 |
| Datum proběhlé obhajoby: | 13.09.2018 |
| Oponenti: | prof. RNDr. Jiří Sgall, DrSc. |
| Zásady pro vypracování |
| Grafové komunikační protokoly jsou protokoly pro řešení Karchmer-Wigdersonovy hry definované pomocí orientovaného acyklického grafu s podmínkami dosažitelnosti v každém vrcholu grafu. Podmínky dosažitelnosti musí splňovat jisté podmínky.
Cílem práce je porovnat složitost protokolů nutných pro výpočet KW hry pro různé podmínky dosažitelnosti, konkrétně porovnat protokoly, které používají nerovnost, a protokoly, které používají rovnost. |
| Seznam odborné literatury |
| 1. Ankit Garg, Mika Goos, Pritish Kamath and Dmitry Sokolov,
Monotone Circuit Lower Bounds from Resolution, Electronic Colloquium on Computational Complexity, TR24, 2017. 2. Pavel Hrubeš and Pavel Pudlák, A note on monotone real circuits, Inf. Process. Lett., 131, pages 15-19, 2018. 3. Dmitry Itsykson and Dmitry Sokolov, Lower Bounds for Splittings by Linear Combinations, Proc. of Mathematical Foundations of Computer Science 2014, 39th International Symposium, Budapest, Hungary, August 25-29, 2014. Proceedings, pages 372-383, 2014. 4. Pavel Hrubes and Pavel Pudlák, Random Formulas, Monotone Circuits, and Interpolation, Proc. of 58th IEEE Annual Symposium on Foundations of Computer Science, Berkeley, CA, USA, October 15-17, 2017, pages 121-131, 2017 |