Faster Exact Bandwidth. - Marek Cygan; Marcin Pilipczuk (WG, 2008)

Exponential-Time Approximation of Hard Problems - Marek Cygan; Lukasz Kowalik; Marcin Pilipczuk; Mateusz Wykurz (CoRR, 2008)

Beyond O*(2^n) in domination-type problems - Marek Cygan; Marcin Pilipczuk; Jakub Onufry Wojtaszczyk (CoRR, 2009)

Exponential-time approximation of weighted set cover. - Marek Cygan; Lukasz Kowalik; Mateusz Wykurz (Inf. Process. Lett., 2009)

A Planar Linear Arboricity Conjecture. - Marek Cygan; Lukasz Kowalik; Borut Luzar (CIAC, 2010)

Irredundant Set Faster Than O(2n). - Marek Cygan; Marcin Pilipczuk; Jakub Onufry Wojtaszczyk (CIAC, 2010)

Algorithms for Three Versions of the Shortest Common Superstring Problem. - Maxime Crochemore; Marek Cygan; Costas S. Iliopoulos; Marcin Kubica 001; Jakub Radoszewski; Wojciech Rytter; Tomasz Walen (CPM, 2010)

Fast Approximation in Subspaces by Doubling Metric Decomposition. - Marek Cygan; Lukasz Kowalik; Marcin Mucha; Marcin Pilipczuk; Piotr Sankowski (ESA (1), 2010)

Capacitated Domination Faster Than O(2n). - Marek Cygan; Marcin Pilipczuk; Jakub Onufry Wojtaszczyk (SWAT, 2010)

Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs. - Marek Cygan; Marcin Pilipczuk; Michal Pilipczuk; Jakub Onufry Wojtaszczyk (WG, 2010)

Exact and approximate bandwidth. - Marek Cygan; Marcin Pilipczuk (Theor. Comput. Sci., 2010)

Approximation Algorithms for Union and Intersection Covering Problems. - Marek Cygan; Fabrizio Grandoni 001; Stefano Leonardi 001; Marcin Mucha; Marcin Pilipczuk; Piotr Sankowski (FSTTCS, 2011)

Parameterized Complexity of Firefighting Revisited. - Marek Cygan; Fedor V. Fomin; Erik Jan van Leeuwen (IPEC, 2011)

The stubborn problem is stubborn no more (a polynomial algorithm for 3-compatible colouring and the stubborn list partition problem). - Marek Cygan; Marcin Pilipczuk; Michal Pilipczuk; Jakub Onufry Wojtaszczyk (SODA, 2011)

On Problems as Hard as CNFSAT - Marek Cygan; Holger Dell; Daniel Lokshtanov; Dániel Marx; Jesper Nederlof; Yoshio Okamoto; Ramamohan Paturi; Saket Saurabh 001; Magnus Wahlström (CoRR, 2011)

Channel assignment via fast zeta transform. - Marek Cygan; Lukasz Kowalik (Inf. Process. Lett., 2011)

Capacitated domination faster than O(n2). - Marek Cygan; Marcin Pilipczuk; Jakub Onufry Wojtaszczyk (Inf. Process. Lett., 2011)

Breaking the 2n-barrier for Irredundance: Two lines of attack. - Daniel Binkele-Raible; Ljiljana Brankovic; Marek Cygan; Henning Fernau; Joachim Kneis; Dieter Kratsch; Alexander Langer; Mathieu Liedloff; Marcin Pilipczuk; Peter Rossmanith; Jakub Onufry Wojtaszczyk (J. Discrete Algorithms, 2011)

Dominating set is fixed parameter tractable in claw-free graphs. - Marek Cygan; Geevarghese Philip; Marcin Pilipczuk; Michal Pilipczuk; Jakub Onufry Wojtaszczyk (Theor. Comput. Sci., 2011)

A Path-Decomposition Theorem with Applications to Pricing and Covering on Trees. - Marek Cygan; Fabrizio Grandoni 001; Stefano Leonardi 001; Marcin Pilipczuk; Piotr Sankowski (ESA, 2012)

LP Rounding for k-Centers with Non-uniform Hard Capacities. - Marek Cygan; MohammadTaghi Hajiaghayi; Samir Khuller (FOCS, 2012)

