Jakub Opršal
Research interests
I work in computational complexity almost exclusively on problems inside the class NP, so-called constraint satisfaction problems. Currently, we are investigating reductions between promise versions of constraint satisfaction; in such promise problems, one is given an instance that is promise to have a solution satisfying some strong constraints (e.g., a graph that is 3 colourable), and is asked to provide a solution satisfying weaker constraints (e.g., colour the graph with 6 colours).
The complexity of such problems depends on surprisingly abstract properties of the problems, and require deep mathematical theories: universal algebra, homology theory, and many that we are not yet completely aware of.
I have written a brief list of open problems in promise constraint satisfaction based on my talk at the AAA 100 held in the beginning of 2021. This is posted on my blog site, https://jakub-oprsal.vercel.app/open-problems.
- Theory of computation → Problems, reductions and completeness;
- Mathematics of computing → Discrete mathematics; Graph colouring; Algebraic topology; Universal algebra;