Publications
See also my DBLP page.
2025
-
J. Holm,
W. Nadara,
E. Rotenberg,
M. Sokołowski
Fully dynamic biconnectivity in Õ(log2 n) time
STOC 2025, arXiV [link] -
M. Bojańczyk,
Mi. Pilipczuk,
W. Przybyszewski,
M. Sokołowski,
G. Stamoulis
Low rank MSO
arXiV [link]
2024
-
T. Korhonen,
M. Sokołowski
Almost-linear time parameterized algorithm for rankwidth via dynamic rankwidth
STOC 2024 [link], arXiV [link] -
A. Karczmarz,
W. Nadara,
M. Sokołowski
Exact Shortest Paths with Rational Weights on the Word RAM
SODA 2024 [link], arXiV [link] -
T. Korhonen,
W. Nadara,
Mi. Pilipczuk,
M. Sokołowski
Fully Dynamic Approximation Schemes on Planar and Apex-Minor-Free Graphs
SODA 2024 [link], arXiV [link] -
Ł. Kowalik,
A. Lassota,
K. Majewski,
Mi. Pilipczuk,
M. Sokołowski
Detecting Points in Integer Cones of Polytopes is Double-Exponentially Hard
SOSA 2024 [link], arXiV [link] -
J. Gajarský,
Mi. Pilipczuk,
Sz. Toruńczyk,
G. Stamoulis,
M. Sokołowski
Elementary first-order model checking for sparse graphs
LICS 2024 [link], arXiV [link] -
V. Chekan,
C. Geniet,
M. Hatzel,
Mi. Pilipczuk,
M. Sokołowski,
M. Seweryn,
M. Witkowski
Half-integral Erdös-Pósa property for non-null S-T paths
arXiV [link]
2023
-
T. Korhonen,
K. Majewski,
W. Nadara,
Mi. Pilipczuk,
M. Sokołowski
Dynamic Treewidth
FOCS 2023 [link], arXiV [link] -
Mi. Pilipczuk,
M. Sokołowski
Graphs of bounded twin-width are quasi-polynomially chi-bounded
J. Comb. Theory B [link], arXiV [link] -
K. Majewski,
Mi. Pilipczuk,
M. Sokołowski
Maintaining CMSO2 properties on dynamic structures with bounded feedback vertex number
TOCT [link], STACS 2023 [link], arXiV [link] -
M. Hatzel,
K. Majewski,
Mi. Pilipczuk,
M. Sokołowski
Simpler and faster algorithms for detours in planar digraphs
SOSA 2023 [link], arXiV [link] -
J. Gajarský,
N. Mählmann,
R. McCarty,
P. Ohlmann,
Mi. Pilipczuk,
W. Przybyszewski,
S. Siebertz,
M. Sokołowski,
Sz. Toruńczyk
Flipper games for monadically stable graph classes
ICALP 2023 [link], arXiV [link] -
B. Bergougnoux,
J. Gajarský,
G. Guśpiel,
P. Hliněný,
F. Pokrývka,
M. Sokołowski
Sparse Graphs of Twin-Width 2 Have Bounded Tree-Width
ISAAC 2023 [link], arXiV [link]
2022
-
K. Majewski,
T. Masařík,
J. Masaříková,
K. Okrasa,
Ma. Pilipczuk,
P. Rzążewski,
M. Sokołowski
Max Weight Independent Set in Graphs with No Long Claws: An Analog of the Gyárfás' Path Argument
ICALP 2022 [link], arXiV [link] -
Mi. Pilipczuk,
M. Sokołowski,
A. Zych-Pawlewicz
Compact Representation for Matrices of Bounded Twin-Width
STACS 2022 [link], arXiV [link]
2021
-
W. Nadara,
M. Radecki,
M. Smulewicz,
M. Sokołowski
Determining 4-Edge-Connected Components in Linear Time
ESA 2021 [link] (best student paper), arXiV [link] -
M. Sokołowski
Bounds on Half Graph Orders in Powers of Sparse Graphs
Elec. J. Comb. [link], EUROCOMB 2021 [link], arXiV [link]