Mathematicians think I am a computer scientist, computer scientists think I am a mathematician. And I think I am a barber.
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, topological combinatorics, and many that we are not yet completely aware of.
- Theory of computation → Problems, reductions and completeness;
- Mathematics → Discrete mathematics; Graph colouring; Algebraic topology; Universal algebra;
- Apr–May 2019 Research stay at Carnegie Mellon University, US. Visiting Venkat Guruswami.
- since 2018 Post-doc, Durham University, UK. Working with Andrei Krokhin.
- 2016–2018 Post-doc, Technische Universität Dresden, Germany. Employed on Manuel Bodirsky’s ERC grant ‘CSP-Infinity’.
- Mar–Sep 2016 Post-doc, Jagellonian University, Kraków, Poland. Working with Marcin Kozik.
- 29 February 2016 PhD, Charles University in Prague, advised by Libor Barto.
- Jun–Dec 2013 Research stay at Johannes Kepler University, Linz, Austria.