Marcin Wrochna
m.wrochnamimuw.edu.pl
I'm a researcher working on deep learning. Previously I focused on theoretical aspects of computer science, specifically algorithmic graph theory, constraint satisfaction, and parameterized complexity.
My PhD thesis investigated multiplicative graphs, which are the subject of Hedetniemi's conjecture (on coloring graph products), as well as spaces of graph homomorphisms, using new algebraictopological methods.
Publications
[DBLP]2020
 A note on hardness of promise hypergraph colouring preprint
 PTAS for Sparse GeneralValued CSPs LICS 2021  ACM Trans. Algorithms (TALG)
 Smaller counterexamples to Hedetniemi's conjecture preprint
 Sallow: a heuristic algorithm for treedepth decompositions GitHub  a submission for PACE 2020, in IPEC 2020 proc.  short presentation slides, vid
 Topology and adjunction in promise constraint satisfaction SIAM J. Comput.  merge of arXiv:1904.03214 and Improved hardness for Hcolourings… Theorem 4.17 is improved from 4 to 3colourings. Adjunction is discussed in the context of gadget constructions. The proofs are significantly more detailed and the presentation has been overhauled, with more examples.
2019
 The power of the combined basic LP and affine relaxation for promise CSPs SIAM J. Comput.  extends SODA 2020 paper by Joshua Brakensiek and Venkatesan Guruswami
 The complexity of promise SAT on nonBoolean domains ICALP 2020  ACM Trans. Comput. Theory (TOCT)  presentation on YouTube
 Pliability and approximating MaxCSPs accepted in JACM  journal version of TreewidthPliability and PTAS for MaxCSPs
 TreewidthPliability and PTAS for MaxCSPs SODA 2021  presentation video
 Improved hardness for Hcolourings of Gcolourable graphs SODA 2020  contains small results about category theory not included in Topology and adjunction…
2018
 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 nonnorming edgetransitive graphs J. Comb. Theory A (JCTA)
2017
 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
2016
 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 immersionclosed graph classes ICALP 2017  SIAM J. Discrete Math.

Squarefree graphs are multiplicative
SIAM DM 2016  J. Comb. Theory B (JCTB)
presentation  Young Author Prize at Bordeaux Graph Workshop
2015
 Fully polynomialtime 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)
2014
 Homomorphism reconfiguration via homotopy STACS 2015  SIAM J. Discrete Math.  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 clawfree graphs SWAT 2014  slides
My name is pronounced like "marchin vrohna", but "Martin" is perfectly fine 🙂