Marek Cygan

ORCID

Publication Activity (10 Years)

Years Active: 2008-2024
Publications (10 Years): 76

Top Venues

CoRR

ACM Trans. Algorithms

Algorithmica

SIAM J. Comput.

Publications

Michal Nauman, Mateusz Ostaszewski, Krzysztof Jankowski, Piotr Milos, Marek Cygan
Bigger, Regularized, Optimistic: scaling for compute and sample-efficient continuous control. CoRR (2024)
Michal Nauman, Michal Bortkiewicz, Mateusz Ostaszewski, Piotr Milos, Tomasz Trzcinski, Marek Cygan
Overestimation, Overfitting, and Plasticity in Actor-Critic: the Bitter Lesson of Reinforcement Learning. CoRR (2024)
Michal Nauman, Mateusz Ostaszewski, Marek Cygan
A Case for Validation Buffer in Pessimistic Actor-Critic. CoRR (2024)
Kevin Qiu, Krzysztof Ciebiera, Pawel Fijalkowski, Marek Cygan, Lukasz Kucinski
RoboMorph: Evolving Robot Morphology using Large Language Models. CoRR (2024)
Dominik Filipiak, Andrzej Zapala, Piotr Tempczyk, Anna Fensel, Marek Cygan
Polite Teacher: Semi-Supervised Instance Segmentation With Mutual Learning and Pseudo-Label Thresholding. IEEE Access 12 (2024)
Jakub Krajewski, Jan Ludziejewski, Kamil Adamczewski, Maciej Pióro, Michal Krutul, Szymon Antoniak, Kamil Ciebiera, Krystian Król, Tomasz Odrzygózdz, Piotr Sankowski, Marek Cygan, Sebastian Jaszczur
Scaling Laws for Fine-Grained Mixture of Experts. CoRR (2024)
Szymon Antoniak, Sebastian Jaszczur, Michal Krutul, Maciej Pióro, Jakub Krajewski, Jan Ludziejewski, Tomasz Odrzygózdz, Marek Cygan
Mixture of Tokens: Efficient LLMs through Cross-Example Aggregation. CoRR (2023)
Michal Nauman, Marek Cygan
On Many-Actions Policy Gradient. ICML (2023)
Michal Nauman, Marek Cygan
Decoupled Actor-Critic. CoRR (2023)
Piotr Krzywicki, Krzysztof Ciebiera, Rafal Michaluk, Inga Maziarz, Marek Cygan
Grasping Student: semi-supervised learning for robotic manipulation. CoRR (2023)
Piotr Tempczyk, Ksawery Smoczynski, Philip Smolenski-Jensen, Marek Cygan
One Simple Trick to Fix Your Bayesian Neural Network. CoRR (2022)
Arkadev Chattopadhyay, Marek Cygan, Noga Ron-Zewi, Christian Wulff-Nilsen
Special Section on the Fifty-Second Annual ACM Symposium on the Theory of Computing (STOC 2020). SIAM J. Comput. 51 (3) (2022)
Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michal Pilipczuk, Johan M. M. van Rooij, Jakub Onufry Wojtaszczyk
Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time. ACM Trans. Algorithms 18 (2) (2022)
Michal Nauman, Marek Cygan
On All-Action Policy Gradients. CoRR (2022)
Dominik Filipiak, Andrzej Zapala, Piotr Tempczyk, Anna Fensel, Marek Cygan
Polite Teacher: Semi-Supervised Instance Segmentation with Mutual Learning and Pseudo-Label Thresholding. CoRR (2022)
Marek Cygan, Alexander S. Kulikov, Ivan Mihajlin, Maksim Nikolaev, Grigory Reznikov
Minimum Common String Partition: Exact Algorithms. ESA (2021)
Marek Cygan, Pawel Komosa, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh, Magnus Wahlström
Randomized Contractions Meet Lean Decompositions. ACM Trans. Algorithms 17 (1) (2021)
Dominik Filipiak, Piotr Tempczyk, Marek Cygan
n-CPS: Generalising Cross Pseudo Supervision to n networks for Semi-Supervised Semantic Segmentation. CoRR (2021)
Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, Luca Trevisan
From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More. SIAM J. Comput. 49 (4) (2020)
Ivan Bliznets, Marek Cygan, Pawel Komosa, Michal Pilipczuk, Lukás Mach
Lower Bounds for the Parameterized Complexity of Minimum Fill-in and Other Completion Problems. ACM Trans. Algorithms 16 (2) (2020)
Marek Cygan, Magnús M. Halldórsson, Guy Kortsarz
Tight Bounds on Subexponential Time Approximation of Set Cover and Related Problems. CoRR (2020)
Magnús M. Halldórsson, Guy Kortsarz, Marek Cygan
Tight Bounds on Subexponential Time Approximation of Set Cover and Related Problems. WAOA (2020)
Marek Cygan, Marcin Mucha, Karol Wegrzycki, Michal Wlodarczyk
On Problems Equivalent to (min, +)-Convolution. ACM Trans. Algorithms 15 (1) (2019)
Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh
Minimum Bisection Is Fixed-Parameter Tractable. SIAM J. Comput. 48 (2) (2019)
Marek Cygan, Lukasz Kowalik, Arkadiusz Socala
Improving TSP Tours Using Dynamic Programming over Tree Decompositions. ACM Trans. Algorithms 15 (4) (2019)
Marek Cygan, Artur Czumaj, Marcin Mucha, Piotr Sankowski
Online Facility Location with Deletions. ESA (2018)
Ivan Bliznets, Marek Cygan, Pawel Komosa, Michal Pilipczuk
-free Edge Modification Problems. ACM Trans. Comput. Theory 10 (2) (2018)
Marek Cygan, Lukasz Kowalik, Arkadiusz Socala, Krzysztof Sornat
Approximation and Parameterized Complexity of Minimax Approval Voting. J. Artif. Intell. Res. 63 (2018)
Marek Cygan, Artur Czumaj, Marcin Mucha, Piotr Sankowski
Online Facility Location with Deletions. CoRR (2018)
Marek Cygan, Stefan Kratsch, Jesper Nederlof
Fast Hamiltonicity Checking Via Bases of Perfect Matchings. J. ACM 65 (3) (2018)
Maciej Jaskowski, Jakub Swiatkowski, Michal Zajac, Maciej Klimek, Jarek Potiuk, Piotr Rybicki, Piotr Polatowski, Przemyslaw Walczyk, Kacper Nowicki, Marek Cygan
Improved GQ-CNN: Deep Learning Model for Planning Robust Grasps. CoRR (2018)
Marek Cygan, Guy Kortsarz, Bundit Laekhanukit
On subexponential running times for approximating directed Steiner tree and related problems. CoRR (2018)
Marek Cygan, Pawel Komosa, Daniel Lokshtanov, Michal Pilipczuk, Marcin Pilipczuk, Saket Saurabh
Randomized contractions meet lean decompositions. CoRR (2018)
Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, Luca Trevisan
From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More. FOCS (2017)
Marek Cygan, Marcin Mucha, Karol Wegrzycki, Michal Wlodarczyk
On problems equivalent to (min, +)-convolution. CoRR (2017)
Marek Cygan, Fedor V. Fomin, Danny Hermelin, Magnus Wahlström
Randomization in Parameterized Complexity (Dagstuhl Seminar 17041). Dagstuhl Reports 7 (1) (2017)
Marek Cygan, Fabrizio Grandoni, Danny Hermelin
Tight Kernel Bounds for Problems on Graphs with Small Degeneracy. ACM Trans. Algorithms 13 (3) (2017)
Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk
Hitting forbidden subgraphs in graphs of bounded treewidth. Inf. Comput. 256 (2017)
Marek Cygan, Marcin Mucha, Karol Wegrzycki, Michal Wlodarczyk
On Problems Equivalent to (min, +)-Convolution. ICALP (2017)
Marek Cygan, Lukasz Kowalik, Arkadiusz Socala
Improving TSP Tours Using Dynamic Programming over Tree Decompositions. ESA (2017)
Marek Cygan, Lukasz Kowalik, Arkadiusz Socala
Improving TSP tours using dynamic programming over tree decomposition. CoRR (2017)
Marek Cygan, Lukasz Kowalik, Arkadiusz Socala, Krzysztof Sornat
Approximation and Parameterized Complexity of Minimax Approval Voting. AAAI (2017)
Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, Luca Trevisan
From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More. CoRR (2017)
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Erik Jan van Leeuwen, Marcin Wrochna
Polynomial Kernelization for Removing Induced Claws and Diamonds. Theory Comput. Syst. 60 (4) (2017)
Marek Cygan, Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Jakub Pachocki, Arkadiusz Socala
Tight Lower Bounds on Graph Embedding Problems. J. ACM 64 (3) (2017)
Marek Cygan, Marcin Mucha, Piotr Sankowski, Qiang Zhang
Online Pricing with Impatient Bidders. SODA (2016)
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk
On Group Feedback Vertex Set Parameterized by the Size of the Cutset. Algorithmica 74 (2) (2016)
Marek Cygan, Holger Dell, Daniel Lokshtanov, Dániel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, Magnus Wahlström
On Problems as Hard as CNF-SAT. ACM Trans. Algorithms 12 (3) (2016)
Pawel Brach, Marek Cygan, Jakub Lacki, Piotr Sankowski
Algorithmic Complexity of Power Law Networks. SODA (2016)
Ivan Bliznets, Marek Cygan, Pawel Komosa, Michal Pilipczuk
Hardness of approximation for H-free edge modification problems. CoRR (2016)
Ivan Bliznets, Marek Cygan, Pawel Komosa, Lukás Mach, Michal Pilipczuk
Lower bounds for the parameterized complexity of Minimum Fill-In and other completion problems. SODA (2016)
Marek Cygan, Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Jakub W. Pachocki, Arkadiusz Socala
Tight Lower Bounds on Graph Embedding Problems. CoRR (2016)
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk
Known Algorithms for Edge Clique Cover are Probably Optimal. SIAM J. Comput. 45 (1) (2016)
Marek Cygan, Lukasz Kowalik, Arkadiusz Socala, Krzysztof Sornat
Approximation and Parameterized Complexity of Minimax Approval Voting. CoRR (2016)
Marek Cygan, Pinar Heggernes
Foreword: Special Issue on IPEC 2014. Algorithmica 75 (2) (2016)
Marek Cygan, Marcin Kubica, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen
Polynomial-time approximation algorithms for weighted LCS problem. Discret. Appl. Math. 204 (2016)
Anudhyan Boral, Marek Cygan, Tomasz Kociumaka, Marcin Pilipczuk
A Fast Branching Algorithm for Cluster Vertex Deletion. Theory Comput. Syst. 58 (2) (2016)
Marek Cygan, Lukasz Jez, Jirí Sgall
Online Knapsack Revisited. Theory Comput. Syst. 58 (1) (2016)
Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh
Lower Bounds for Approximation Schemes for Closest String. SWAT (2016)
Rajesh Chitnis, Marek Cygan, MohammadTaghi Hajiaghayi, Marcin Pilipczuk, Michal Pilipczuk
Designing FPT Algorithms for Cut Problems Using Randomized Contractions. SIAM J. Comput. 45 (4) (2016)
Marek Cygan, Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Jakub Pachocki, Arkadiusz Socala
Tight Bounds for Graph Homomorphism and Subgraph Isomorphism. SODA (2016)
Ivan Bliznets, Marek Cygan, Pawel Komosa, Michal Pilipczuk
Hardness of Approximation for H-Free Edge Modification Problems. APPROX-RANDOM (2016)
Marek Cygan, Pinar Heggernes
Erratum to: Foreword: Special Issue on IPEC 2014. Algorithmica 75 (2) (2016)
Ivan Bliznets, Marek Cygan, Pawel Komosa, Lukás Mach, Michal Pilipczuk
Lower bounds for the parameterized complexity of Minimum Fill-in and other completion problems. CoRR (2015)
Marek Cygan, Marcin Pilipczuk
Faster exponential-time algorithms in graphs of bounded average degree. Inf. Comput. 243 (2015)
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk
Sitting Closer to Friends than Enemies, Revisited. Theory Comput. Syst. 56 (2) (2015)
Marek Cygan, Harold N. Gabow, Piotr Sankowski
Algorithmic Applications of Baur-Strassen's Theorem: Shortest Cycles, Diameter, and Matchings. J. ACM 62 (4) (2015)
Pawel Brach, Marek Cygan, Jakub Lacki, Piotr Sankowski
Algorithmic Complexity of Power Law Networks. CoRR (2015)
Rajesh Hemant Chitnis, Marek Cygan, Mohammad Taghi Hajiaghayi, Dániel Marx
Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable. ACM Trans. Algorithms 11 (4) (2015)
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Erik Jan van Leeuwen, Marcin Wrochna
Polynomial kernelization for removing induced claws and diamonds. CoRR (2015)
Hans L. Bodlaender, Marek Cygan, Stefan Kratsch, Jesper Nederlof
Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Inf. Comput. 243 (2015)
Marek Cygan, Jakub Pachocki, Arkadiusz Socala
The Hardness of Subgraph Isomorphism. CoRR (2015)
Ivan Bliznets, Marek Cygan, Pawel Komosa, Lukás Mach
Kernelization lower bound for Permutation Pattern Matching. Inf. Process. Lett. 115 (5) (2015)
Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh
Lower bounds for approximation schemes for Closest String. CoRR (2015)
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Erik Jan van Leeuwen, Marcin Wrochna
Polynomial Kernelization for Removing Induced Claws and Diamonds. WG (2015)
Marek Cygan, Tomasz Kociumaka
Approximating Upper Degree-Constrained Partial Orientations. APPROX-RANDOM (2015)
Marek Cygan, Tomasz Kociumaka
Approximating Upper Degree-Constrained Partial Orientations. CoRR (2014)
Tomasz Kociumaka, Marek Cygan
Constant Factor Approximation for Capacitated k-Center with Outliers. CoRR (2014)
Marek Cygan, Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk, Magnus Wahlström
Clique Cover and Graph Separation: New Incompressibility Results. ACM Trans. Comput. Theory 6 (2) (2014)
Ivan Bliznets, Marek Cygan, Pawel Komosa, Lukás Mach
Kernelization lower bound for Permutation Pattern Matching. CoRR (2014)
Marek Cygan, Tomasz Kociumaka
Constant Factor Approximation for Capacitated k-Center with Outliers. STACS (2014)
Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh
On Cutwidth Parameterized by Vertex Cover. Algorithmica 68 (4) (2014)
Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh
On the Hardness of Losing Width. Theory Comput. Syst. 54 (1) (2014)
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk
Solving the 2-Disjoint Connected Subgraphs Problem Faster than 2 n. Algorithmica 70 (2) (2014)
Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, Ildikó Schlotter
Parameterized Complexity of Eulerian Deletion Problems. Algorithmica 68 (1) (2014)
Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh
Minimum bisection is fixed parameter tractable. STOC (2014)
Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk
Hitting Forbidden Subgraphs in Graphs of Bounded Treewidth. MFCS (2) (2014)
Anudhyan Boral, Marek Cygan, Tomasz Kociumaka, Marcin Pilipczuk
A Fast Branching Algorithm for Cluster Vertex Deletion. CSR (2014)
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk
Scheduling Partially Ordered Jobs Faster than 2 n. Algorithmica 68 (3) (2014)
Cristina Bazgan, Morgan Chopin, Marek Cygan, Michael R. Fellows, Fedor V. Fomin, Erik Jan van Leeuwen
Parameterized complexity of firefighting. J. Comput. Syst. Sci. 80 (7) (2014)
Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk
Hitting forbidden subgraphs in graphs of bounded treewidth. CoRR (2014)
Marek Cygan, Marcin Pilipczuk
Faster exponential-time algorithms in graphs of bounded average degree CoRR (2013)
Marek Cygan, Marcin Pilipczuk
Split Vertex Deletion meets Vertex Cover: New fixed-parameter and exact exponential-time algorithms. Inf. Process. Lett. 113 (5-6) (2013)
Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk
The Planar Directed K-Vertex-Disjoint Paths Problem Is Fixed-Parameter Tractable. FOCS (2013)
Marek Cygan, Matthias Englert, Anupam Gupta, Marcin Mucha, Piotr Sankowski
Catch them if you can: how to serve impatient users. ITCS (2013)
Marek Cygan, Guy Kortsarz, Zeev Nutov
Steiner Forest Orientation Problems. SIAM J. Discret. Math. 27 (3) (2013)
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk
Known algorithms for EDGE CLIQUE COVER are probably optimal. SODA (2013)
Marek Cygan, Marcin Pilipczuk
Faster Exponential-Time Algorithms in Graphs of Bounded Average Degree. ICALP (1) (2013)
Marek Cygan, Stefan Kratsch, Jesper Nederlof
Fast hamiltonicity checking via bases of perfect matchings. STOC (2013)
Marek Cygan
Improved approximation for 3-dimensional matching via bounded pathwidth local search CoRR (2013)

Marek Cygan.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Marek Cygan