Deterministic Parameterized Connected Vertex Cover. - Marek Cygan (SWAT, 2012)

An Improved FPT Algorithm and a Quadratic Kernel for Pathwidth One Vertex Deletion. - Marek Cygan; Marcin Pilipczuk; Michal Pilipczuk; Jakub Onufry Wojtaszczyk (Algorithmica, 2012)

On fixed-parameter algorithms for Split Vertex Deletion - Marek Cygan; Marcin Pilipczuk (CoRR, 2012)

Solving weighted and counting variants of connectivity problems parameterized by treewidth deterministically in single exponential time - Hans L. Bodlaender; Marek Cygan; Stefan Kratsch; Jesper Nederlof (CoRR, 2012)

Bandwidth and distortion revisited. - Marek Cygan; Marcin Pilipczuk (Discret. Appl. Math., 2012)

Kernelization hardness of connectivity problems in d-degenerate graphs. - Marek Cygan; Marcin Pilipczuk; Michal Pilipczuk; Jakub Onufry Wojtaszczyk (Discret. Appl. Math., 2012)

A Planar linear arboricity conjecture. - Marek Cygan; Jianfeng Hou; Lukasz Kowalik; Borut Luzar; Jian-Liang Wu 001 (J. Graph Theory, 2012)

A Polynomial Algorithm for 3-Compatible Coloring and the Stubborn List Partition Problem (The Stubborn Problem Is Stubborn No More). - Marek Cygan; Marcin Pilipczuk; Michal Pilipczuk; Jakub Onufry Wojtaszczyk (SIAM J. Comput., 2012)

Even Faster Exact Bandwidth. - Marek Cygan; Marcin Pilipczuk (ACM Trans. Algorithms, 2012)

Tight Kernel Bounds for Problems on Graphs with Small Degeneracy - (Extended Abstract). - Marek Cygan; Fabrizio Grandoni 001; Danny Hermelin (ESA, 2013)

Improved Approximation for 3-Dimensional Matching via Bounded Pathwidth Local Search. - Marek Cygan (FOCS, 2013)

The Planar Directed K-Vertex-Disjoint Paths Problem Is Fixed-Parameter Tractable. - Marek Cygan; Dániel Marx; Marcin Pilipczuk; Michal Pilipczuk (FOCS, 2013)

Catch them if you can: how to serve impatient users. - Marek Cygan; Matthias Englert; Anupam Gupta 001; Marcin Mucha; Piotr Sankowski (ITCS, 2013)

How to Sell Hyperedges: The Hypermatching Assignment Problem. - Marek Cygan; Fabrizio Grandoni 001; Monaldo Mastrolilli (SODA, 2013)

On Pairwise Spanners. - Marek Cygan; Fabrizio Grandoni 001; Telikepalli Kavitha (STACS, 2013)

Online Knapsack Revisited. - Marek Cygan; Lukasz Jez (WAOA, 2013)

A bound on the number of perfect matchings in Klee-graphs. - Marek Cygan; Marcin Pilipczuk; Riste Skrekovski (Discret. Math. Theor. Comput. Sci., 2013)

Split Vertex Deletion meets Vertex Cover: New fixed-parameter and exact exponential-time algorithms. - Marek Cygan; Marcin Pilipczuk (Inf. Process. Lett., 2013)

Steiner Forest Orientation Problems. - Marek Cygan; Guy Kortsarz; Zeev Nutov (SIAM J. Discret. Math., 2013)

Subset Feedback Vertex Set Is Fixed-Parameter Tractable. - Marek Cygan; Marcin Pilipczuk; Michal Pilipczuk; Jakub Onufry Wojtaszczyk (SIAM J. Discret. Math., 2013)

On multiway cut parameterized above lower bounds. - Marek Cygan; Marcin Pilipczuk; Michal Pilipczuk; Jakub Onufry Wojtaszczyk (ACM Trans. Comput. Theory, 2013)

Constant Factor Approximation for Capacitated k-Center with Outliers. - Marek Cygan; Tomasz Kociumaka (STACS, 2014)

