Karol Wegrzycki

CoRR, July, 2025

Fined-Grained Complexity of Ambiguity Problems on Automata and Directed Graphs.

[BibT_eX]

[DOI]

CoRR, January, 2025

A Subexponential Time Algorithm for Makespan Scheduling of Unit Jobs with Precedence Constraints.

[BibT_eX]

[DOI]

Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, 2025

Space-Efficient Algorithm for Integer Programming with Few Constraints.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2025

Fine-Grained Equivalence for Problems Related to Integer Linear Programming.

[BibT_eX]

[DOI]

Proceedings of the 16th Innovations in Theoretical Computer Science Conference, 2025

2024

Improving Lagarias-Odlyzko Algorithm For Average-Case Subset Sum: Modular Arithmetic Approach.

[BibT_eX]

[DOI]

Antoine Joux

CoRR, 2024

Polynomial Time Algorithms for Integer Programming and Unbounded Subset Sum in the Total Regime.

[BibT_eX]

[DOI]

CoRR, 2024

A polynomial-time OPTɛ-approximation algorithm for maximum independent set of connected subgraphs in a planar graph.

[BibT_eX]

[DOI]

Jana Cslovjecsek

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Sensitivity, Proximity and FPT Algorithms for Exact Matroid Problems.

[BibT_eX]

[DOI]

Friedrich Eisenbrand

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

The Tractability Border of Reachability in Simple Vector Addition Systems with States.

[BibT_eX]

[DOI]

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

Hitting Meets Packing: How Hard Can It Be?

[BibT_eX]

[DOI]

Proceedings of the 32nd Annual European Symposium on Algorithms, 2024

Parameterized Approximation for Maximum Weight Independent Set of Rectangles and Segments.

[BibT_eX]

[DOI]

Jana Cslovjecsek

Proceedings of the 32nd Annual European Symposium on Algorithms, 2024

Parameterized Algorithms on Integer Sets with Small Doubling: Integer Programming, Subset Sum and k-SUM.

[BibT_eX]

[DOI]

Tim Randolph

Proceedings of the 32nd Annual European Symposium on Algorithms, 2024

Separator Theorem and Algorithms for Planar Hyperbolic Graphs.

[BibT_eX]

[DOI]

Proceedings of the 40th International Symposium on Computational Geometry, 2024

Fine-Grained Complexity of Earth Mover's Distance Under Translation.

[BibT_eX]

[DOI]

Proceedings of the 40th International Symposium on Computational Geometry, 2024

2023

On the independence number of intersection graphs of axis-parallel segments.

[BibT_eX]

[DOI]

J. Comput. Geom., 2023

A polynomial-time OPTε-approximation algorithm for maximum independent set of connected subgraphs in a planar graph.

[BibT_eX]

[DOI]

Jana Cslovjecsek

CoRR, 2023

Bounding Generalized Coloring Numbers of Planar Graphs Using Coin Models.

[BibT_eX]

[DOI]

Electron. J. Comb., 2023

Dynamic Data Structures for Parameterized String Problems.

[BibT_eX]

[DOI]

Proceedings of the 40th International Symposium on Theoretical Aspects of Computer Science, 2023

Gap-ETH-Tight Approximation Schemes for Red-Green-Blue Separation and Bicolored Noncrossing Euclidean Travelling Salesman Tours.

[BibT_eX]

[DOI]

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Coverability in VASS Revisited: Improving Rackoff's Bound to Obtain Conditional Optimality.

[BibT_eX]

[DOI]

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

Coverability in 2-VASS with One Unary Counter is in NP.

[BibT_eX]

[DOI]

Filip Mazowiecki

Henry Sinclair-Banks

Proceedings of the Foundations of Software Science and Computation Structures, 2023

2022

Makespan Scheduling of Unit Jobs with Precedence Constraints in O(1.995n) time.

[BibT_eX]

[DOI]

CoRR, 2022

Isolation Schemes for Problems on Decomposable Graphs.

[BibT_eX]

[DOI]

Proceedings of the 39th International Symposium on Theoretical Aspects of Computer Science, 2022

Computing Generalized Convolutions Faster Than Brute Force.

[BibT_eX]

[DOI]

Proceedings of the 17th International Symposium on Parameterized and Exact Computation, 2022

2021

Improving Schroeppel and Shamir's algorithm for subset sum via orthogonal vectors.

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics.

[BibT_eX]

[DOI]

Jakub Pawlewicz

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Knapsack and Subset Sum with Small Items.

[BibT_eX]

[DOI]

Adam Polak

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

A Gap-ETH-Tight Approximation Scheme for Euclidean TSP.

[BibT_eX]

[DOI]

Sándor Kisfaludi-Bak

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

2020

Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space.

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2020

2019

Approximating APSP without scaling: equivalence of approximate min-plus and exact min-max.

[BibT_eX]

[DOI]

Karl Bringmann

Marvin Künnemann

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

A Subquadratic Approximation Scheme for Partition.

[BibT_eX]

[DOI]

Marcin Mucha

Michal Wlodarczyk

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Equal-Subset-Sum Faster Than the Meet-in-the-Middle.

[BibT_eX]

[DOI]

Proceedings of the 27th Annual European Symposium on Algorithms, 2019

2017

Why Do Cascade Sizes Follow a Power-Law?

[BibT_eX]

[DOI]

Proceedings of the 26th International Conference on World Wide Web, 2017

Improved Distance Queries and Cycle Counting by Frobenius Normal Form.

[BibT_eX]

[DOI]

Piotr Sankowski