Lower Bounds on Boolean Formula Size
| Thesis title in Czech: | Dolní odhady velikosti Booleovských formulí |
|---|---|
| Thesis title in English: | Lower Bounds on Boolean Formula Size |
| Key words: | Booleovská formule|formální míra složitosti|dolní odhady |
| English key words: | Boolean formula|Formal complexity measure|Lower bounds |
| Academic year of topic announcement: | 2018/2019 |
| Thesis type: | Bachelor's thesis |
| Thesis language: | angličtina |
| Department: | Department of Logic (21-KLOG) |
| Supervisor: | Mgr. Pavel Hrubeš, Ph.D. |
| Author: | hidden - assigned and confirmed by the Study Dept. |
| Date of registration: | 25.09.2018 |
| Date of assignment: | 01.10.2018 |
| Administrator's approval: | not processed yet |
| Confirmed by Study dept. on: | 17.01.2019 |
| Date and time of defence: | 19.06.2019 10:00 |
| Date of electronic submission: | 17.05.2019 |
| Date of proceeded defence: | 19.06.2019 |
| Submitted/finalized: | committed by student and finalized |
| Opponents: | RNDr. Petr Savický, CSc. |
| Guidelines |
| Práce se bude zabývat Booleovskými formulemi a jejich velikostí.
Student se seznámí se základními metodami konstrukce dolních odhadů (Nechiporuk, Krapchenko, ...) a uvede stručný přehled. V další části prozkoumá pojmy formální míry složitosti, kombinatorických obdélníků a jejich měr a porovná vztahy s předchozím. Práce by také měla obsahovat vlastní příklady aplikace metod na konkrétní Booleovské funkce. |
| References |
| I. Wegener, The Complexity of Boolean Functions, 1987. P. Hrubeš, S. Jukna, A. Kulikov, P. Pudlák, On Convex Complexity Measures, 2010. M.Karchmer, E. Kushilevitz, N. Nisan, Fractional covers and communication complexity, 1995. M. V. Khrapchenko, A method for obtaining lower bounds for the complexity of pi-schemes, 1972. |