Marcin Wrochna

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 algebraic-topological methods. 

Publications

2025

• Complexity of approximate conflict-free, linearly-ordered, and nonmonochromatic hypergraph colourings
  with Tamio-Vesa Nakajima, Zephyr Verwimp, Stanislav Živný
    ICALP 2025 | subsumes A note on hardness of promise hypergraph colouring

2024

• Deep learning outperforms traditional image segmentation and feature extraction methods in automatic follicle counting
  with Piotr Wygocki, Andrzej Zapała, Mateusz Ulfig, Marcin Zieleń, Krystian Zieliński, Natalia Gajewska, Damian Drzyzga, Michał Brzozowski
    ASRM 2024
• Prospective validation of an artificial intelligence platform for automated follicle counting
  with Piotr Wygocki, Mateusz Ulfig, Andrzej Zapała, Marcin Zieleń, Krystian Zieliński, Natalia Gajewska, Damian Drzyzga
    ESHRE 2024
• Fully automated follicle counting matches human accuracy levels in predicting stimulation outcomes
  with Piotr Wygocki, Mateusz Ulfig, Andrzej Zapała, Marcin Zieleń, Krystian Zieliński, Natalia Gajewska, Damian Drzyzga
    ESHRE 2024

2023

• Automated ovarian follicle counting and measurement with deep learning
  with Piotr Wygocki, Mateusz Ulfig, Andrzej Zapała, Marcin Zieleń, Krystian Zieliński, Natalia Gajewska, Damian Drzyzga
    submitted
• Comparison of manual and automated ovarian follicle measurement methods
  with Piotr Wygocki, Mateusz Ulfig, Andrzej Zapała, Marcin Zieleń, Krystian Zieliński, Natalia Gajewska, Damian Drzyzga
    FRMC (Foundation for Reproductive Medicine Conference) 2023
• Automatizing ovarian follicle counting and measurement with artificial intelligence
  with Piotr Wygocki, Mateusz Ulfig, Andrzej Zapała, Marcin Zieleń, Krystian Zieliński, Urszula Sankowska, Natalia Gajewska, Damian Drzyzga, Piotr Sankowski
    ESHRE 2023

2020

• A note on hardness of promise hypergraph colouring   preprint
• PTAS for Sparse General-Valued CSPs
  with Balázs F. Mezei, Stanislav Živný
    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
  with Andrei Krokhin, Jakub Opršal, Stanislav Živný
    SIAM J. Comput. | 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.

2019

• The power of the combined basic LP and affine relaxation for promise CSPs
  with Joshua Brakensiek, Venkatesan Guruswami, Stanislav Živný
    SIAM J. Comput. | extends SODA 2020 paper by Joshua Brakensiek and Venkatesan Guruswami
• The complexity of promise SAT on non-Boolean domains
  with Alex Brandts, Stanislav Živný
    ICALP 2020 | ACM Trans. Comput. Theory (TOCT) | presentation on YouTube
• Pliability and approximating Max-CSPs
  with Miguel Romero, Stanislav Živný
    Journal of the ACM | journal version of Treewidth-Pliability and PTAS for Max-CSPs
• Treewidth-Pliability and PTAS for Max-CSPs
  with Miguel Romero, Stanislav Živný
    SODA 2021 | presentation video
• Improved hardness for H-colourings of G-colourable graphs
  with Stanislav Živný
    SODA 2020 | contains small results about category theory not included in Topology and adjunction…

2018

• Graphs that are not strongly multplicative
  with Claude Tardif
    in preparation…
• Tight complexity lower bounds for integer linear programming with few constraints
  with Dušan Knop, Michał Pilipczuk
    STACS 2019 | ACM TOCT
• Integer Programming and Incidence Treedepth
  with Eduard Eiben, Robert Ganian, Dušan Knop, Sebastian Ordyniak, Michał Pilipczuk
    IPCO 2019
• Hedetniemi's conjecture and strongly multiplicative graphs
  with Claude Tardif
    SIAM J. Discrete Math.
• The step Sidorenko property and non-norming edge-transitive graphs
  with Daniel Král’, Taísa L. Martins, Péter Pál Pach
    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
  with Bart M. P. Jansen, Marcin Pilipczuk
    IPEC 2017 | invited to Algorithmica special issue
• On Directed Feedback Vertex Set parameterized by treewidth
  with Marthe Bonamy, Łukasz Kowalik, Jesper Nederlof, Michał Pilipczuk, Arkadiusz Socała
    WG 2018

2016

• Tight lower bounds for the complexity of multicoloring
  with Marthe Bonamy, Łukasz Kowalik, Michał Pilipczuk, Arkadiusz Socała
    ESA 2017 | ACM Trans. Comput. Theory (TOCT)
• Cutwidth: obstructions and algorithmic aspects
  with Archontia C. Giannopoulou, Michał Pilipczuk, Jean-Florent Raymond, Dimitrios M. Thilikos
    IPEC 2016, Best Paper award | invited to Algorithmica special issue
• Linear kernels for edge deletion problems to immersion-closed graph classes
  with Archontia C. Giannopoulou, Michał Pilipczuk, Jean-Florent Raymond, Dimitrios M. Thilikos
    ICALP 2017 | SIAM J. Discrete Math.
• Square-free graphs are multiplicative   SIAM DM 2016 | J. Comb. Theory B (JCTB)
    presentation | Young Author Prize at Bordeaux Graph Workshop

2015

• Fully polynomial-time parameterized computations for graphs and matrices of low treewidth
  with Fedor V. Fomin, Daniel Lokshtanov, Michał Pilipczuk, Saket Saurabh
    SODA 2017 | ACM Trans. Algorithms (TALG)
• On space efficiency of algorithms working on structural decompositions of graphs
  with Michał Pilipczuk
    STACS 2016 | ACM Trans. Comput. Theory (TOCT)
• Edge bipartization faster than 2^k
  with Marcin Pilipczuk, Michał Pilipczuk
    IPEC 2016 | invited to Algorithmica special issue
• Polynomial kernelization for removing induced claws and diamonds
  with Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Erik Jan van Leeuwen
    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
  with Amer E. Mouawad, Naomi Nishimura, Venkatesh Raman
    IPEC 2014
• Reconfiguring independent sets in claw-free graphs
  with Paul Bonsma, Marcin Kamiński
    SWAT 2014 | slides

My name is pronounced like "mar-chin vroh-na", but "Martin" is perfectly fine 🙂