Marek Cygan
Publication record assembled from the DBLP archive of ranked conferences.
Papers indexed
55
Venues
16
Active years
2008–2025
Best venue rank
A*
Where they publish
Papers
55 indexed papers, newest first.
| Year | Venue | Title | Authors |
|---|---|---|---|
| 2025 | AAAI | Decoupled Policy Actor-Critic: Bridging Pessimism and Risk Awareness in Reinforcement Learning. | Michal Nauman, Marek Cygan |
| 2025 | ICML | Joint MoE Scaling Laws: Mixture of Experts Can Be Memory Efficient. | Jan Ludziejewski, Maciej Piro, Jakub Krajewski, Maciej Stefaniak, Michal Krutul, Jan Malasnicki, Marek Cygan, Piotr Sankowski, Kamil Adamczewski, Piotr Milos, Sebastian Jaszczur |
| 2025 | IJCAI | A Case for Validation Buffer in Pessimistic Actor-Critic. | Michal Nauman, Mateusz Ostaszewski, Marek Cygan |
| 2024 | ICML | Scaling Laws for Fine-Grained Mixture of Experts. | Jan Ludziejewski, Jakub Krajewski, Kamil Adamczewski, Maciej Piro, Michal Krutul, Szymon Antoniak, Kamil Ciebiera, Krystian Krl, Tomasz Odrzygzdz, Piotr Sankowski, Marek Cygan, Sebastian Jaszczur |
| 2024 | ICML | 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 |
| 2023 | ICML | On Many-Actions Policy Gradient. | Michal Nauman, Marek Cygan |
| 2021 | ESA | Minimum Common String Partition: Exact Algorithms. | Marek Cygan, Alexander S. Kulikov, Ivan Mihajlin, Maksim Nikolaev, Grigory Reznikov |
| 2020 | WAOA | Tight Bounds on Subexponential Time Approximation of Set Cover and Related Problems. | Magns M. Halldrsson, Guy Kortsarz, Marek Cygan |
| 2018 | ESA | Online Facility Location with Deletions. | Marek Cygan, Artur Czumaj, Marcin Mucha, Piotr Sankowski |
| 2017 | AAAI | Approximation and Parameterized Complexity of Minimax Approval Voting. | Marek Cygan, Lukasz Kowalik, Arkadiusz Socala, Krzysztof Sornat |
| 2017 | ESA | Improving TSP Tours Using Dynamic Programming over Tree Decompositions. | Marek Cygan, Lukasz Kowalik, Arkadiusz Socala |
| 2017 | FOCS | 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 |
| 2017 | ICALP | On Problems Equivalent to (min, +)-Convolution. | Marek Cygan, Marcin Mucha, Karol Wegrzycki, Michal Wlodarczyk |
| 2016 | SODA | Lower bounds for the parameterized complexity of Minimum Fill-In and other completion problems. | Ivan Bliznets, Marek Cygan, Pawel Komosa, Luks Mach, Michal Pilipczuk |
| 2016 | SODA | Algorithmic Complexity of Power Law Networks. | Pawel Brach, Marek Cygan, Jakub Lacki, Piotr Sankowski |
| 2016 | SODA | Tight Bounds for Graph Homomorphism and Subgraph Isomorphism. | Marek Cygan, Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Jakub Pachocki, Arkadiusz Socala |
| 2016 | SODA | Online Pricing with Impatient Bidders. | Marek Cygan, Marcin Mucha, Piotr Sankowski, Qiang Zhang |
| 2015 | WG | Polynomial Kernelization for Removing Induced Claws and Diamonds. | Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Erik Jan van Leeuwen, Marcin Wrochna |
| 2014 | CSR | A Fast Branching Algorithm for Cluster Vertex Deletion. | Anudhyan Boral, Marek Cygan, Tomasz Kociumaka, Marcin Pilipczuk |
| 2014 | MFCS | Hitting Forbidden Subgraphs in Graphs of Bounded Treewidth. | Marek Cygan, Dniel Marx, Marcin Pilipczuk, Michal Pilipczuk |
| 2014 | STOC | Minimum bisection is fixed parameter tractable. | Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh |
| 2014 | STACS | Constant Factor Approximation for Capacitated k-Center with Outliers. | Marek Cygan, Tomasz Kociumaka |
| 2013 | ESA | Tight Kernel Bounds for Problems on Graphs with Small Degeneracy - (Extended Abstract). | Marek Cygan, Fabrizio Grandoni, Danny Hermelin |
| 2013 | FOCS | Improved Approximation for 3-Dimensional Matching via Bounded Pathwidth Local Search. | Marek Cygan |
| 2013 | FOCS | The Planar Directed K-Vertex-Disjoint Paths Problem Is Fixed-Parameter Tractable. | Marek Cygan, Dniel Marx, Marcin Pilipczuk, Michal Pilipczuk |
| 2013 | ICALP | Deterministic Single Exponential Time Algorithms for Connectivity Problems Parameterized by Treewidth. | Hans L. Bodlaender, Marek Cygan, Stefan Kratsch, Jesper Nederlof |
| 2013 | ICALP | Faster Exponential-Time Algorithms in Graphs of Bounded Average Degree. | Marek Cygan, Marcin Pilipczuk |
| 2013 | SODA | How to Sell Hyperedges: The Hypermatching Assignment Problem. | Marek Cygan, Fabrizio Grandoni, Monaldo Mastrolilli |
| 2013 | SODA | Known algorithms for EDGE CLIQUE COVER are probably optimal. | Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk |
| 2013 | STOC | Fast hamiltonicity checking via bases of perfect matchings. | Marek Cygan, Stefan Kratsch, Jesper Nederlof |
| 2013 | STACS | On Pairwise Spanners. | Marek Cygan, Fabrizio Grandoni, Telikepalli Kavitha |
| 2013 | WAOA | Online Knapsack Revisited. | Marek Cygan, Lukasz Jez |
| 2012 | ESA | A Path-Decomposition Theorem with Applications to Pricing and Covering on Trees. | Marek Cygan, Fabrizio Grandoni, Stefano Leonardi, Marcin Pilipczuk, Piotr Sankowski |
| 2012 | ESA | Steiner Forest Orientation Problems. | Marek Cygan, Guy Kortsarz, Zeev Nutov |
| 2012 | FOCS | Designing FPT Algorithms for Cut Problems Using Randomized Contractions. | Rajesh Hemant Chitnis, Marek Cygan, MohammadTaghi Hajiaghayi, Marcin Pilipczuk, Michal Pilipczuk |
| 2012 | FOCS | Algorithmic Applications of Baur-Strassen's Theorem: Shortest Cycles, Diameter and Matchings. | Marek Cygan, Harold N. Gabow, Piotr Sankowski |
| 2012 | FOCS | LP Rounding for k-Centers with Non-uniform Hard Capacities. | Marek Cygan, MohammadTaghi Hajiaghayi, Samir Khuller |
| 2012 | ICALP | Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable. | Rajesh Hemant Chitnis, Marek Cygan, Mohammad Taghi Hajiaghayi, Dniel Marx |
| 2012 | ICALP | Clique Cover and Graph Separation: New Incompressibility Results. | Marek Cygan, Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk, Magnus Wahlstrm |
| 2012 | LATIN | Solving the 2-Disjoint Connected Subgraphs Problem Faster Than 2 n. | Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk |
| 2012 | MFCS | Sitting Closer to Friends Than Enemies, Revisited. | Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk |
| 2012 | WG | On Group Feedback Vertex Set Parameterized by the Size of the Cutset. | Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk |
| 2011 | CPM | Polynomial-Time Approximation Algorithms for Weighted LCS Problem. | Marek Cygan, Marcin Kubica, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen |
| 2011 | ESA | Scheduling Partially Ordered Jobs Faster Than 2 n. | Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk |
| 2011 | FOCS | 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 |
| 2011 | ICALP | Subset Feedback Vertex Set Is Fixed-Parameter Tractable. | Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk |
| 2011 | SODA | 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 |
| 2011 | WG | Parameterized Complexity of Eulerian Deletion Problems. | Marek Cygan, Dniel Marx, Marcin Pilipczuk, Michal Pilipczuk, Ildik Schlotter |
| 2010 | CIAC | A Planar Linear Arboricity Conjecture. | Marek Cygan, Lukasz Kowalik, Borut Luzar |
| 2010 | CIAC | Irredundant Set Faster Than | Marek Cygan, Marcin Pilipczuk, Jakub Onufry Wojtaszczyk |
| 2010 | CPM | Algorithms for Three Versions of the Shortest Common Superstring Problem. | Maxime Crochemore, Marek Cygan, Costas S. Iliopoulos, Marcin Kubica, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen |
| 2010 | ESA | Fast Approximation in Subspaces by Doubling Metric Decomposition. | Marek Cygan, Lukasz Kowalik, Marcin Mucha, Marcin Pilipczuk, Piotr Sankowski |
| 2010 | WG | Kernelization Hardness of Connectivity Problems in | Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk |
| 2009 | ICALP | Exact and Approximate Bandwidth. | Marek Cygan, Marcin Pilipczuk |
| 2008 | WG | Faster Exact Bandwidth. | Marek Cygan, Marcin Pilipczuk |