Skip to main content

Jakub Opršal

Jakub Opršal

jakub.oprsal (at)

[arXiv] [scholar] [dblp] [github]


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,

  • Theory of computation → Problems, reductions and completeness;
  • Mathematics of computing → Discrete mathematics; Graph colouring; Algebraic topology; Universal algebra;