On Cutwidth Parameterized by Vertex Cover. - Marek Cygan; Daniel Lokshtanov; Marcin Pilipczuk; Michal Pilipczuk; Saket Saurabh 001 (Algorithmica, 2014)

Parameterized Complexity of Eulerian Deletion Problems. - Marek Cygan; Dániel Marx; Marcin Pilipczuk; Michal Pilipczuk; Ildikó Schlotter (Algorithmica, 2014)

Scheduling Partially Ordered Jobs Faster than 2 n. - Marek Cygan; Marcin Pilipczuk; Michal Pilipczuk; Jakub Onufry Wojtaszczyk (Algorithmica, 2014)

Solving the 2-Disjoint Connected Subgraphs Problem Faster than 2 n. - Marek Cygan; Marcin Pilipczuk; Michal Pilipczuk; Jakub Onufry Wojtaszczyk (Algorithmica, 2014)

Parameterized complexity of firefighting. - Cristina Bazgan; Morgan Chopin; Marek Cygan; Michael R. Fellows; Fedor V. Fomin; Erik Jan van Leeuwen (J. Comput. Syst. Sci., 2014)

On the Hardness of Losing Width. - Marek Cygan; Daniel Lokshtanov; Marcin Pilipczuk; Michal Pilipczuk; Saket Saurabh 001 (Theory Comput. Syst., 2014)

Clique Cover and Graph Separation: New Incompressibility Results. - Marek Cygan; Stefan Kratsch; Marcin Pilipczuk; Michal Pilipczuk; Magnus Wahlström (ACM Trans. Comput. Theory, 2014)

Parameterized Algorithms - Marek Cygan; Fedor V. Fomin; Lukasz Kowalik; Daniel Lokshtanov; Dániel Marx; Marcin Pilipczuk; Michal Pilipczuk; Saket Saurabh 001 (Springer, 2015)

Approximating Upper Degree-Constrained Partial Orientations. - Marek Cygan; Tomasz Kociumaka (APPROX-RANDOM, 2015)

The Hardness of Subgraph Isomorphism. - Marek Cygan; Jakub Pachocki; Arkadiusz Socala (CoRR, 2015)

Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. - Hans L. Bodlaender; Marek Cygan; Stefan Kratsch; Jesper Nederlof (Inf. Comput., 2015)

Faster exponential-time algorithms in graphs of bounded average degree. - Marek Cygan; Marcin Pilipczuk (Inf. Comput., 2015)

Kernelization lower bound for Permutation Pattern Matching. - Ivan Bliznets; Marek Cygan; Pawel Komosa; Lukás Mach (Inf. Process. Lett., 2015)

Algorithmic Applications of Baur-Strassen's Theorem: Shortest Cycles, Diameter, and Matchings. - Marek Cygan; Harold N. Gabow; Piotr Sankowski (J. ACM, 2015)

Sitting Closer to Friends than Enemies, Revisited. - Marek Cygan; Marcin Pilipczuk; Michal Pilipczuk; Jakub Onufry Wojtaszczyk (Theory Comput. Syst., 2015)

Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable. - Rajesh Hemant Chitnis; Marek Cygan; Mohammad Taghi Hajiaghayi; Dániel Marx (ACM Trans. Algorithms, 2015)

Hardness of Approximation for H-Free Edge Modification Problems. - Ivan Bliznets; Marek Cygan; Pawel Komosa; Michal Pilipczuk (APPROX-RANDOM, 2016)

Algorithmic Complexity of Power Law Networks. - Pawel Brach; Marek Cygan; Jakub Lacki; Piotr Sankowski (SODA, 2016)

Tight Bounds for Graph Homomorphism and Subgraph Isomorphism. - Marek Cygan; Fedor V. Fomin; Alexander Golovnev; Alexander S. Kulikov; Ivan Mihajlin; Jakub Pachocki; Arkadiusz Socala (SODA, 2016)

Online Pricing with Impatient Bidders. - Marek Cygan; Marcin Mucha; Piotr Sankowski; Qiang Zhang (SODA, 2016)

Lower Bounds for Approximation Schemes for Closest String. - Marek Cygan; Daniel Lokshtanov; Marcin Pilipczuk; Michal Pilipczuk; Saket Saurabh 001 (SWAT, 2016)

