hidden - assigned and confirmed by the Study Dept.
Date of registration:
09.12.2021
Date of assignment:
27.01.2022
Confirmed by Study dept. on:
11.03.2022
Date and time of defence:
06.09.2022 09:00
Date of electronic submission:
20.07.2022
Date of submission of printed version:
25.07.2022
Date of proceeded defence:
06.09.2022
Opponents:
Michael Kompatscher, Ph.D.
Guidelines
The aim is to improve the combinatorial version of the PCP Theorem proved in the SODA 22 paper "Combinatorial Gap Theorem and Reductions between Promise CSPs" in some of the directions proposed in that paper, i.e., towards the Smooth Label Cover, a combinatorial k-to-1 Conjecture, or a combinatorial Parallel Repetition Theorem.
References
L. Barto, M. Kozik, Combinatorial Gap Theorem and Reductions between Promise CSPs, SODA 2022
L. Barto, J. Bulin, A. Krokhin, J. Oprsal, Algebraic approach to promise constraint satisfaction, Journal of the ACM 68/4 (2021), 1-66
- assigned and confirmed by the Study Dept.