University of Oxford

Power of Algorithms in Discrete Optimisation

University of Warsaw

Thesis: The topology of solution spaces of combinatorial problems

Advisor: Michał Pilipczuk

Faculty of Mathematics, Informatics and Mechanics

University of Warsaw

Thesis: Reconfiguration and structural graph theory

Advisor: Marcin Kamiński

College of Inter-Faculty Individual Studies in Mathematics and Natural Sciences

University of Warsaw

Full CV

My interests range over theoretical aspects of computer science, focusing on parameterized algorithms, graph theory, computational complexity and occasionally logic. Currently I am looking into connections to more applied algorithmics.

My PhD thesis investigates *multiplicative graphs*, which are the subject of Hedetniemi's conjecture (on coloring graph products), as well as spaces of graph homomorphisms, using new algebraic-topological methods. News: in May 2019, Hedetniemi's conjecture was refuted by Yaroslav Shitov!

- Sallow: a heuristic algorithm for treedepth decompositions GitHub | a submission for PACE 2020 | to appear in IPEC 2020 proceedings
- Topology and adjunction in promise constraint satisfaction submitted | merge of arXiv:1904.03214 and
*Improved hardness for H-colourings…*. Theorem 4.17 is improved from 4- to 3-colourings. Adjunction is discussed in the context of gadget constructions. The proofs are significantly more detailed and the presentation has been overhauled, with more examples.

- The power of the combined basic LP and affine relaxation for promise CSPs to appear in SICOMP | extends SODA 2020 paper by Joshua Brakensiek and Venkatesan Guruswami
- The complexity of promise SAT on non-Boolean domains ICALP 2020 | presentation on YouTube
- Treewidth-Pliability and PTAS for Max-CSPs SODA 2021
- Improved hardness for H-colourings of G-colourable graphs SODA 2020 | contains small results about category theory not included in Topology and adjunction…

- Graphs that are not strongly multplicative in preparation…
- Tight complexity lower bounds for integer linear programming with few constraints STACS 2019 | ACM TOCT
- Integer Programming and Incidence Treedepth IPCO 2019
- Hedetniemi's conjecture and strongly multiplicative graphs SIAM J. Discrete Math.
- The step Sidorenko property and non-norming edge-transitive graphs J. Comb. Theory A (JCTA)

- On inverse powers of graphs and topological implications of Hedetniemi's conjecture | J. Comb. Theory B (JCTB)
- Turing kernelization for finding long paths in graph classes excluding a topological minor IPEC 2017 | invited to Algorithmica special issue
- On Directed Feedback Vertex Set parameterized by treewidth WG 2018

- Tight lower bounds for the complexity of multicoloring ESA 2017 | ACM Trans. Comput. Theory (TOCT)
- Cutwidth: obstructions and algorithmic aspects IPEC 2016, Best Paper award | invited to Algorithmica special issue
- Linear kernels for edge deletion problems to immersion-closed graph classes ICALP 2017
- Square-free graphs are multiplicative SIAM DM 2016 | J. Comb. Theory B (JCTB)

presentation | Young Author Prize at Bordeaux Graph Workshop

- Fully polynomial-time parameterized computations for graphs and matrices of low treewidth SODA 2017 | ACM Trans. Algorithms (TALG)
- On space efficiency of algorithms working on structural decompositions of graphs STACS 2016 | ACM Trans. Comput. Theory (TOCT)
- Edge bipartization faster than 2
^{k}IPEC 2016 | invited to Algorithmica special issue - Polynomial kernelization for removing induced claws and diamonds WG 2015 | Theory Comput. Syst. (ToCS)

- Homomorphism reconfiguration via homotopy SIAM J. Discrete Math. | STACS 2015 | animated presentation (fr)
- Reconfiguration in bounded bandwidth and treedepth J. Comput. Syst. Sci. | slides | (abridged version in joint paper below)
- Reconfiguration over tree decompositions IPEC 2014
- Reconfiguring independent sets in claw-free graphs SWAT 2014 | slides

- Principal investigator in
*The topology of solution spaces of combinatorial problems*, a PRELUDIUM grant funded by the National Science Centre, Poland (2017-2019). - Research project
*CUTACOMBS*with Marcin Pilipczuk. - Research project
*Optimality in parameterized complexity*with my advisor Michał Pilipczuk (2014-2017). - I visited Daniel Kráľ at the University of Warwick, DIMAP, for 5 weeks in 2017; Claude Tardif at Queen's University in Kingston, Ontario, for a week in 2017; Marthe Bonamy at LaBRI, Bordeaux, for 2 weeks in 2016; the Bergen Algorithms Research Group for a week in 2015 and two weeks in 2016.
- Second award for best master thesis in computer science in Poland, from PTI.
- Research project
*Graphs Within Graphs*with my masters' advisor Marcin Kamiński (2013-2014). - I visited the University of Waterloo, Canada for 2 weeks for a research collaboration with Naomi Nishimura and Amer Mouawad (2014).

* pronounced [ˈmarʨ̑in 'vrɔxna], like "mar-chin vroh-na", but "Martin" is perfectly fine :)