MS
Marek Sokołowski
cs.DScs.DMmath.COcs.CCcs.LOmath.LO
On Valency
published · living versionsW_k6htykwp·v1 · currentpublished
Subexponential Algorithms for Total Search Problems in the Dense Pigeonhole Regime
with Jadwiga Czyżewska, Karolina Drabik, Karol Węgrzycki
1 version
Preprints & journals
28 papers in the corpus · 2021–2026Subexponential Algorithms for Total Search Problems in the Dense Pigeonhole Regime2610.25338v1 · Jadwiga Czyżewska, Karolina Drabik, Marek Soko\lowski et al.2026 · 0 citationsarXivon Valency
Time-Optimal APSP and Matrix Multiplication in Classes of Linear Neighborhood Complexity2608.25212v1 · 'Edouard Bonnet, Julien Duron, Marcin Pilipczuk et al.2026 · 0 citationsarXiv
A tight lower bound for malicious online bipartite matching with limited recourse budget2608.22524v1 · Julia Baligacs, Bart\lomiej Bosek, PawełPutra et al.2026 · 0 citationsarXiv
Multiway -Cut is fixed-parameter tractable2608.10380v1 · Tony Huynh, Eun Jung Kim, Sang-il Oum et al.2026 · 0 citationsarXiv
An Erdős-Pósa theorem for cycles and faces of distinct lengths2607.06869v1 · J. Pascal Gollin, Maximilian Gorsky, Meike Hatzel et al.2026 · 0 citationsarXiv
Fast decremental tree sums in forests2605.06555v1 · Benjamin Aram Berendsohn, Marek Soko\lowski2026 · 0 citationsarXiv
Dynamic Detours2605.03225v1 · Daniel Dadush, MichałPilipczuk, Amadeus Reinald et al.2026 · 0 citationsarXiv
Polynomial-size encoding of all cuts of small value in integer-valued symmetric submodular functions2603.10710v2 · Sang-il Oum, Marek Soko\lowski2026 · 0 citationsarXiv
Strongly Polynomial Parallel Work-Depth Tradeoffs for Directed SSSP2510.19780v1 · Adam Karczmarz, Wojciech Nadara, Marek Soko\lowski2025 · 0 citationsarXiv
Treedepth Inapproximability and Exponential ETH Lower Bound2507.13818v1 · 'Edouard Bonnet, Daniel Neuen, Marek Soko\lowski2025 · 0 citationsarXiv
Fully dynamic biconnectivity in time2503.21733v1 · Jacob Holm, Wojciech Nadara, Eva Rotenberg et al.2025 · 1 citationarXiv
Low rank MSO2502.08476v1 · Miko\laj Boja'nczyk, MichałPilipczuk, Wojciech Przybyszewski et al.2025 · 0 citationsarXiv
Half-integral Erdős-Pósa property for non-null - paths2408.16344v1 · Vera Chekan, Colin Geniet, Meike Hatzel et al.2024 · 0 citationsarXiv
Almost-linear time parameterized algorithm for rankwidth via dynamic rankwidth2402.12364v1 · Tuukka Korhonen, Marek Soko\lowski2024 · 2 citationsarXiv
Elementary first-order model checking for sparse graphs2401.16230v2 · Jakub Gajarsk'y, MichałPilipczuk, Marek Soko\lowski et al.2024 · 2 citationsarXiv
Exact Shortest Paths with Rational Weights on the Word RAM2311.03321v1 · Adam Karczmarz, Wojciech Nadara, Marek Soko\lowski2023 · 1 citationarXiv
Fully dynamic approximation schemes on planar and apex-minor-free graphs2310.20623v1 · Tuukka Korhonen, Wojciech Nadara, MichałPilipczuk et al.2023 · 1 citationarXiv
Sparse Graphs of Twin-width 2 Have Bounded Tree-width2307.01732v1 · Benjamin Bergougnoux, Jakub Gajarsk'y, Grzegorz Gu'spiel et al.2023 · 0 citationsarXiv
Detecting Points in Integer Cones of Polytopes is Double-Exponentially Hard2307.00406v1 · \Lukasz Kowalik, Alexandra Lassota, Konrad Majewski et al.2023 · 2 citationsarXiv
Dynamic treewidth2304.01744v1 · Tuukka Korhonen, Konrad Majewski, Wojciech Nadara et al.2023 · 3 citationsarXiv
Flipper games for monadically stable graph classes2301.13735v2 · Jakub Gajarsk'y, Nikolas Mahlmann, Rose McCarty et al.2023 · 7 citationsarXiv
Simpler and faster algorithms for detours in planar digraphs2301.02421v1 · Meike Hatzel, Konrad Majewski, MichałPilipczuk et al.2023 · 3 citationsarXiv
Max Weight Independent Set in graphs with no long claws: An analog of the Gyárfás' path argument2203.04836v1 · Konrad Majewski, Tom'as Masar'ik, Jana Novotn'a et al.2022 · 1 citationarXiv
Graphs of bounded twin-width are quasi-polynomially -bounded2202.07608v1 · MichałPilipczuk, Marek Soko\lowski2022 · 7 citationsarXiv
Compact representation for matrices of bounded twin-width2110.08106v1 · MichałPilipczuk, Marek Soko\lowski, Anna Zych-Pawlewicz2021 · 7 citationsarXiv
Maintaining properties on dynamic structures with bounded feedback vertex number2107.06232v2 · Konrad Majewski, MichałPilipczuk, Marek Soko\lowski2021 · 0 citationsarXiv
Determining 4-edge-connected components in linear time2105.01699v1 · Wojciech Nadara, Mateusz Radecki, Marcin Smulewicz et al.2021 · 3 citationsarXiv
Bounds on half graph orders in powers of sparse graphs2103.06218v1 · Marek Soko\lowski2021 · 0 citationsarXiv
Career total: 35 works. 28 are in this corpus.
Profile built from the corpus for this byline.
Author records are still filling in while the Hub is in alpha. If this is your page, you'll be able to claim it soon. Spot a mistake? Tell us.