Foreword: Special Issue on IPEC 2014. - Marek Cygan; Pinar Heggernes (Algorithmica, 2016)

Erratum to: Foreword: Special Issue on IPEC 2014. - Marek Cygan; Pinar Heggernes (Algorithmica, 2016)

On Group Feedback Vertex Set Parameterized by the Size of the Cutset. - Marek Cygan; Marcin Pilipczuk; Michal Pilipczuk (Algorithmica, 2016)

Polynomial-time approximation algorithms for weighted LCS problem. - Marek Cygan; Marcin Kubica 001; Jakub Radoszewski; Wojciech Rytter; Tomasz Walen (Discret. Appl. Math., 2016)

A Fast Branching Algorithm for Cluster Vertex Deletion. - Anudhyan Boral; Marek Cygan; Tomasz Kociumaka; Marcin Pilipczuk (Theory Comput. Syst., 2016)

Online Knapsack Revisited. - Marek Cygan; Lukasz Jez; Jirí Sgall (Theory Comput. Syst., 2016)

Designing FPT Algorithms for Cut Problems Using Randomized Contractions. - Rajesh Chitnis; Marek Cygan; MohammadTaghi Hajiaghayi; Marcin Pilipczuk; Michal Pilipczuk (SIAM J. Comput., 2016)

Known Algorithms for Edge Clique Cover are Probably Optimal. - Marek Cygan; Marcin Pilipczuk; Michal Pilipczuk (SIAM J. Comput., 2016)

On Problems as Hard as CNF-SAT. - Marek Cygan; Holger Dell; Daniel Lokshtanov; Dániel Marx; Jesper Nederlof; Yoshio Okamoto; Ramamohan Paturi; Saket Saurabh 001; Magnus Wahlström (ACM Trans. Algorithms, 2016)

Exact Algorithms for Bandwidth. - Marek Cygan (Encyclopedia of Algorithms, 2016)

Randomized Contraction. - Marek Cygan (Encyclopedia of Algorithms, 2016)

From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More. - Parinya Chalermsook; Marek Cygan; Guy Kortsarz; Bundit Laekhanukit; Pasin Manurangsi; Danupon Nanongkai; Luca Trevisan 001 (FOCS, 2017)

Improving TSP tours using dynamic programming over tree decomposition. - Marek Cygan; Lukasz Kowalik; Arkadiusz Socala (CoRR, 2017)

Randomization in Parameterized Complexity (Dagstuhl Seminar 17041). - Marek Cygan; Fedor V. Fomin; Danny Hermelin; Magnus Wahlström (Dagstuhl Reports, 2017)

Hitting forbidden subgraphs in graphs of bounded treewidth. - Marek Cygan; Dániel Marx; Marcin Pilipczuk; Michal Pilipczuk (Inf. Comput., 2017)

Tight Lower Bounds on Graph Embedding Problems. - Marek Cygan; Fedor V. Fomin; Alexander Golovnev; Alexander S. Kulikov; Ivan Mihajlin; Jakub Pachocki; Arkadiusz Socala (J. ACM, 2017)

Polynomial Kernelization for Removing Induced Claws and Diamonds. - Marek Cygan; Marcin Pilipczuk; Michal Pilipczuk; Erik Jan van Leeuwen; Marcin Wrochna (Theory Comput. Syst., 2017)

Tight Kernel Bounds for Problems on Graphs with Small Degeneracy. - Marek Cygan; Fabrizio Grandoni 001; Danny Hermelin (ACM Trans. Algorithms, 2017)

Online Facility Location with Deletions. - Marek Cygan; Artur Czumaj; Marcin Mucha; Piotr Sankowski (ESA, 2018)

Improved GQ-CNN: Deep Learning Model for Planning Robust Grasps. - Maciej Jaskowski; Jakub Swiatkowski; Michal Zajac 005; Maciej Klimek; Jarek Potiuk; Piotr Rybicki; Piotr Polatowski; Przemyslaw Walczyk; Kacper Nowicki; Marek Cygan (CoRR, 2018)

Randomized contractions meet lean decompositions. - Marek Cygan; Pawel Komosa; Daniel Lokshtanov; Michal Pilipczuk; Marcin Pilipczuk; Saket Saurabh 001 (CoRR, 2018)

