no group
2024
The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds.
Innovations in Theoretical Computer Science (ITCS) 2024
The Time Complexity of Fully Sparse Matrix Multiplication.
ACM-SIAM Symposium on Discrete Algorithms (SODA) 2024
The Effect of Sparsity on -Dominating Set and Related First-Order Graph Properties.
ACM-SIAM Symposium on Discrete Algorithms (SODA) 2024
2023
Engineering a Preprocessor for Symmetry Detection.
Symposium on Experimental and Efficient Algorithms (SEA) 2023
Engineering a Preprocessor for Symmetry Detection.
Computing Research Repository (CoRR) 2023
Combinatorial Designs Meet Hypercliques: Higher Lower Bounds for Klee's Measure Problem and Related Problems in Dimensions d ≥ 4.
International Symposium on Computational Geometry (SoCG) 2023
Coverability in VASS Revisited: Improving Rackoff's Bound to Obtain Conditional Optimality.
International Colloquium on Automata, Languages and Programming (ICALP) 2023
Combinatorial Designs Meet Hypercliques: Higher Lower Bounds for Klee's Measure Problem and Related Problems in Dimensions d≥4.
Computing Research Repository (CoRR) 2023
Coverability in VASS Revisited: Improving Rackoff's Bound to Obtain Conditional Optimality.
Computing Research Repository (CoRR) 2023
Smoothed Analysis of the 2-Opt Heuristic for the TSP under Gaussian Noise.
Computing Research Repository (CoRR) 2023
The Time Complexity of Fully Sparse Matrix Multiplication.
Computing Research Repository (CoRR) 2023
The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds.
Computing Research Repository (CoRR) 2023
The Effect of Sparsity on k-Dominating Set and Related First-Order Graph Properties.
Computing Research Repository (CoRR) 2023
2022
The Fine-Grained Complexity of Multi-Dimensional Ordering Properties.
Algorithmica 2022
Dynamic Time Warping Under Translation: Approximation Guided by Space-Filling Curves.
International Symposium on Computational Geometry (SoCG) 2022
Towards Sub-Quadratic Diameter Computation in Geometric Intersection Graphs.
International Symposium on Computational Geometry (SoCG) 2022
A tight (non-combinatorial) conditional lower bound for Klee's Measure Problem in 3D.
IEEE Annual Symposium on Foundations of Computer Science (FOCS) 2022
A Structural Investigation of the Approximability of Polynomial-Time Problems.
International Colloquium on Automata, Languages and Programming (ICALP) 2022
Polygon Placement Revisited: (Degree of Freedom + 1)-SUM Hardness and an Improvement via Offline Dynamic Rectangle Union.
ACM-SIAM Symposium on Discrete Algorithms (SODA) 2022
Towards Sub-Quadratic Diameter Computation in Geometric Intersection Graphs.
Computing Research Repository (CoRR) 2022
Dynamic Time Warping Under Translation: Approximation Guided by Space-Filling Curves.
Computing Research Repository (CoRR) 2022
A Structural Investigation of the Approximability of Polynomial-Time Problems.
Computing Research Repository (CoRR) 2022
Minimizing the Sombor Index among Trees with Fixed Degree Sequence.
Computing Research Repository (CoRR) 2022
2021
Walking the dog fast in practice: Algorithm engineering of the Fréchet distance.
Journal of Computational Geometry (JoCG) 2021
Discrete Fréchet Distance under Translation: Conditional Hardness and an Improved Algorithm.
ACM Transactions on Algorithms (TALG) 2021
Fine-Grained Completeness for Optimization in P.
International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX) 2021
The Fine-Grained Complexity of Multi-Dimensional Ordering Properties.
International Symposium on Parameterized and Exact Computation (IPEC) 2021
Fine-Grained Completeness for Optimization in P.
Computing Research Repository (CoRR) 2021
Polygon Placement Revisited: (Degree of Freedom + 1)-SUM Hardness and an Improvement via Offline Dynamic Rectangle Union.
Computing Research Repository (CoRR) 2021
2020
Improved Protocols and Hardness Results for the Two-Player Cryptogenography Problem.
IEEE Transactions on Information Theory 2020
Finding Small Satisfying Assignments Faster Than Brute Force: A Fine-Grained Perspective into Boolean Constraint Satisfaction.
Computational Complexity Conference (CCC) 2020
When Lipschitz Walks Your Dog: Algorithm Engineering of the Discrete Fréchet Distance Under Translation.
European Symposium on Algorithms (ESA) 2020
Impossibility Results for Grammar-Compressed Linear Algebra.
Conference on Neural Information Processing Systems (NeurIPS) 2020
Finding Small Satisfying Assignments Faster Than Brute Force: A Fine-grained Perspective into Boolean Constraint Satisfaction.
Computing Research Repository (CoRR) 2020
When Lipschitz Walks Your Dog: Algorithm Engineering of the Discrete Fréchet Distance under Translation.
Computing Research Repository (CoRR) 2020
Impossibility Results for Grammar-Compressed Linear Algebra.
Computing Research Repository (CoRR) 2020
2019
Subquadratic Algorithms for Succinct Stable Matching.
Algorithmica 2019
Tight Conditional Lower Bounds for Longest Common Increasing Subsequence.
Algorithmica 2019
Secretary markets with local information.
Distributed Computing 2019
A Fine-Grained Analogue of Schaefer's Theorem in P: Dichotomy of Exists^k-Forall-Quantified First-Order Graph Properties.
Computational Complexity Conference (CCC) 2019
Walking the Dog Fast in Practice: Algorithm Engineering of the Fréchet Distance.
International Symposium on Computational Geometry (SoCG) 2019
Few Matches or Almost Periodicity: Faster Pattern Matching with Mismatches in Compressed Texts.
ACM-SIAM Symposium on Discrete Algorithms (SODA) 2019
Fréchet Distance Under Translation: Conditional Hardness and an Algorithm via Offline Dynamic Grid Reachability.
ACM-SIAM Symposium on Discrete Algorithms (SODA) 2019
Approximating APSP without scaling: equivalence of approximate min-plus and exact min-max.
Symposium on the Theory of Computing (STOC) 2019
Walking the Dog Fast in Practice: Algorithm Engineering of the Fréchet Distance.
Computing Research Repository (CoRR) 2019
Approximating APSP without Scaling: Equivalence of Approximate Min-Plus and Exact Min-Max.
Computing Research Repository (CoRR) 2019
2018
On Nondeterministic Derandomization of Freivalds' Algorithm: Consequences, Avenues and Algorithmic Progress.
European Symposium on Algorithms (ESA) 2018
Multivariate Fine-Grained Complexity of Longest Common Subsequence.
ACM-SIAM Symposium on Discrete Algorithms (SODA) 2018
Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-And-Solve.
Computing Research Repository (CoRR) 2018
Multivariate Fine-Grained Complexity of Longest Common Subsequence.
Computing Research Repository (CoRR) 2018
On Nondeterministic Derandomization of Freivalds' Algorithm: Consequences, Avenues and Algorithmic Progress.
Computing Research Repository (CoRR) 2018
Fréchet Distance Under Translation: Conditional Hardness and an Algorithm via Offline Dynamic Grid Reachability.
Computing Research Repository (CoRR) 2018
2017
Improved Approximation for Fréchet Distance on c-Packed Curves Matching Conditional Lower Bounds.
International Journal of Computational Geometry and Applications 2017
Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-and-Solve.
IEEE Annual Symposium on Foundations of Computer Science (FOCS) 2017
On the Fine-Grained Complexity of One-Dimensional Dynamic Programming.
International Colloquium on Automata, Languages and Programming (ICALP) 2017
Tight Conditional Lower Bounds for Longest Common Increasing Subsequence.
International Symposium on Parameterized and Exact Computation (IPEC) 2017
On the Fine-grained Complexity of One-Dimensional Dynamic Programming.
Computing Research Repository (CoRR) 2017
Tight Conditional Lower Bounds for Longest Common Increasing Subsequence.
Computing Research Repository (CoRR) 2017
2016
Tight(er) bounds for similarity measures, smoothed approximation and broadcasting.
Saarland University, Germany 2016
Improved Protocols and Hardness Results for the Two-Player Cryptogenography Problem.
International Colloquium on Automata, Languages and Programming (ICALP) 2016
Improved Protocols and Hardness Results for the Two-Player Cryptogenography Problem.
Computing Research Repository (CoRR) 2016
2015
A Quantization Framework for Smoothed Analysis of Euclidean Optimization Problems.
Algorithmica 2015
Optimizing linear functions with the (1+λ) evolutionary algorithm - Different asymptotic runtimes for different instances.
Theoretical Computer Science 2015
Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping.
IEEE Annual Symposium on Foundations of Computer Science (FOCS) 2015
Secretary Markets with Local Information.
International Colloquium on Automata, Languages and Programming (ICALP) 2015
Towards Understanding the Smoothed Approximation Ratio of the 2-Opt Heuristic.
International Colloquium on Automata, Languages and Programming (ICALP) 2015
Improved Approximation for Fréchet Distance on c-packed Curves Matching Conditional Lower Bounds.
International Symposium on Algorithms and Computation (ISAAC) 2015
On the Smoothed Approximation Ratio of the 2-Opt Heuristic for the TSP.
Cologne Twente Workshop on Graphs and Combinatorial Optimization (CTW) 2015
Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping.
Computing Research Repository (CoRR) 2015
2014
Tight Analysis of Randomized Rumor Spreading in Complete Graphs.
Workshop on Analytic Algorithmics and Combinatorics (ANALCO) 2014
Improved approximation for Fréchet distance on c-packed curves matching conditional lower bounds.
Computing Research Repository (CoRR) 2014
2013
Royal road functions and the (1 + λ) evolutionary algorithm: Almost no speed-up from larger offspring populations.
IEEE Congress on Evolutionary Computation (CEC) 2013
A Quantization Framework for Smoothed Analysis of Euclidean Optimization Problems.
European Symposium on Algorithms (ESA) 2013
How the (1+λ) evolutionary algorithm optimizes linear functions.
Annual Conference on Genetic and Evolutionary Computation (GECCO) 2013
A quantization framework for smoothed analysis on Euclidean optimization problems.
Cologne Twente Workshop on Graphs and Combinatorial Optimization (CTW) 2013
2011
Quasirandom rumor spreading: An experimental analysis.
ACM Journal of Experimental Algorithmics (JEA) 2011
Dependent Randomized Rounding: The Bipartite Case.
Symposium on Algorithm Engineering and Experiments (ALENEX) 2011
2010
Randomized Rounding for Routing and Covering Problems: Experiments and Improvements.
Symposium on Experimental and Efficient Algorithms (SEA) 2010
Randomized Rounding for Routing and Covering Problems: Experiments and Improvements
Computing Research Repository (CoRR) 2010
Quasirandom Rumor Spreading: An Experimental Analysis
Computing Research Repository (CoRR) 2010
2009
Quasirandom Rumor Spreading: An Experimental Analysis.
Symposium on Algorithm Engineering and Experiments (ALENEX) 2009