Monotone functions avoiding majorities

• Thesis title in Czech: Monotónní funkce vyhýbající se majoritám
• Thesis title in English: Monotone functions avoiding majorities
• Key words: Promise Constraint Satisfaction Problem, majoritní funkce, polymorfismus, minor funkce, minion
• English key words: Promise Constraint Satisfaction Problem, majority function, polymorphism, minor of a function, minion
• Academic year of topic announcement: 2019/2020
• Thesis type: Bachelor's thesis
• Thesis language: angličtina
• Department: Department of Algebra (32-KA)
• Supervisor: doc. Mgr. Libor Barto, Ph.D.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 25.02.2020
• Date of assignment: 25.02.2020
• Confirmed by Study dept. on: 13.03.2020
• Date and time of defence: 15.07.2020 09:00
• Date of electronic submission: 04.06.2020
• Date of submission of printed version: 04.06.2020
• Date of proceeded defence: 15.07.2020
• Opponents: Antoine Mottet

Guidelines

Úkolem práce je vyřešit speciální případy kombinatorických hypotéz, které vycházejí ze studia složitosti Promise CSP nad dvouprkovými strukturami obsahujícími nerovnosti.

References

L. Barto, J. Bulin, A. Krokhin, J. Oprsal, Algebraic approach to promise constraint satisfaction, arXiv 1811.00970

J. Brakensiek, V. Guruswami, Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy. SODA 2018.