On subexponential running times for approximating directed Steiner tree and related problems. - Marek Cygan; Guy Kortsarz; Bundit Laekhanukit (CoRR, 2018)

Fast Hamiltonicity Checking Via Bases of Perfect Matchings. - Marek Cygan; Stefan Kratsch; Jesper Nederlof (J. ACM, 2018)

Approximation and Parameterized Complexity of Minimax Approval Voting. - Marek Cygan; Lukasz Kowalik; Arkadiusz Socala; Krzysztof Sornat (J. Artif. Intell. Res., 2018)

Hardness of Approximation for H-free Edge Modification Problems. - Ivan Bliznets; Marek Cygan; Pawel Komosa; Michal Pilipczuk (ACM Trans. Comput. Theory, 2018)

Minimum Bisection Is Fixed-Parameter Tractable. - Marek Cygan; Daniel Lokshtanov; Marcin Pilipczuk; Michal Pilipczuk; Saket Saurabh 001 (SIAM J. Comput., 2019)

Improving TSP Tours Using Dynamic Programming over Tree Decompositions. - Marek Cygan; Lukasz Kowalik; Arkadiusz Socala (ACM Trans. Algorithms, 2019)

On Problems Equivalent to (min, +)-Convolution. - Marek Cygan; Marcin Mucha; Karol Wegrzycki; Michal Wlodarczyk 001 (ACM Trans. Algorithms, 2019)

Tight Bounds on Subexponential Time Approximation of Set Cover and Related Problems. - Magnús M. Halldórsson; Guy Kortsarz; Marek Cygan (WAOA, 2020)

From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More. - Parinya Chalermsook; Marek Cygan; Guy Kortsarz; Bundit Laekhanukit; Pasin Manurangsi; Danupon Nanongkai; Luca Trevisan 001 (SIAM J. Comput., 2020)

Lower Bounds for the Parameterized Complexity of Minimum Fill-in and Other Completion Problems. - Ivan Bliznets; Marek Cygan; Pawel Komosa; Michal Pilipczuk; Lukás Mach (ACM Trans. Algorithms, 2020)

Minimum Common String Partition: Exact Algorithms. - Marek Cygan; Alexander S. Kulikov; Ivan Mihajlin; Maksim Nikolaev; Grigory Reznikov (ESA, 2021)

n-CPS: Generalising Cross Pseudo Supervision to n networks for Semi-Supervised Semantic Segmentation. - Dominik Filipiak; Piotr Tempczyk; Marek Cygan (CoRR, 2021)

Randomized Contractions Meet Lean Decompositions. - Marek Cygan; Pawel Komosa; Daniel Lokshtanov; Marcin Pilipczuk; Michal Pilipczuk; Saket Saurabh 001; Magnus Wahlström (ACM Trans. Algorithms, 2021)

One Simple Trick to Fix Your Bayesian Neural Network. - Piotr Tempczyk; Ksawery Smoczynski; Philip Smolenski-Jensen; Marek Cygan (CoRR, 2022)

On All-Action Policy Gradients. - Michal Nauman; Marek Cygan (CoRR, 2022)

Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time. - Marek Cygan; Jesper Nederlof; Marcin Pilipczuk; Michal Pilipczuk; Johan M. M. van Rooij; Jakub Onufry Wojtaszczyk (ACM Trans. Algorithms, 2022)

Special Section on the Fifty-Second Annual ACM Symposium on the Theory of Computing (STOC 2020). - Arkadev Chattopadhyay; Marek Cygan; Noga Ron-Zewi; Christian Wulff-Nilsen (SIAM J. Comput., 2022)

On Many-Actions Policy Gradient. - Michal Nauman; Marek Cygan (ICML, 2023)

Grasping Student: semi-supervised learning for robotic manipulation. - Piotr Krzywicki; Krzysztof Ciebiera; Rafal Michaluk; Inga Maziarz; Marek Cygan (CoRR, 2023)

Mixture of Tokens: Efficient LLMs through Cross-Example Aggregation. - Szymon Antoniak; Sebastian Jaszczur; Michal Krutul; Maciej Pióro; Jakub Krajewski; Jan Ludziejewski; Tomasz Odrzygózdz; Marek Cygan (CoRR, 2023)

Decoupled Actor-Critic. - Michal Nauman; Marek Cygan (CoRR, 2023)

Scaling Laws for Fine-Grained Mixture of Experts. - Jan Ludziejewski; Jakub Krajewski; Kamil Adamczewski; Maciej Pióro; Michal Krutul; Szymon Antoniak; Kamil Ciebiera; Krystian Król; Tomasz Odrzygózdz; Piotr Sankowski; Marek Cygan; Sebastian Jaszczur (ICML, 2024)

Overestimation, Overfitting, and Plasticity in Actor-Critic: the Bitter Lesson of Reinforcement Learning. - Michal Nauman; Michal Bortkiewicz; Piotr Milos; Tomasz Trzcinski; Mateusz Ostaszewski; Marek Cygan (ICML, 2024)

Mixture of Tokens: Continuous MoE through Cross-Example Aggregation. - Szymon Antoniak; Michal Krutul; Maciej Pióro; Jakub Krajewski; Jan Ludziejewski; Kamil Ciebiera; Krystian Król; Tomasz Odrzygózdz; Marek Cygan; Sebastian Jaszczur (NeurIPS, 2024)

Bigger, Regularized, Optimistic: scaling for compute and sample efficient continuous control. - Michal Nauman; Mateusz Ostaszewski; Krzysztof Jankowski; Piotr Milos; Marek Cygan (NeurIPS, 2024)

Polite Teacher: Semi-Supervised Instance Segmentation With Mutual Learning and Pseudo-Label Thresholding. - Dominik Filipiak; Andrzej Zapala; Piotr Tempczyk; Anna Fensel; Marek Cygan (IEEE Access, 2024)

A Case for Validation Buffer in Pessimistic Actor-Critic. - Michal Nauman; Mateusz Ostaszewski; Marek Cygan (CoRR, 2024)

RoboMorph: Evolving Robot Morphology using Large Language Models. - Kevin Qiu; Krzysztof Ciebiera; Pawel Fijalkowski; Marek Cygan; Lukasz Kucinski (CoRR, 2024)

Decoupled Policy Actor-Critic: Bridging Pessimism and Risk Awareness in Reinforcement Learning. - Michal Nauman; Marek Cygan (AAAI, 2025)

Joint MoE Scaling Laws: Mixture of Experts Can Be Memory Efficient. - Jan Ludziejewski; Maciej Pióro; Jakub Krajewski; Maciej Stefaniak; Michal Krutul; Jan Malasnicki; Marek Cygan; Piotr Sankowski; Kamil Adamczewski; Piotr Milos; Sebastian Jaszczur (CoRR, 2025)

Bigger, Regularized, Categorical: High-Capacity Value Functions are Efficient Multi-Task Learners. - Michal Nauman; Marek Cygan; Carmelo Sferrazza; Aviral Kumar; Pieter Abbeel (CoRR, 2025)

FlySearch: Exploring how vision-language models explore. - Adam Pardyl; Dominik Matuszek; Mateusz Przebieracz; Marek Cygan; Bartosz Zielinski 001; Maciej Wolczyk (CoRR, 2025)

Projected Compression: Trainable Projection for Efficient Transformer Compression. - Maciej Stefaniak; Michal Krutul; Jan Malasnicki; Maciej Pióro; Jakub Krajewski; Sebastian Jaszczur; Marek Cygan; Kamil Adamczewski; Jan Ludziejewski (CoRR, 2025)

Decoupled Relative Learning Rate Schedules. - Jan Ludziejewski; Jan Malasnicki; Maciej Pióro; Michal Krutul; Kamil Ciebiera; Maciej Stefaniak; Jakub Krajewski; Piotr Sankowski; Marek Cygan; Kamil Adamczewski; Sebastian Jaszczur (CoRR, 2025)

μ-Parametrization for Mixture of Experts. - Jan Malasnicki; Kamil Ciebiera; Mateusz Borun; Maciej Pióro; Jan Ludziejewski; Maciej Stefaniak; Michal Krutul; Sebastian Jaszczur; Marek Cygan; Kamil Adamczewski; Jakub Krajewski (CoRR, 2025)