Publications

2025

  1. Conference paper
    D1
    “EFX Allocations and Orientations on Bipartite Multi-Graphs: A Complete Picture,” in Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2025), Detroit, MI, USA.
  2. Thesis
    D1IMPR-CS
    “Share-Based and Envy-Based Approaches to Fair Division of Indivisible Goods,” Universität des Saarlandes, Saarbrücken, 2025.
  3. Conference paper
    D1
    “Achieving Maximin Share and EFX/EF1 Guarantees Simultaneously,” in Proceedings of the 39th AAAI Conference on Artificial Intelligence, Philadelphia, PA, USA, 2025.
  4. Article
    D1
    “Maximizing Nash Social Welfare in 2-Value Instances: Delineating Tractability,” Mathematics of Operations Research, 2025.
  5. Conference paper
    D1
    “Epistemic EFX Allocations Exist for Monotone Valuations,” in Proceedings of the 39th AAAI Conference on Artificial Intelligence, Philadelphia, PA, USA, 2025.
  6. Article
    D1
    “Complexity of Computing the Anti-Ramsey Numbers for Paths,” Theoretical Computer Science, vol. 1044, 2025.
  7. Conference paper
    D1
    “Distortion of Multi-Winner Elections on the Line Metric: The Polar Comparison Rule,” in Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2025), Detroit, MI, USA.
  8. Article
    D1
    “Negative-Weight Single-Source Shortest Paths in Near-Linear Time,” Communications of the ACM, vol. 68, no. 2, 2025.
  9. Conference paper
    D1
    “Global vs. s-t Vertex Connectivity Beyond Sequential: Almost-Perfect Reductions & Near-Optimal Separations,” in STOC ’25, 57th Annual ACM Symposium on Theory of Computing, Prague, Czech Republic.
  10. Conference paper
    D1
    “Deterministic Online Bipartite Edge Coloring,” in Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2025), New Orleans, LA, USA, 2025.
  11. Conference paper
    D1
    “Efficient Matroid Intersection via a Batch-Update Auction Algorithm,” in Symposium on Simplicity of Algorithms (SOSA 2025), New Orleans, LA, USA, 2025.
  12. Conference paper
    D1
    “Online Matching on 3-Uniform Hypergraphs,” in Integer Programming and Combinatorial Optimization (IPCO 2025), Baltimore, MA, USA.
  13. Conference paper
    D1
    “Stronger Adversaries Grow Cheaper Forests: Online Node-weighted Steiner Problems,” in Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2025), New Orleans, LA, USA, 2025.
  14. Conference paper
    D1
    “A Fine-grained Classification of Subquadratic Patterns for Subgraph Listing and Friends,” in STOC ’25, 57th Annual ACM Symposium on Theory of Computing, Prague, Czechia, 2025.
  15. Conference paper
    D1
    “Beating Bellman’s Algorithm for Subset Sum,” in Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2025), New Orleans, LA, USA, 2025.
  16. Conference paper
    D1
    “Approximating Klee’s Measure Problem and a Lower Bound for Union Volume Estimation,” in 41st International Symposium on Computational Geometry (SoCG 2025), Kanazawa, Japan.
  17. Article
    D1
    “Tight Fine-Grained Bounds for Direct Access on Join Queries,” ACM Transactions on Database Systems, vol. 50, no. 11, 2025.
  18. Paper
    D1
    “Near-Optimal Directed Low-Diameter Decompositions,” 2025. [Online]. Available: https://arxiv.org/abs/2502.05687.
  19. Article
    D1
    “Unbalanced Triangle Detection and Enumeration Hardness for Unions of Conjunctive Queries,” Logical Methods in Computer Science, vol. 21, no. 1, 2025.
  20. Conference paper
    D1
    “Welfare-Optimal Serial Dictatorships have Polynomial Query Complexity,” in Proceedings of the 39th AAAI Conference on Artificial Intelligence, Philadelphia, PA, USA, 2025.
  21. Paper
    D1
    “Fitting Tree Metrics and Ultrametrics in Data Streams,” 2025. [Online]. Available: https://arxiv.org/abs/2504.17776.
  22. Paper
    D1
    “Algorithm Engineering of SSSP With Negative Edge Weights,” 2025. [Online]. Available: https://arxiv.org/abs/2502.11999.
  23. Article
    D1
    “Improved Bounds for Single-Nomination Impartial Selection,” Mathematics of Operations Research, 2025.
  24. Conference paper
    D1
    “New Combinatorial Insights for Monotone Apportionment,” in Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2025), New Orleans, LA, USA, 2025.
  25. Paper
    D1
    “Shortcuts and Transitive-Closure Spanners Approximation,” 2025. [Online]. Available: https://arxiv.org/abs/2502.08032.
  26. Conference paper
    D1
    “Fair Division in a Variable Setting,” in Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2025), Detroit, MI, USA.
  27. Paper
    D1
    “No Metric to Rule Them All: Toward Principled Evaluations of Graph-Learning Datasets,” 2025. [Online]. Available: arXiv:2502.02379.
  28. Conference paper
    D1
    “Can You Link Up With Treewidth?,” in 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025), Jena, Germany, 2025.
  29. Conference paper
    D1
    “From Graph Properties to Graph Parameters: Tight Bounds for Counting on Small Subgraphs,” in Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2025), New Orleans, LA, USA, 2025.
  30. Paper
    D1
    “Fined-Grained Complexity of Ambiguity Problems on Automata and Directed Graphs,” 2025. [Online]. Available: https://arxiv.org/abs/2501.14725.
  31. Conference paper
    D1
    “Breaking the Sorting Barrier for Directed Single-Source Shortest Paths,” in STOC ’25, 57th Annual ACM Symposium on Theory of Computing, Prague, Czech Republic.
  32. Conference paper
    D1
    “A Faster Algorithm for Constrained Correlation Clustering,” in 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025), Jena, Germany, 2025.
  33. Article
    D1
    “Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part II: Hardness Results,” ACM Transactions on Computation Theory, vol. 17, no. 2, 2025.
  34. Article
    D1
    “Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs,” ACM Transactions on Algorithms, 2025.
  35. Paper
    D1
    “Engineering Insights into Biclique Partitions and Fractional Binary Ranks of Matrices,” 2025. [Online]. Available: https://arxiv.org/abs/2502.06730.
  36. Conference paper
    D1
    “Bounded Edit Distance: Optimal Static and Dynamic Algorithms for Small Integer Weights,” in STOC ’25, 57th Annual ACM Symposium on Theory of Computing, Prague, Czech Republic.
  37. Article
    D1
    “The Iteration Number of the Weisfeiler-Leman Algorithm,” ACM Transactions on Computational Logic, vol. 26, no. 1, 2025.
  38. Article
    D1
    “Compressing CFI Graphs and Lower Bounds for the Weisfeiler-Leman Refinements,” Journal of the ACM, vol. 72, no. 3, 2025.
  39. Conference paper
    D1
    “Sublinear Data Structures for Nearest Neighbor in Ultra High Dimensions,” in 41st International Symposium on Computational Geometry (SoCG 2025), Kanazawa, Japan.
  40. Conference paper
    D1
    “Clustering to Minimize Cluster-Aware Norm Objectives,” in Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2025), New Orleans, LA, USA, 2025.
  41. Conference paper
    D1
    “Fully Dynamic Biconnectivity in Õ(log2 n) Time,” in STOC ’25, 57th Annual ACM Symposium on Theory of Computing, Prague, Czech Republic.
  42. Conference paper
    D1
    “The Long Arm of Nashian Allocation in Online p-Mean Welfare Maximization,” in 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025), Aarhus, Denmark,.
  43. Conference paper
    D1
    “Deterministic Vertex Connectivity via Common-Neighborhood Clustering and Pseudorandomness,” in STOC ’25, 57th Annual ACM Symposium on Theory of Computing, Prague, Czech Republic.
  44. Conference paper
    D1
    “On the Hardness Hierarchy for the O(n √log n) Complexity in the Word RAM,” in STOC ’25, 57th Annual ACM Symposium on Theory of Computing, Prague, Czech Republic.
  45. Conference paper
    D1
    “Near-Optimal-Time Quantum Algorithms for Approximate Pattern Matching,” in Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2025), New Orleans, LA, USA, 2025.
  46. Article
    D1
    “Vertex Connectivity in Poly-logarithmic Max-flows,” Journal of the ACM, 2025.
  47. Conference paper
    D1
    “A Subexponential Time Algorithm for Makespan Scheduling of Unit Jobs with Precedence Constraints,” in Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2025), New Orleans, LA, USA, 2025.
  48. Conference paper
    D1
    “Space-Efficient Algorithm for Integer Programming with Few Constraints,” in Integer Programming and Combinatorial Optimization (IPCO 2025), Baltimore, MA, USA.
  49. Conference paper
    D1
    “Fine-Grained Equivalence for Problems Related to Integer Linear Programming,” in 16th Innovations in Theoretical Computer Science (ITCS 2025), New York, NY, USA, 2025.
  50. Article
    D1
    “A Survey on Approximability of Traveling Salesman Problems Using the TSP-T3CO Definition Scheme,” Annals of Operations Research, 2025.

2024

  1. Paper
    D1
    “Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces,” 2024. [Online]. Available: https://arxiv.org/abs/2305.07316.
  2. Conference paper
    D1
    “Parameterized Approximation For Robust Clustering in Discrete Geometric Spaces,” in 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024), Tallinn, Estonia, 2024.
  3. Conference paper
    D1
    “The Time Complexity of Fully Sparse Matrix Multiplication,” in Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2024), Alexandria, VA, USA, 2024.
  4. Conference paper
    D1
    “Minimum Star Partitions of Simple Polygons in Polynomial Time,” in STOC ’24, 56th Annual ACM Symposium on Theory of Computing, Vancouver, Canada, 2024.
  5. Paper
    D1
    “Approximate EFX and Exact tEFX Allocations for Indivisible Chores: Improved Algorithms,” 2024. [Online]. Available: https://arxiv.org/abs/2410.18655.
  6. Paper
    D1
    “MMS Approximations Under Additive Leveled Valuations,” 2024. [Online]. Available: https://arxiv.org/abs/2410.02274.
  7. Paper
    D1
    “Polynomial Time Algorithms for Integer Programming and Unbounded Subset Sum in the Total Regime,” 2024. [Online]. Available: https://arxiv.org/abs/2407.05435.
  8. Conference paper
    D1
    “Odd Cycle Transversal on P5-free Graphs in Quasi-polynomial Time,” in Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2024), Alexandria, VA, USA, 2024.
  9. Article
    D1
    “EFX: A Simpler Approach and an (Almost) Optimal Guarantee via Rainbow Cycle Number,” Operations Research, 2024.
  10. Conference paper
    D1
    “Breaking the 3/4 Barrier for Approximate Maximin Share,” in Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2024), Alexandria, VA, USA, 2024.
  11. Conference paper
    D1
    “Improving Approximation Guarantees for Maximin Share,” in EC ’24, 25th ACM Conference on Economics and Computation, New Heaven, CT, USA, 2024.
  12. Paper
    D1
    “On the Theoretical Foundations of Data Exchange Economies,” 2024. [Online]. Available: https://arxiv.org/abs/2412.01968.
  13. Paper
    D1
    “Gabow’s Cardinality Matching Algorithm in General Graphs: Implementation and Experiments,” 2024. [Online]. Available: https://arxiv.org/abs/2409.14849.
  14. Conference paper
    D1
    “Parallel, Distributed, and Quantum Exact Single-Source Shortest Paths with Negative Edge Weights,” in 32nd Annual European Symposium on Algorithms (ESA 2024), London, UK, 2024.
  15. Conference paper
    D1
    “Randomized Strategic Facility Location with Predictions,” in Advances in Neural Information Processing Systems 37 (NeurIPS 2024), Vancouver, Canada, 2024.
  16. Paper
    D1
    “Robust Contraction Decomposition for Minor-Free Graphs and its Applications,” 2024. [Online]. Available: https://arxiv.org/abs/2412.04145.
  17. Article
    D1
    “Computing Longest Lyndon Subsequences and Longest Common Lyndon Subsequences,” Algorithmica, vol. 86, 2024.
  18. Paper
    D1
    “On the Complexity of Computing the Co-lexicographic Width of a Regular Language,” 2024. [Online]. Available: https://arxiv.org/abs/2410.04771.
  19. Conference paper
    D1
    “Maximum Flow by Augmenting Paths in n2+o(1) Time,” in IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS 2024), Chicago, IL, USA, 2024.
  20. Article
    D1
    “Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time,” Journal of the ACM, vol. 71, no. 5, 2024.
  21. Conference paper
    D1
    “Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs,” in STOC ’24, 56th Annual ACM Symposium on Theory of Computing, Vancouver, Canada, 2024.
  22. Paper
    D1
    “Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs,” 2024. [Online]. Available: https://arxiv.org/abs/2306.11828.
  23. Conference paper
    D1
    “Online Edge Coloring Is (Nearly) as Easy as Offline,” in STOC ’24, 56th Annual ACM Symposium on Theory of Computing, Vancouver, Canada, 2024.
  24. Conference paper
    D1
    “Simple and Asymptotically Optimal Online Bipartite Edge Coloring,” in Symposium on Simplicity in Algorithms (SOSA 2024), Alexandria, VA, USA, 2024.
  25. Paper
    D1
    “Deterministic Online Bipartite Edge Coloring,” 2024. [Online]. Available: https://arxiv.org/abs/2408.03661.
  26. Paper
    D1
    “Efficient Matroid Intersection via a Batch-Update Auction Algorithm,” 2024. [Online]. Available: https://arxiv.org/abs/2410.14901.
  27. Conference paper
    D1
    “The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds,” in 15th Innovations in Theoretical Computer Science Conference (ITCS 2024), Berkeley, CA, USA, 2024.
  28. Conference paper
    D1
    “Dynamic Dynamic Time Warping,” in Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2024), Alexandria, VA, USA, 2024.
  29. Conference paper
    D1
    “Fine-Grained Complexity of Earth Mover’s Distance Under Translation,” in 40th International Symposium on Computational Geometry (SoCG 2024), Athens, Greece, 2024.
  30. Conference paper
    D1
    “Even Faster Knapsack via Rectangular Monotone Min-Plus Convolution and Balancing,” in 32nd Annual European Symposium on Algorithms (ESA 2024), London, UK, 2024.
  31. Conference paper
    D1
    “Faster Sublinear-Time Edit Distance,” in Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2024), Alexandria, VA, USA, 2024.
  32. Conference paper
    D1
    “Approximating Subset Sum Ratio faster than Subset Sum,” in Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2024), Alexandria, VA, USA, 2024.
  33. Conference paper
    D1
    “Exploring the Approximability Landscape of 3SUM,” in 32nd Annual European Symposium on Algorithms (ESA 2024), London, UK, 2024.
  34. Conference paper
    D1
    “Knapsack with Small Items in Near-Quadratic Time,” in STOC ’24, 56th Annual ACM Symposium on Theory of Computing, Vancouver, Canada, 2024.
  35. Article
    D1
    “Optimizing Over Serial Dictatorships,” Theory of Computing Systems, vol. 68, 2024.
  36. Thesis
    D1IMPR-CS
    “Algorithms for Knapsacks, Paths and Strings,” Universität des Saarlandes, Saarbrücken, 2024.
  37. Conference paper
    D1
    “Packing a Knapsack with Items Owned by Strategic Agents,” in 20th Conference on Web and Internet Economics (WINE 2024), Edinburgh, UK.
  38. Conference paper
    D1
    “Impartial Selection Under Combinatorial Constraints,” in 20th Conference on Web and Internet Economics (WINE 2024), Edinburgh, UK.
  39. Article
    D1
    “New bounds on the anti-Ramsey numbers of star graphs via maximum edge q-coloring,” Discrete Mathematics, vol. 347, no. 4, 2024.
  40. Conference paper
    D1
    “The Tractability Border of Reachability in Simple Vector Addition Systems with States,” in IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS 2024), Chicago, IL, USA, 2024.
  41. Article
    D1
    “Legal Hypergraphs,” Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, vol. 382, no. 2270, 2024.
  42. Paper
    D1
    “Model-Agnostic Approximation of Constrained Forest Problems,” 2024. [Online]. Available: https://arxiv.org/abs/2407.14536.
  43. Conference paper
    D1
    “Parameterized Approximation for Maximum Weight Independent Set of Rectangles and Segments,” in 32nd Annual European Symposium on Algorithms (ESA 2024), London, UK, 2024.
  44. Conference paper
    D1
    “A Polynomial-time OPT Ɛ-Approximation Algorithm for Maximum Independent Set of Connected Subgraphs in a Planar Graph,” in Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2024), Alexandria, VA, USA, 2024.
  45. Conference paper
    D1
    “Parameterized Algorithms for Block-structured Integer Programs with Large Entries,” in Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2024), Alexandria, VA, USA, 2024.
  46. Conference paper
    D1
    “Counting Small Induced Subgraphs with Edge-monotone Properties,” in STOC ’24, 56th Annual ACM Symposium on Theory of Computing, Vancouver, Canada, 2024.
  47. Conference paper
    D1
    “Logarithmic-Time Internal Pattern Matching Queries in Compressed and Dynamic Texts,” in String Processing and Information Retrieval (SPIRES 2024), Puerto Vallarta, Mexico, 2024.
  48. Conference paper
    D1
    “Sensitivity, Proximity and FPT Algorithms for Exact Matroid Problems,” in IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS 2024), Chicago, IL, USA, 2024.
  49. Article
    D1
    “Computing Generalized Convolutions Faster Than Brute Force,” Algorithmica, vol. 86, 2024.
  50. Conference paper
    D1
    “Optimally Repurposing Existing Algorithms to Obtain Exponential-Time Approximations,” in Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2024), Alexandria, VA, USA, 2024.
  51. Conference paper
    D1
    “Deterministic 3SUM-Hardness,” in 15th Innovations in Theoretical Computer Science Conference (ITCS 2024), Berkeley, CA, USA, 2024.
  52. Conference paper
    D1
    “Hitting Meets Packing: How Hard Can It Be?,” in 32nd Annual European Symposium on Algorithms (ESA 2024), London, UK, 2024.
  53. Article
    D1
    “Self-organized Transport in Noisy Dynamic Networks,” Physical Review E, vol. 110, no. 4, 2024.
  54. Article
    D1
    “An Improved Algorithm for The k-Dyck Edit Distance Problem,” ACM Transactions on Algorithms, vol. 20, no. 3, 2024.
  55. Article
    D1
    “Domination and Cut Problems on Chordal Graphs with Bounded Leafage,” Algorithmica, vol. 86, 2024.
  56. Conference paper
    D1
    “Subexponential Parameterized Directed Steiner Network Problems on Planar Graphs: A Complete Classification,” in 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024), Tallinn, Estonia, 2024.
  57. Article
    D1
    “Satiation in Fisher Markets and Approximation of Nash Social Welfare,” Mathematics of Operations Research, vol. 49, no. 2, 2024.
  58. Paper
    D1
    “Core-Sparse Monge Matrix Multiplication: Improved Algorithm and Applications,” 2024. [Online]. Available: https://arxiv.org/abs/2408.04613.
  59. Conference paper
    D1
    “Near-Optimal Quantum Algorithms for Bounded Edit Distance and Lempel-Ziv Factorization,” in Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2024), Alexandria, VA, USA, 2024.
  60. Conference paper
    D1
    “Component Order Connectivity Admits No Polynomial Kernel Parameterized,” in 18th International Symposium on Parameterized and Exact Computation (IPEC 2024), Egham, UK, 2024.
  61. Paper
    D1
    “Shining Light on Periodic Dominating Sets in Bounded-Treewidth Graphs,” 2024. [Online]. Available: https://arxiv.org/abs/2403.07524.
  62. Paper
    D1
    “Clustering to Minimize Cluster-Aware Norm Objectives,” 2024. [Online]. Available: https://arxiv.org/abs/2410.24104.
  63. Conference paper
    D1
    “Connectivity Oracles for Predictable Vertex Failures,” in 32nd Annual European Symposium on Algorithms (ESA 2024), London, UK, 2024.
  64. Paper
    D1
    “EFX Exists for Three Types of Agents,” 2024. [Online]. Available: https://arxiv.org/abs/2410.13580.
  65. Paper
    D1
    “Improving Lagarias-Odlyzko Algorithm For Average-Case Subset Sum: Modular Arithmetic Approach,” 2024. [Online]. Available: https://arxiv.org/abs/2408.16108.
  66. Conference paper
    D1
    “Lempel-Ziv (LZ77) Factorization in Sublinear Time,” in IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS 2024), Chicago, IL, USA, 2024.
  67. Article
    D1
    “On Weighted Graph Separation Problems and Flow-Augmentation,” SIAM Journal on Discrete Mathematics, 2024.
  68. Conference paper
    D1
    “Separator Theorem and Algorithms for Planar Hyperbolic Graphs,” in 40th International Symposium on Computational Geometry (SoCG 2024), Athens, Greece, 2024.
  69. Article
    D1
    “Internal Pattern Matching Queries in a Text and Applications,” SIAM Journal on Computing, vol. 53, no. 5, 2024.
  70. Conference paper
    D1
    “On the Communication Complexity of Approximate Pattern Matching,” in STOC ’24, 56th Annual ACM Symposium on Theory of Computing, Vancouver, Canada, 2024.
  71. Article
    D1
    “Near-Optimal Search Time in δ-Optimal Space, and Vice Versa,” Algorithmica, vol. 86, 2024.
  72. Conference paper
    D1
    “Detecting Points in Integer Cones of Polytopes is Double-Exponentially Hard,” in Symposium on Simplicity in Algorithms (SOSA 2024), Alexandria, VA, USA, 2024.
  73. Paper
    D1
    “Maximizing Nash Social Welfare in 2-Value Instances: A Simpler Proof for the Half-Integer Case,” 2024. [Online]. Available: https://arxiv.org/abs/2411.06924.
  74. Conference paper
    D1
    Namrata, and A. Williams, “On the Hardness of Gray Code Problems for Combinatorial Objects,” in WALCOM: Algorithms and Computation, Kanazawa, Japan, 2024.
  75. Article
    D1
    “On the Two-Dimensional Knapsack Problem for Convex Polygons,” ACM Transactions on Algorithms, vol. 20, no. 2, 2024.
  76. Conference paper
    D1
    “Cross-Paradigm Graph Algorithms (Invited Talk),” in 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024), Tallinn, Estonia, 2024.
  77. Article
    D1
    “Strongly Sublinear Algorithms for Testing Pattern Freeness,” TheoretiCS, vol. 3, 2024.
  78. Article
    D1
    “pymnet: A Python Library for Multilayer Networks,” The Journal of Open Source Software (JOSS), vol. 9, no. 99, 2024.
  79. Conference paper
    D1
    “Parameterized Algorithms on Integer Sets with Small Doubling: Integer Programming, Subset Sum and k-SUM,” in 32nd Annual European Symposium on Algorithms (ESA 2024), London, UK, 2024.
  80. Article
    D1
    “EFX Exists for Three Agents,” Journal of the ACM, vol. 71, no. 1, 2024.
  81. Article
    D1
    “Improving Envy Freeness up to Any Good Guarantees Through Rainbow Cycle Number,” Mathematics of Operations Research, vol. 49, no. 4, 2024.
  82. Paper
    D1
    “Query Complexity Lower Bounds for Local List-Decoding and Hard-Core Predicates (Even for Small Rate and Huge Lists),” 2024. [Online]. Available: https://arxiv.org/abs/2409.01708.
  83. Paper
    D1
    “A Systematic Review of Approximability Results for Traveling Salesman Problems leveraging the TSP-T3CO Definition Scheme,” 2024. [Online]. Available: https://arxiv.org/abs/2311.00604.
  84. Conference paper
    D1
    “Parameterized Approximation Schemes for Clustering with General Norm Objectives,” in Recent Trends in Graph Decomposition, Dagstuhl, Germany, 2024, no. 8.
  85. Article
    D1
    “MAP- and MLE-Based Teaching,” Journal of Machine Learning Research, vol. 25, 2024.
  86. Conference paper
    D1
    “On Dynamic Graph Algorithms with Predictions,” in Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2024), Alexandria, VA, USA, 2024.
  87. Conference paper
    D1
    “Mapping the Multiverse of Latent Representations,” in Proceedings of the 41st International Conference on Machine Learning (ICML 2024), Vienna, Austria, 2024.

2023

  1. Conference paper
    D1
    “Parameterized Approximation Schemes for Clustering with General Norm Objectives,” in IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS 2023), Santa Cruz, CA, USA, 2023.
  2. Conference paper
    D1
    “Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics,” in STOC ’23, 55th Annual ACM Symposium on Theory of Computing, Orlando, FL, USA, 2023.
  3. Paper
    D1
    Ü. V. Çatalyürek, C. Chevalier, F. Chudigiewitsch, M. F. Faraj, M. Fellows, L. Gottesbüren, T. Heuer, G. Karypis, K. Kaya, J. Lacki, J. Langguth, X. S. Li, R. Mayer, J. Meintrup, Y. Mizutani, F. Pellegrini, F. Petrini, F. Rosamond, I. Safro, S. Schlag, C. Schulz, R. Sharma, D. Strash, B. D. Sullivan, B. Uçar, and A.-J. Yzelman, “Open Problems in (Hyper)Graph Decomposition,” 2023. [Online]. Available: https://arxiv.org/abs/2310.11812.
  4. Conference paper
    D1
    “Simplification and Improvement of MMS Approximation,” in Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence (IJCAI 2023), Macao, 2023.
  5. Conference paper
    D1
    “EFX: A Simpler Approach and an (Almost) Optimal Guarantee via Rainbow Cycle Number,” in EC 2023, 24th ACM Conference on Economics and Computation, London, UK, 2023.
  6. Conference paper
    D1
    “Fair and Efficient Allocation of Indivisible Chores with Surplus,” in Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence (IJCAI 2023), Macao, 2023.
  7. Conference paper
    D1
    “Randomized and Deterministic Maximin-share Approximations for Fractionally Subadditive Valuations,” in Advances in Neural Information Processing Systems 36 (NeurIPS 2023), New Orleans, LA, USA, 2023.
  8. Article
    D1
    “Online Metric Algorithms with Untrusted Predictions,” ACM Transactions on Algorithms, vol. 19, no. 2, 2023.
  9. Conference paper
    D1
    “Paging with Succinct Predictions,” in Proceedings of the 40th International Conference on Machine Learning (ICML 2023), Honolulu, HI, USA, 2023.
  10. Conference paper
    D1
    “Mixing Predictions for Online Metric Algorithms,” in Proceedings of the 40th International Conference on Machine Learning (ICML 2023), Honolulu, HI, USA, 2023.
  11. Article
    D1
    “Secretary and Online Matching Problems with Machine Learned Advice,” Discrete Optimization, vol. 48, no. 2, 2023.
  12. Paper
    D1
    “Mixing Predictions for Online Metric Algorithms,” 2023. [Online]. Available: https://arxiv.org/abs/2304.01781.
  13. Conference paper
    D1
    “Balanced Substructures in Bicolored Graphs,” in SOFSEM 2023: Theory and Practice of Computer Science, Nový Smokovec, Slovakia, 2023.
  14. Paper
    D1
    “Parallel and Distributed Exact Single-Source Shortest Paths with Negative Edge Weights,” 2023. [Online]. Available: https://arxiv.org/abs/2303.00811.
  15. Conference paper
    D1
    “Learning-Augmented Online TSP on Rings, Trees, Flowers and (Almost) Everywhere Else,” in 31st Annual European Symposium on Algorithms (ESA 2023), Amsterdam, The Netherlands, 2023.
  16. Conference paper
    D1
    “Small-Space Algorithms for the Online Language Distance Problem for Palindromes and Squares,” in 34th International Symposium on Algorithms and Computation (ISAAC 2023), Kyoto, Japan, 2023.
  17. Conference paper
    D1
    “Mind the Gap: Edge Facility Location Problems in Theory and Practice,” in Algorithms and Discrete Applied Mathematics (CALDAM 2023), Gandhinagar, India, 2023.
  18. Article
    D1
    “The Smoothed Number of Pareto-optimal Solutions in Bicriteria Integer Optimization,” Mathematical Programming / A, vol. 200, 2023.
  19. Paper
    D1
    “Negative-Weight Single-Source Shortest Paths in Near-linear Time,” 2023. [Online]. Available: https://arxiv.org/abs/2203.03456.
  20. Article
    D1
    “Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover,” SIAM Journal on Computing, vol. 52, no. 5, 2023.
  21. Conference paper
    D1
    “Sublinear Algorithms for (1.5+Epsilon)-Approximate Matching,” in STOC ’23, 55th Annual ACM Symposium on Theory of Computing, Orlando, FL, USA, 2023, pp. 254–266.
  22. Paper
    D1
    “Dynamic (1+ϵ)-Approximate Matching Size in Truly Sublinear Update Time,” 2023. [Online]. Available: https://arxiv.org/abs/2302.05030.
  23. Conference paper
    D1
    “Dynamic Algorithms for Packing-Covering LPs via Multiplicative Weight,” in Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023), Florence, Italy, 2023.
  24. Conference paper
    D1
    “Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time,” in Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023), Florence, Italy, 2023.
  25. Conference paper
    D1
    “Dynamic (1+ϵ)-Approximate Matching Size in Truly Sublinear Update Time,” in IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS 2023), Santa Cruz, CA, USA, 2023.
  26. Conference paper
    D1
    “Difference Determines the Degree: Structural Kernelizations of Component Order Connectivity,” in 18th International Symposium on Parameterized and Exact Computation (IPEC 2023), Amsterdam, The Netherlands, 2023.
  27. Conference paper
    D1
    “Fast Algorithms via Dynamic-Oracle Matroids,” in STOC ’23, 55th Annual ACM Symposium on Theory of Computing, Orlando, FL, USA, 2023.
  28. Conference paper
    D1
    “Incremental (1-ε)-Approximate Dynamic Matching in O(poly(1/ε)) Update Time,” in 31st Annual European Symposium on Algorithms (ESA 2023), Amsterdam, The Netherlands, 2023.
  29. Paper
    D1
    “Incremental (1 - ε)-approximate dynamic matching in O(poly(1/ε)) update time,” 2023. [Online]. Available: https://arxiv.org/abs/2302.08432.
  30. Conference paper
    D1
    “Fast Convolutions for Near-Convex Sequences,” in 34th International Symposium on Algorithms and Computation (ISAAC 2023), Kyoto, Japan, 2023.
  31. Article
    D1
    “Treedepth vs Circumference,” Combinatorica, vol. 43, 2023.
  32. Conference paper
    D1
    “Negative-Weight Single-Source Shortest Paths in Near-Linear Time: Now Faster!,” in IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS 2023), Santa Cruz, CA, USA, 2023.
  33. Conference paper
    D1
    “Faster 0-1-Knapsack via Near-Convex Min-Plus-Convolution,” in 31st Annual European Symposium on Algorithms (ESA 2023), Amsterdam, The Netherlands, 2023.
  34. Conference paper
    D1
    “Traversing the FFT Computation Tree for Dimension-Independent Sparse Fourier Transforms,” in Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023), Florence, Italy, 2023.
  35. Article
    D1
    “A Linear-Time n0.4-Approximation for Longest Common Subsequence,” ACM Transactions on Algorithms, vol. 19, no. 1, 2023.
  36. Article
    D1
    “Independence Number of Intersection Graphs of Axis-Parallel Segments,” Journal of Computational Geometry, vol. 14, no. 1, 2023.
  37. Conference paper
    D1
    “Optimal Algorithms for Bounded Weighted Edit Distance,” in IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS 2023), Santa Cruz, CA, USA, 2023.
  38. Conference paper
    D1
    “Reducing Exposure to Harmful Content via Graph Rewiring,” in KDD ’23, 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Long Beach, CA, USA, 2023.
  39. Article
    D1
    “All the world’s a (hyper)graph: A data drama,” Digital Scholarship in the Humanities, 2023.
  40. Article
    D1
    “Law Smells - Defining and Detecting Problematic Patterns in Legal Drafting,” Artificial Intelligence and Law, vol. 31, 2023.
  41. Thesis
    D1IMPR-CS
    “Beyond Flatland : Exploring Graphs in Many Dimensions,” Universität des Saarlandes, Saarbrücken, 2023.
  42. Conference paper
    D1
    “Ollivier-Ricci Curvature for Hypergraphs: A Unified Framework,” in Eleventh International Conference on Learning Representations (ICLR 2023), Kigali, Rwanda, 2023.
  43. Paper
    D1
    “Parameterized Algorithms for Block-structured Integer Programs with Large Entries,” 2023. [Online]. Available: https://arxiv.org/abs/2311.01890.
  44. Paper
    D1
    “Parameterized Complexity Classification for Interval Constraints,” 2023. [Online]. Available: https://arxiv.org/abs/2305.13889.
  45. Conference paper
    D1
    “Parameterized Complexity Classification for Interval Constraints,” in 18th International Symposium on Parameterized and Exact Computation (IPEC 2023), Amsterdam, The Netherlands, 2023.
  46. Conference paper
    D1
    “Weighted Edit Distance Computation: Strings, Trees, and Dyck,” in STOC ’23, 55th Annual ACM Symposium on Theory of Computing, Orlando, FL, USA, 2023.
  47. Conference paper
    D1
    “Gap-ETH-Tight Approximation Schemes for Red-Green-Blue Separation and Bicolored Noncrossing Euclidean Travelling Salesman Tours,” in Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023), Florence, Italy, 2023.
  48. Conference paper
    D1
    “Upward Translation of Optimal and P-Optimal Proof Systems in the Boolean Hierarchy over NP,” in 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023), Bordeaux, France, 2023.
  49. Article
    D1
    “Online Cardinality Constrained Scheduling,” Operations Research Letters, vol. 51, no. 5, 2023.
  50. Paper
    D1
    “Approximate Monotone Local Search for Weighted Problems,” 2023. [Online]. Available: https://arxiv.org/abs/2308.15306.
  51. Paper
    D1
    “Optimally Repurposing Existing Algorithms to Obtain Exponential-Time Approximations,” 2023. [Online]. Available: https://arxiv.org/abs/2306.15331.
  52. Conference paper
    D1
    “Approximate Monotone Local Search for Weighted Problems,” in 18th International Symposium on Parameterized and Exact Computation (IPEC 2023), Amsterdam, The Netherlands, 2023.
  53. Article
    D1
    “On Batch Teaching Without Collusion,” Journal of Machine Learning Research, vol. 24, 2023.
  54. Thesis
    D1IMPR-CS
    “Algorithms for Sparse Convolution and Sublinear Edit Distance,” Universität des Saarlandes, Saarbrücken, 2023.
  55. Conference paper
    D1
    “Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs,” in Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023), Florence, Italy, 2023.
  56. Article
    D1
    “Noise-Induced Network Topologies,” Physical Review Letters, vol. 130, no. 26, 2023.
  57. Paper
    D1
    “Perfect Simulation of Las Vegas Algorithms via Local Computation,” 2023. [Online]. Available: https://arxiv.org/abs/2311.11679.
  58. Article
    D1
    “Parameterized Complexity of Weighted Multicut in Trees,” Theoretical Computer Science, vol. 978, 2023.
  59. Article
    D1
    “Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters,” SIAM Journal on Discrete Mathematics, vol. 37, no. 4, 2023.
  60. Paper
    D1
    “Robust and Practical Solution of Laplacian Equations by Approximate Elimination,” 2023. [Online]. Available: https://arxiv.org/abs/2303.00709.
  61. Article
    D1
    “Tight Bound for the Number of Distinct Palindromes in a Tree,” The Electronic Journal of Combinatorics, vol. 30, no. 2, 2023.
  62. Conference paper
    D1
    “A Constant-Factor Approximation Algorithm for Reconciliation k-Median,” in Proceedings of the 26th International Conference on Artificial Intelligence and Statistics (AISTATS 2023), Valencia, Spain, 2023.
  63. Conference paper
    D1
    “An Algorithmic Bridge Between Hamming and Levenshtein Distances,” in 14th Innovations in Theoretical Computer Science Conference (ITCS 2023), Cambridge, MA, USA, 2023.
  64. Conference paper
    D1
    “Fully Dynamic Exact Edge Connectivity in Sublinear Time,” in Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023), Florence, Italy, 2023.
  65. Conference paper
    D1
    “Learning-Augmented Algorithms for Online TSP on the Line,” in Proceedings of the 37th AAAI Conference on Artificial Intelligence, Washington, DC, USA, 2023.
  66. Article
    D1
    “The Hamilton Compression of Highly Symmetric Graphs,” Annals of Combinatorics, vol. 28, 2023.
  67. Conference paper
    D1
    “Coloring Mixed and Directional Interval Graphs,” in Graph Drawing and Network Visualization (GD 2022), Tokyo, Japan, 2023.
  68. Conference paper
    D1
    “Who can Submit an Excellent Review for this Manuscript in the Next 30 Days? - Peer Reviewing in the Age of Overload,” in ACM/IEEE Joint Conference on Digital Libraries (JCDL 2023), Santa Fe, NM, USA, 2023.
  69. Conference paper
    D1
    “Fixed-Parameter Tractability of Directed Multicut with Three Terminal Pairs Parameterized by the Size of the Cutset: Twin-width Meets Flow-Augmentation,” in Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023), Florence, Italy, 2023.
  70. Paper
    D1
    “Connectivity Oracles for Predictable Vertex Failures,” 2023. [Online]. Available: https://arxiv.org/abs/2312.08489.
  71. Conference paper
    D1
    “Linear-Time Computation of Cyclic Roots and Cyclic Covers of a String,” in 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023), Marne-la-Vallée, France, 2023.
  72. Conference paper
    D1
    “Structural Parameterizations of b-Coloring,” in 34th International Symposium on Algorithms and Computation (ISAAC 2023), Kyoto, Japan, 2023.
  73. Conference paper
    D1
    “Finding a Small Vertex Cut on Distributed Networks,” in STOC ’23, 55th Annual ACM Symposium on Theory of Computing, Orlando, FL, USA, 2023.
  74. Conference paper
    D1
    “Collapsing the Hierarchy of Compressed Data Structures: Suffix Arrays in Optimal Compressed Space,” in IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS 2023), Santa Cruz, CA, USA, 2023.
  75. Conference paper
    D1
    “Breaking the O(n)-Barrier in the Construction of Compressed Suffix Arrays,” in Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023), Florence, Italy, 2023.
  76. Conference paper
    D1
    “Fitting Tree Metrics with Minimum Disagreements,” in 31st Annual European Symposium on Algorithms (ESA 2023), Amsterdam, The Netherlands, 2023.
  77. Article
    D1
    “Primal and Dual Combinatorial Dimensions,” Discrete Applied Mathematics, vol. 327, 2023.
  78. Conference paper
    D1
    “Approximating Edit Distance in the Fully Dynamic Model,” in IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS 2023), Santa Cruz, CA, USA, 2023.
  79. Conference paper
    D1
    “Bellman-Ford Is Optimal for Shortest Hop-Bounded Paths,” in 31st Annual European Symposium on Algorithms (ESA 2023), Amsterdam, The Netherlands, 2023.
  80. Conference paper
    D1
    “Parameterized Complexity of Biclique Contraction and Balanced Biclique Contraction,” in 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023), Hyderabad, India, 2023.
  81. Paper
    D1
    “Parameterized Complexity of Biclique Contraction and Balanced Biclique Contraction,” 2023. [Online]. Available: https://arxiv.org/abs/2307.10607.
  82. Conference paper
    D1
    “Coverability in VASS Revisited: Improving Rackoff’s Bound to Obtain Conditional Optimality,” in 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), Paderborn, Germany, 2023.
  83. Conference paper
    D1
    “Near-Linear Time Approximations for Cut Problems via Fair Cuts,” in Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023), Florence, Italy, 2023.
  84. Article
    D1
    “A Mathematical Model Predicting the Abundance and Spatio-temporal Dispersal of Adfluvial Salmonid (Salvelinus Malma) fry in a Stream,” Ecological Informatics, vol. 78, 2023.
  85. Conference paper
    D1
    “Coverability in 2-VASS with One Unary Counter is in NP,” in Foundations of Software Science and Computation Structures (FoSSaCS 2023), Paris, France, 2023.
  86. Article
    D1
    “Sub-exponential Time Parameterized Algorithms for Graph Layout Problems on Digraphs with Bounded Independence Number,” Algorithmica, 2023.
  87. Article
    D1
    “A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics,” SIAM Journal on Computing, vol. 52, no. 6, 2023.
  88. Article
    D1
    “Bounding Generalized Coloring Numbers of Planar Graphs Using Coin Models,” The Electronic Journal of Combinatorics, vol. 30, no. 3, 2023.
  89. Article
    D1
    “Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space,” SIAM Journal on Discrete Mathematics, vol. 37, no. 3, 2023.
  90. Conference paper
    D1
    “Dynamic Data Structures for Parameterized String Problems,” in 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023), Hamburg, Germany, 2023.
  91. Article
    D1
    “Parameterized Counting and Cayley Graph Expanders,” SIAM Journal on Discrete Mathematics, vol. 37, no. 2, 2023.
  92. Conference paper
    D1
    “Tournaments, Johnson Graphs, and NC-Teaching,” in Proceedings of the 34th International Conference on Algorithmic Learning Theory (ALT 2023), Singapore, 2023.
  93. Paper
    D1
    “On Dynamic Graph Algorithms with Predictions,” 2023. [Online]. Available: https://arxiv.org/abs/2307.09961.
  94. Paper
    D1
    “KDEformer: Accelerating Transformers via Kernel Density Estimation,” 2023. [Online]. Available: https://arxiv.org/abs/2302.02451.

2022

  1. Conference paper
    D1
    “Hardness of Approximation in p via Short Cycle Removal: Cycle Detection, Distance Oracles, and Beyond,” in STOC ’22, 54th Annual ACM Symposium on Theory of Computing, Rome, Italy, 2022.
  2. Article
    D1
    “Scheduling Lower Bounds via AND Subset Sum,” Journal of Computer and System Sciences, vol. 127, 2022.
  3. Article
    D1
    “SETH-Based Lower Bounds for Subset Sum and Bicriteria Path,” ACM Transactions on Algorithms, vol. 18, no. 1, 2022.
  4. Article
    D1
    “Erdős–Pósa Property of Obstructions to Interval Graphs,” Journal of Graph Theory, vol. 102, no. 4, 2022.
  5. Paper
    D1
    “EFX Allocations: Simplifications and Improvements,” 2022. [Online]. Available: https://arxiv.org/abs/2205.07638.
  6. Conference paper
    D1
    “Maximizing Nash Social Welfare in 2-Value Instances,” in Proceedings of the 36th AAAI Conference on Artificial Intelligence, Virtual Conference, 2022.
  7. Paper
    D1
    “Maximizing Nash Social Welfare in 2-Value Instances: The Half-Integer Case,” 2022. [Online]. Available: https://arxiv.org/abs/2207.10949.
  8. Conference paper
    D1
    “An EF2X Allocation Protocol for Restricted Additive Valuations,” in Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI 2022), Vienna, Austria, 2022.
  9. Paper
    D1
    “An EF2X Allocation Protocol for Restricted Additive Valuations,” 2022. [Online]. Available: https://arxiv.org/abs/2202.13676.
  10. Article
    D1
    “Rapid Mixing of the Switch Markov Chain for 2-Class Joint Degree Matrices,” SIAM Journal on Discrete Mathematics, vol. 36, no. 1, 2022.
  11. Article
    D1
    “Distributed Distance-r Dominating Set on Sparse High-Girth Graphs,” Theoretical Computer Science, vol. 906, 2022.
  12. Conference paper
    D1
    “Almost Universally Optimal Distributed Laplacian Solvers via Low-Congestion Shortcuts,” in 36th International Symposium on Distributed Computing (DISC 2022), Augusta, GA, USA, 2022.
  13. Article
    D1
    “The Fine-Grained Complexity of Multi-Dimensional Ordering Properties,” Algorithmica, vol. 84, 2022.
  14. Conference paper
    D1
    “A Novel Prediction Setup for Online Speed-Scaling,” in 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022), Tórshavn, Faroe Islands, 2022.
  15. Paper
    D1
    “A Novel Prediction Setup for Online Speed-Scaling,” 2022. [Online]. Available: https://arxiv.org/abs/2112.03082.
  16. Paper
    D1
    “Paging with Succinct Predictions,” 2022. [Online]. Available: https://arxiv.org/abs/2210.02775.
  17. Conference paper
    D1
    “Cut Query Algorithms with Star Contraction,” in FOCS 2022, IEEE 63rd Annual Symposium on Foundations of Computer Science, Denver, CO, USA, 2022.
  18. Conference paper
    D1
    “Unlabeled Multi-Robot Motion Planning with Tighter Separation Bounds,” in 38th International Symposium on Computational Geometry (SoCG 2022), Berlin, Germany, 2022.
  19. Conference paper
    D1
    “Negative-Weight Single-Source Shortest Paths in Near-linear Time,” in FOCS 2022, IEEE 63rd Annual Symposium on Foundations of Computer Science, Denver, CO, USA, 2022.
  20. Paper
    D1
    “Sublinear Algorithms for (1.5+Epsilon)-Approximate Matching,” 2022. [Online]. Available: https://arxiv.org/abs/2212.00189.
  21. Conference paper
    D1
    “Nearly Optimal Communication and Query Complexity of Bipartite Matching,” in FOCS 2022, IEEE 63rd Annual Symposium on Foundations of Computer Science, Denver, CO, USA, 2022.
  22. Article
    D1
    “Physarum-inspired Multi-commodity Flow Dynamics,” Theoretical Computer Science, vol. 920, 2022.
  23. Conference paper
    D1
    “Polynomial Time Algorithms to Find an Approximate Competitive Equilibrium for Chores,” in Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2022), Virtual, 2022.
  24. Paper
    D1
    “Treedepth Vs Circumference,” 2022. [Online]. Available: https://arxiv.org/abs/2211.11410.
  25. Conference paper
    D1
    “Almost-Optimal Sublinear-Time Edit Distance in the Low Distance Regime,” in STOC ’22, 54th Annual ACM Symposium on Theory of Computing, Rome, Italy, 2022.
  26. Conference paper
    D1
    “Tight Bounds for Approximate Near Neighbor Searching for Time Series under the Fréchet Distance,” in Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2022), Virtual, 2022.
  27. Conference paper
    D1
    “Deterministic and Las Vegas Algorithms for Sparse Nonnegative Convolution,” in Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2022), Virtual, 2022.
  28. Article
    D1
    “Greedy Routing and the Algorithmic Small-World Phenomenon,” Journal of Computer and System Sciences, vol. 125, 2022.
  29. Article
    D1
    “Faster Minimization of Tardy Processing Time on a Single Machine,” Algorithmica, vol. 84, 2022.
  30. Conference paper
    D1
    “Dynamic Time Warping Under Translation: Approximation Guided by Space-Filling Curves,” in 38th International Symposium on Computational Geometry (SoCG 2022), Berlin, Germany, 2022.
  31. Conference paper
    D1
    “Towards Sub-Quadratic Diameter Computation in Geometric Intersection Graphs,” in 38th International Symposium on Computational Geometry (SoCG 2022), Berlin, Germany, 2022.
  32. Conference paper
    D1
    “A Structural Investigation of the Approximability of Polynomial-Time Problems,” in 49th EATCS International Conference on Automata, Languages, and Programming (ICALP 2022), Paris, France, 2022.
  33. Conference paper
    D1
    “Improved Sublinear-Time Edit Distance for Preprocessed Strings,” in 49th EATCS International Conference on Automata, Languages, and Programming (ICALP 2022), Paris, France, 2022.
  34. Conference paper
    D1
    “Faster Knapsack Algorithms via Bounded Monotone Min-Plus-Convolution,” in 49th EATCS International Conference on Automata, Languages, and Programming (ICALP 2022), Paris, France, 2022.
  35. Conference paper
    D1
    “Tight Fine-Grained Bounds for Direct Access on Join Queries,” in PODS ’22, 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, Philadelphia, PA, USA, 2022.
  36. Conference paper
    D1
    “Computing Continuous Dynamic Time Warping of Time Series in Polynomial Time,” in 38th International Symposium on Computational Geometry (SoCG 2022), Berlin, Germany, 2022.
  37. Thesis
    D1IMPR-CS
    “Hazard-free Clock Synchronization,” Universität des Saarlandes, Saarbrücken, 2022.
  38. Conference paper
    D1
    “Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver,” in 49th EATCS International Conference on Automata, Languages, and Programming (ICALP 2022), Paris, France, 2022.
  39. Paper
    D1
    “Faster Pattern Matching under Edit Distance,” 2022. [Online]. Available: https://arxiv.org/abs/2204.03087.
  40. Conference paper
    D1
    “Faster Pattern Matching under Edit Distance: A Reduction to Dynamic Puzzle Matching and the Seaweed Monoid of Permutation Matrices,” in FOCS 2022, IEEE 63rd Annual Symposium on Foundations of Computer Science, Denver, CO, USA, 2022.
  41. Conference paper
    D1
    “Approximate Circular Pattern Matching,” in 30th Annual European Symposium on Algorithms (ESA 2022), Berlin/Potsdam, Germany, 2022.
  42. Conference paper
    D1
    “Computing Graph Hyperbolicity Using Dominating Sets,” in Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX 2022), Alexandria, VA, USA, 2022.
  43. Article
    D1
    “Enumeration of Far-Apart Pairs by Decreasing Distance for Faster Hyperbolicity Computation,” ACM Journal of Experimental Algorithmics, vol. 27, 2022.
  44. Paper
    D1
    “All the World’s a (Hyper)Graph: A Data Drama,” 2022. [Online]. Available: https://arxiv.org/abs/2206.08225.
  45. Paper
    D1
    “Sharing and Caring: Creating a Culture of Constructive Criticism in Computational Legal Studies,” 2022. [Online]. Available: https://arxiv.org/abs/2205.01071.
  46. Article
    D1
    “Rechtsstrukturvergleichung,” Rabels Zeitschrift für ausländisches und internationales Privatrecht, vol. 86, no. 4, 2022.
  47. Conference paper
    D1
    “Differentially Describing Groups of Graphs,” in Proceedings of the 36th AAAI Conference on Artificial Intelligence, Virtual Conference, 2022.
  48. Paper
    D1
    “Differentially Describing Groups of Graphs,” 2022. [Online]. Available: https://arxiv.org/abs/2201.04064.
  49. Article
    D1
    “Indepth Combinatorial Analysis of Admissible Sets for Abstract Argumentation,” Annals of Mathematics and Artificial Intelligence, vol. 90, 2022.
  50. Article
    D1
    Á. Cseh, Y. Faenza, T. Kavitha, and V. Powers, “Understanding Popular Matchings via Stable Matchings,” SIAM Journal on Discrete Mathematics, vol. 36, no. 1, 2022.
  51. Conference paper
    D1
    “Improved Approximation Algorithms for Dyck Edit Distance and RNA Folding,” in 49th EATCS International Conference on Automata, Languages, and Programming (ICALP 2022), Paris, France, 2022.
  52. Conference paper
    D1
    “Õ(n + poly(k))-time Algorithm for Bounded Tree Edit Distance,” in FOCS 2022, IEEE 63rd Annual Symposium on Foundations of Computer Science, Denver, CO, USA, 2022.
  53. Conference paper
    D1
    “Cardinality Constrained Scheduling in Online Models,” in 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022), Marseille, France (Virtual Conference), 2022.
  54. Paper
    D1
    “Cardinality Constrained Scheduling in Online Models,” 2022. [Online]. Available: https://arxiv.org/abs/2201.05113.
  55. Conference paper
    D1
    “Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search,” in 30th Annual European Symposium on Algorithms (ESA 2022), Berlin/Potsdam, Germany, 2022.
  56. Conference paper
    D1
    “Computing Generalized Convolutions Faster Than Brute Force,” in 17th International Symposium on Parameterized and Exact Computation (IPEC 2022), Potsdam, Germany, 2022.
  57. Paper
    D1
    “Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search,” 2022. [Online]. Available: https://arxiv.org/abs/2206.13481.
  58. Conference paper
    D1
    “Hypergraph Representation via Axis-Aligned Point-Subspace Cover,” in WALCOM: Algorithms and Computation, Jember, Indonesia, 2022.
  59. Article
    D1
    “Parameterized Complexity of Directed Spanner Problems,” Algorithmica, vol. 84, 2022.
  60. Article
    D1
    “Fast All-Digital Clock Frequency Adaptation Circuit for Voltage Droop Tolerance,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 41, no. 8, 2022.
  61. Conference paper
    D1
    “Parameterized Complexity of Weighted Multicut in Trees,” in Graph-Theoretic Concepts in Computer Science (WG 2022), Tübingen, Germany, 2022.
  62. Conference paper
    D1
    “Domination and Cut Problems on Chordal Graphs with Bounded Leafage,” in 17th International Symposium on Parameterized and Exact Computation (IPEC 2022), Potsdam, Germany, 2022.
  63. Conference paper
    D1
    “Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters,” in 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022), Vienna, Austria, 2022.
  64. Paper
    D1
    “Parameterized Complexity of Weighted Multicut in Trees,” 2022. [Online]. Available: https://arxiv.org/abs/2205.10105.
  65. Paper
    D1
    “Domination and Cut Problems on Chordal Graphs with Bounded Leafage,” 2022. [Online]. Available: https://arxiv.org/abs/2208.02850.
  66. Paper
    D1
    “Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters,” 2022. [Online]. Available: https://arxiv.org/abs/2206.15424.
  67. Paper
    D1
    “Subexponential Parameterized Directed Steiner Network Problems on Planar Graphs: A Complete Classification,” 2022. [Online]. Available: https://arxiv.org/abs/2208.06015.
  68. Paper
    D1
    “Physarum Inspired Dynamics to Solve Semi-Definite Programs,” 2022. [Online]. Available: https://arxiv.org/abs/2111.02291.
  69. Conference paper
    D1
    “Improved Online Algorithm for Fractional Knapsack in the Random Order Model,” in Approximation and Online Algorithms, Lisbon, Portugal, 2022.
  70. Conference paper
    D1
    “Gap Edit Distance via Non-Adaptive Queries: Simple and Optimal,” in FOCS 2022, IEEE 63rd Annual Symposium on Foundations of Computer Science, Denver, CO, USA, 2022.
  71. Paper
    D1
    “Learning-Augmented Algorithms for Online TSP on the Line,” 2022. [Online]. Available: https://arxiv.org/abs/2206.00655.
  72. Paper
    D1
    “Coloring Mixed and Directional Interval Graphs,” 2022. [Online]. Available: https://arxiv.org/abs/2208.14250.
  73. Article
    D1
    “The Maximum-Level Vertex in an Arrangement of Lines,” Discrete & Computational Geometry, vol. 67, 2022.
  74. Conference paper
    D1
    “Fast Neural Kernel Embeddings for General Activations,” in Advances in Neural Information Processing Systems 35 (NeurIPS 2022), New Orleans, LA, USA, 2022.
  75. Conference paper
    D1
    “Random Gegenbauer Features for Scalable Kernel Methods,” in Proceedings of the 39th International Conference on Machine Learning (ICML 2022), Baltimore, MA, USA, 2022.
  76. Paper
    D1
    “Fixed-Parameter Tractability of Directed Multicut with Three Terminal Pairs Parameterized by the Size of the Cutset: Twin-width Meets Flow-Augmentation,” 2022. [Online]. Available: https://arxiv.org/abs/2207.07425.
  77. Paper
    D1
    “b-Coloring Parameterized by Pathwidth is XNLP-complete,” 2022. [Online]. Available: https://arxiv.org/abs/2209.07772.
  78. Conference paper
    D1
    “Robust and Optimal Contention Resolution without Collision Detection,” in SPAA ’22, 34th ACM Symposium on Parallelism in Algorithms and Architectures, Philadelphia, PA, USA, 2022.
  79. Paper
    D1
    “On Weighted Graph Separation Problems and Flow-Augmentation,” 2022. [Online]. Available: https://arxiv.org/abs/2208.14841.
  80. Thesis
    D1IMPR-CS
    “On Time, Time Synchronization and Noise in Time Measurement Systems,” Universität des Saarlandes, Saarbrücken, 2022.
  81. Article
    D1
    “Optimal Collusion-Free Teaching,” Journal of Machine Learning Research.
  82. Conference paper
    D1
    “A Gap-ETH-Tight Approximation Scheme for Euclidean TSP,” in FOCS 2021, IEEE 62nd Annual Symposium on Foundations of Computer Science, Denver, CO, USA (Virtual Conference), 2022.
  83. Conference paper
    D1
    “Near-Optimal Search Time in δ-Optimal Space,” in LATIN 2022: Theoretical Informatics, Guanajuato, Mexico, 2022.
  84. Article
    D1
    “Toward a Definitive Compressibility Measure for Repetitive Sequences,” IEEE Transactions on Information Theory, vol. 69, no. 4, 2022.
  85. Conference paper
    D1
    “The Complexity of Contracting Bipartite Graphs into Small Cycles,” in Graph-Theoretic Concepts in Computer Science (WG 2022), Tübingen, Germany, 2022.
  86. Paper
    D1
    “The Complexity of Contracting Bipartite Graphs into Small Cycles,” 2022. [Online]. Available: https://arxiv.org/abs/2206.07358.
  87. Conference paper
    D1
    “Polygon Placement Revisited: (Degree of Freedom + 1)-SUM Hardness and an Improvement via Offline Dynamic Rectangle Union,” in Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2022), Virtual, 2022.
  88. Paper
    D1
    “Near-Linear Time Approximations for Cut Problems via Fair Cuts,” 2022. [Online]. Available: https://arxiv.org/abs/2203.00751.
  89. Conference paper
    D1
    “On Batch Teaching with Sample Complexity Bounded by VCD,” in Advances in Neural Information Processing Systems 35 (NeurIPS 2022), New Orleans, LA, USA, 2022.
  90. Conference paper
    D1
    “Isolation Schemes for Problems on Decomposable Graphs,” in 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022), Marseille, France (Virtual Conference), 2022.
  91. Paper
    D1
    “Makespan Scheduling of Unit Jobs with Precedence Constraints in O(1.995n) time,” 2022. [Online]. Available: https://arxiv.org/abs/2208.02664.
  92. Thesis
    D1IMPR-CS
    “Fine-Grained Complexity and Algorithm Engineering of Geometric Similarity Measures,” Universität des Saarlandes, Saarbrücken, 2022.
  93. Article
    D1
    “Fair Division of Indivisible Goods for a Class of Concave Valuations,” Journal of Artificial Intelligence Research, vol. 74, 2022.
  94. Article
    D1
    “Counting Small Induced Subgraphs Satisfying Monotone Properties,” SIAM Journal on Computing, vol. 53, no. 6, 2022.
  95. Thesis
    D1IMPR-CS
    “Pulse Propagation, Graph Cover, and Packet Forwarding,” Universität des Saarlandes, Saarbrücken, 2022.
  96. Conference paper
    D1
    “Leverage Score Sampling for Tensor Product Matrices in Input Sparsity Time,” in Proceedings of the 39th International Conference on Machine Learning (ICML 2022), Baltimore, MA, USA, 2022.
  97. Paper
    D1
    “Near Optimal Reconstruction of Spherical Harmonic Expansions,” 2022. [Online]. Available: https://arxiv.org/abs/2202.12995.

2021

  1. Paper
    D1
    “Maximizing Nash Social Welfare in 2-Value Instances,” 2021. [Online]. Available: https://arxiv.org/abs/2107.08965.
  2. Paper
    D1
    “Nash Social Welfare for 2-value Instances,” 2021. [Online]. Available: https://arxiv.org/abs/2106.14816.
  3. Paper
    D1
    “Approximate Sampling and Counting of Graphs with Near-Regular Degree Intervals,” 2021. [Online]. Available: https://arxiv.org/abs/2110.09068.
  4. Conference paper
    D1
    “Robust Learning under Strong Noise via SQs,” in Proceedings of the 24th International Conference on Artificial Intelligence and Statistics (AISTATS 2021), Virtual Conference, 2021.
  5. Conference paper
    D1
    “Deterministic Distributed Algorithms and Lower Bounds in the Hybrid Model,” in 35th International Symposium on Distributed Computing (DISC 2021), Freiburg, Germany (Virtual Conference), 2021.
  6. Paper
    D1
    “Almost Universally Optimal Distributed Laplacian Solvers via Low-Congestion Shortcuts,” 2021. [Online]. Available: https://arxiv.org/abs/2109.05151.
  7. Conference paper
    D1
    “The Fine-Grained Complexity of Multi-Dimensional Ordering Properties,” in 16th International Symposium on Parameterized and Exact Computation (IPEC 2021), Lisbon, Portugal, 2021.
  8. Paper
    D1
    “Online Search for a Hyperplane in High-Dimensional Euclidean Space,” 2021. [Online]. Available: https://arxiv.org/abs/2109.04340.
  9. Conference paper
    D1
    “Fast and Simple Modular Subset Sum,” in Symposium on Simplicity in Algorithms (SOSA 2021), Alexandria, VA, USA (Virtual Conference), 2021.
  10. Article
    D1
    “Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models,” SIAM Journal on Computing, vol. 50, no. 3, 2021.
  11. Article
    D1
    “Finding and Counting Permutations via CSPs,” Algorithmica, vol. 83, 2021.
  12. Paper
    D1
    “Current Algorithms for Detecting Subgraphs of Bounded Treewidth are Probably Optimal,” 2021. [Online]. Available: https://arxiv.org/abs/2105.05062.
  13. Conference paper
    D1
    “Sparse Nonnegative Convolution is Equivalent to Dense Nonnegative Convolution,” in STOC ’21, 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual, Italy, 2021.
  14. Article
    D1
    “Walking the Dog Fast in Practice: Algorithm Engineering of the Fréchet Distance,” Journal of Computational Geometry, vol. 12, no. 1, 2021.
  15. Paper
    D1
    “Fine-Grained Complexity Theory: Conditional Lower Bounds for Computational Geometry,” 2021. [Online]. Available: https://arxiv.org/abs/2110.10283.
  16. Conference paper
    D1
    “Fine-Grained Complexity Theory: Conditional Lower Bounds for Computational Geometry,” in Connecting with Computability (CiE 2021), Ghent, Belgium (Virtual Event), 2021.
  17. Paper
    D1
    “Translating Hausdorff is Hard: Fine-Grained Lower Bounds for Hausdorff Distance Under Translation,” 2021. [Online]. Available: https://arxiv.org/abs/2101.07696.
  18. Article
    D1
    “Discrete Fréchet Distance under Translation: Conditional Hardness and an Improved Algorithm,” ACM Transactions on Algorithms, vol. 17, no. 3, 2021.
  19. Article
    D1
    “Translating Hausdorff is Hard: Fine-Grained Lower Bounds for Hausdorff Distance under Translation,” Journal of Computational Geometry, vol. 13, no. 2, 2021.
  20. Paper
    D1
    “Fast n-fold Boolean Convolution via Additive Combinatorics,” 2021. [Online]. Available: https://arxiv.org/abs/2105.03968.
  21. Paper
    D1
    “Tight Bounds for Approximate Near Neighbor Searching for Time Series under the Fréchet Distance,” 2021. [Online]. Available: https://arxiv.org/abs/2107.07792.
  22. Conference paper
    D1
    “Current Algorithms for Detecting Subgraphs of Bounded Treewidth Are Probably Optimal,” in 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), Glasgow, UK (Virtual Conference), 2021.
  23. Conference paper
    D1
    “A Linear-Time n0.4-Approximation for Longest Common Subsequence,” in 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), Glasgow, UK (Virtual Conference), 2021.
  24. Paper
    D1
    “Sparse Fourier Transform by Traversing Cooley-Tukey FFT Computation Graphs,” 2021. [Online]. Available: https://arxiv.org/abs/2107.07347.
  25. Conference paper
    D1
    “Translating Hausdorff Is Hard: Fine-Grained Lower Bounds for Hausdorff Distance Under Translation,” in 37th International Symposium on Computational Geometry (SoCG 2021), Buffalo, NY, USA (Virtual Conference), 2021.
  26. Conference paper
    D1
    “Fast n-Fold Boolean Convolution via Additive Combinatorics,” in 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), Glasgow, UK (Virtual Conference), 2021.
  27. Paper
    D1
    “Deterministic and Las Vegas Algorithms for Sparse Nonnegative Convolution,” 2021. [Online]. Available: https://arxiv.org/abs/2107.07625.
  28. Paper
    D1
    “Top-k-Convolution and the Quest for Near-Linear Output-Sensitive Subset Sum,” 2021. [Online]. Available: https://arxiv.org/abs/2107.13206.
  29. Conference paper
    D1
    “Fine-Grained Completeness for Optimization in P,” in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021), Seattle, WA, USA, 2021.
  30. Paper
    D1
    “Fine-Grained Completeness for Optimization in P,” 2021. [Online]. Available: https://arxiv.org/abs/2107.01721.
  31. Conference paper
    D1
    “A Fine-Grained Perspective on Approximating Subset Sum and Partition,” in Proceedings of the Thirty-Second ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), Alexandria, VA, USA (Virtual Conference), 2021.
  32. Conference paper
    D1
    “On Near-Linear-Time Algorithms for Dense Subset Sum,” in Proceedings of the Thirty-Second ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), Alexandria, VA, USA (Virtual Conference), 2021.
  33. Paper
    D1
    “Sparse Nonnegative Convolution Is Equivalent to Dense Nonnegative Convolution,” 2021. [Online]. Available: https://arxiv.org/abs/2105.05984.
  34. Paper
    D1
    “A Linear-Time n0.4-Approximation for Longest Common Subsequence,” 2021. [Online]. Available: https://arxiv.org/abs/2106.08195.
  35. Conference paper
    D1
    “Faster Approximate Pattern Matching: A Unified Approach,” in FOCS 2020, 61st Annual IEEE Symposium on Foundations of Computer Science, Durham, NC, USA (Virtual Conference), 2021.
  36. Thesis
    D1IMPR-CS
    “Finding Fair and Efficient Allocations,” Universität des Saarlandes, Saarbrücken, 2021.
  37. Conference paper
    D1
    “Improving EFX Guarantees through Rainbow Cycle Number,” in EC ’21, 22nd ACM Conference on Economics and Computation, Budapest, Hungary (Virtual), 2021.
  38. Conference paper
    D1
    “Combinatorial Group Testing and Sparse Recovery Schemes with Near-Optimal Decoding Time,” in FOCS 2020, 61st Annual IEEE Symposium on Foundations of Computer Science, Durham, NC, USA (Virtual Conference), 2021.
  39. Conference paper
    D1
    “Simplify Your Law: Using Information Theory to Deduplicate Legal Documents,” in 21st IEEE International Conference on Data Mining Workshops (ICDMW 2021), Virtual Conference, 2021.
  40. Article
    D1
    “Measuring Law Over Time: A Network Analytical Framework with an Application to Statutes and Regulations in the United States and Germany,” Frontiers in Physics, vol. 9, 2021.
  41. Conference paper
    D1
    “Graph Similarity Description: How Are These Graphs Similar?,” in KDD ’21, 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Virtual Event, Singapore, 2021.
  42. Conference paper
    D1
    “A Breezing Proof of the KMW Bound,” in Symposium on Simplicity in Algorithms (SOSA 2021), Alexandria, VA, USA (Virtual Conference), 2021.
  43. Article
    D1
    “Phase Transition of the 2-Choices Dynamics on Core-Periphery Networks,” Distributed Computing, vol. 34, 2021.
  44. Article
    D1
    “Memory-Adjustable Navigation Piles with Applications to Sorting and Convex Hulls,” ACM Transactions on Algorithms, vol. 17, no. 2, 2021.
  45. Article
    D1
    “Foraging-based Optimization of Menu Systems,” International Journal of Human-Computer Studies, vol. 151, 2021.
  46. Conference paper
    D1
    “Clique-Based Separators for Geometric Intersection Graphs,” in 32nd International Symposium on Algorithms and Computation (ISAAC 2021), Fukuoka, Japan, 2021.
  47. Conference paper
    D1
    “Optimal Testing of Discrete Distributions with High Probability,” in STOC ’21, 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual, Italy, 2021.
  48. Article
    D1
    “Counting Induced Subgraphs: An Algebraic Approach to #W[1]-hardness,” Algorithmica, 2021.
  49. Article
    D1
    “The VC Dimension of Metric Balls under Fréchet and Hausdorff Distances,” Discrete & Computational Geometry, 2021.
  50. Article
    D1
    “Sampling Hypergraphs with Given Degrees,” Discrete Mathematics, vol. 344, no. 11, 2021.
  51. Article
    D1
    “AZERTY Amélioré: Computational Design on a National Scale,” Communications of the ACM, vol. 64, no. 2, 2021.
  52. Article
    D1
    “Interplay of Periodic Dynamics and Noise: Insights from a Simple Adaptive System,” Physical Review E, vol. 104, no. 5, 2021.
  53. Paper
    D1
    “Improved Online Algorithm for Fractional Knapsack in the Random Order Model,” 2021. [Online]. Available: https://arxiv.org/abs/2109.04428.
  54. Conference paper
    D1
    “Isomorphism Testing for Graphs Excluding Small Minors,” in FOCS 2020, 61st Annual IEEE Symposium on Foundations of Computer Science, Durham, NC, USA (Virtual Conference), 2021.
  55. Paper
    D1
    “Primal and Dual Combinatorial Dimensions,” 2021. [Online]. Available: https://arxiv.org/abs/2108.10037.
  56. Conference paper
    D1
    “Sampling from the Gibbs Distribution in Congestion Games,” in EC ’21, 22nd ACM Conference on Economics and Computation, Budapest, Hungary (Virtual), 2021.
  57. Paper
    D1
    “Sampling from the Gibbs Distribution in Congestion Games,” 2021. [Online]. Available: https://arxiv.org/abs/2105.12982.
  58. Article
    D1
    “Computation and Efficiency of Potential Function Minimizers of Combinatorial Congestion Games,” Mathematical Programming, vol. 190, no. 1, 2021.
  59. Paper
    D1
    “Polygon Placement Revisited: (Degree of Freedom + 1)-SUM Hardness and an Improvement via Offline Dynamic Rectangle Union,” 2021. [Online]. Available: https://arxiv.org/abs/2111.02544.
  60. Conference paper
    D1
    “Approximate Minimum Directed Spanning Trees Under Congestion,” in Structural Information and Communication Complexity (SIROCCO 2021), Wrocław, Poland (Online), 2021.
  61. Article
    D1
    “2-Approximating Feedback Vertex Set in Tournaments,” ACM Transactions on Algorithms, vol. 17, no. 2, 2021.
  62. Conference paper
    D1
    “FPT-approximation for FPT Problems,” in Proceedings of the Thirty-Second ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), Alexandria, VA, USA (Virtual Conference), 2021.
  63. Article
    D1
    “A Sub-exponential FPT Algorithm and a Polynomial Kernel for Minimum Directed Bisection on Semicomplete Digraphs,” Algorithmica, vol. 83, 2021.
  64. Conference paper
    D1
    “Improving Schroeppel and Shamir’s Algorithm for Subset Sum via Orthogonal Vectors,” in STOC ’21, 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual, Italy, 2021.
  65. Article
    D1
    “Computational Design and Optimization of Electro-physiological Sensors,” Nature Communications, vol. 12, no. 1, 2021.
  66. Thesis
    D1IMPR-CS
    “Variety Membership Testing in Algebraic Complexity Theory,” Universität des Saarlandes, Saarbrücken, 2021.
  67. Conference paper
    D1
    “Knapsack and Subset Sum with Small Items,” in 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), Glasgow, UK (Virtual Conference), 2021.
  68. Conference paper
    D1
    “Fair and Efficient Allocations under Subadditive Valuations,” in AAAI Technical Track on Game Theory and Economic Paradigms, Virtual Conference, 2021.
  69. Paper
    D1
    “Improving EFX Guarantees through Rainbow Cycle Number,” 2021. [Online]. Available: https://arxiv.org/abs/2103.01628.
  70. Conference paper
    D1
    “Competitive Allocation of a Mixed Manna,” in Proceedings of the Thirty-Second ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), Alexandria, VA, USA (Virtual Conference), 2021.
  71. Article
    D1
    “A Little Charity Guarantees Almost Envy-Freeness,” SIAM Journal on Computing, vol. 50, no. 4, 2021.
  72. Conference paper
    D1
    “Detecting and Counting Small Subgraphs, and Evaluating a Parameterized Tutte Polynomial: Lower Bounds via Toroidal Grids and Cayley Graph Expanders,” in 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), Glasgow, UK (Virtual Conference), 2021.
  73. Conference paper
    D1
    “Counting Small Induced Subgraphs Satisfying Monotone Properties,” in FOCS 2020, 61st Annual IEEE Symposium on Foundations of Computer Science, Durham, NC, USA (Virtual Conference), 2021.
  74. Conference paper
    D1
    “Strong Connectivity Augmentation is FPT,” in Proceedings of the Thirty-Second ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), Alexandria, VA, USA (Virtual Conference), 2021.
  75. Thesis
    D1IMPR-CS
    “Counting Patterns in Strings and Graphs,” Universität des Saarlandes, Saarbrücken, 2021.
  76. Conference paper
    D1
    “Scaling Neural Tangent Kernels via Sketching and Random Features,” in Advances in Neural Information Processing Systems 34 (NeurIPS 2021), Virtual, 2021.

2020

  1. Conference paper
    D1
    “Impossibility Results for Grammar-Compressed Linear Algebra,” in Advances in Neural Information Processing Systems 33 (NeurIPS 2020), Virtual Event, 2020.
  2. Conference paper
    D1
    “Scheduling Lower Bounds via AND Subset Sum,” in 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), Saarbrücken, Germany (Virtual Conference), 2020.
  3. Article
    D1
    “Fooling Views: A New Lower Bound Technique for Distributed Computations under Congestion,” Distributed Computing, vol. 33, 2020.
  4. Paper
    D1
    “Scheduling Lower Bounds via AND Subset Sum,” 2020. [Online]. Available: https://arxiv.org/abs/2003.07113.
  5. Conference paper
    D1
    “Simple Local Computation Algorithms for the General Lovász Local Lemma,” in SPAA ’20, 32nd ACM Symposium on Parallelism in Algorithms and Architectures, Virtual Event, USA, 2020.
  6. Article
    D1
    “Polylogarithmic Approximation Algorithms for Weighted-F-deletion Problems,” ACM Transactions on Algorithms, vol. 16, no. 4, 2020.
  7. Conference paper
    D1
    “Parameterized Complexity of MAXIMUM EDGE COLORABLE SUBGRAPH,” in Computing and Combinatorics (COCOON 2020), Atlanta, GA, USA, 2020.
  8. Conference paper
    D1
    “Euclidean TSP in Narrow Strips,” in 36th International Symposium on Computational Geometry (SoCG 2020), Zürich, Switzerland (Virtual Conference), 2020.
  9. Paper
    D1
    “Euclidean TSP in Narrow Strips,” 2020. [Online]. Available: https://arxiv.org/abs/2003.09948.
  10. Article
    D1
    “Rapid Mixing of the Switch Markov Chain for Strongly Stable Degree Sequences,” Random Structures and Algorithms, vol. 57, no. 3, 2020.
  11. Conference paper
    D1
    “Complexity of Computing the Anti-Ramsey Numbers for Paths,” in 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020), Prague, Czech Republic (Virtual Event), 2020.
  12. Paper
    D1
    “Distributed Distance-r Dominating Set on Sparse High-Girth Graphs,” 2020. [Online]. Available: https://arxiv.org/abs/1910.02794.
  13. Article
    D1
    “Walking Through Waypoints,” Algorithmica, vol. 82, no. 7, 2020.
  14. Paper
    D1
    “Robust Learning under Strong Noise via SQs,” 2020. [Online]. Available: https://arxiv.org/abs/2010.09106.
  15. Conference paper
    D1
    “Secretary and Online Matching Problems with Machine Learned Advice,” in Advances in Neural Information Processing Systems 33 (NeurIPS 2020), Virtual Event, 2020.
  16. Paper
    D1
    “On the Approximability of the Traveling Salesman Problem with Line Neighborhoods,” 2020. [Online]. Available: https://arxiv.org/abs/2008.12075.
  17. Article
    D1
    “A PTAS for Euclidean TSP with Hyperplane Neighborhoods,” ACM Transactions on Algorithms, vol. 16, no. 3, 2020.
  18. Conference paper
    D1
    “Parallel Machine Scheduling to Minimize Energy Consumption,” in Proceedings of the Thirty-First ACM-SIAM Symposium on Discrete Algorithms (SODA 2020), Salt Lake City, UT, USA, 2020.
  19. Conference paper
    D1
    “Online Metric Algorithms with Untrusted Predictions,” in Proceedings of the 37th International Conference on Machine Learning (ICML 2020), Virtual Conference, 2020.
  20. Conference paper
    D1
    “A General Framework for Energy-Efficient Cloud Computing Mechanisms,” in AAMAS’20, 19th International Conference on Autonomous Agents and MultiAgent Systems, Auckland, New Zealand (Virtual), 2020.
  21. Paper
    D1
    “Secretary and Online Matching Problems with Machine Learned Advice,” 2020. [Online]. Available: https://arxiv.org/abs/2006.01026.
  22. Conference paper
    D1
    “Improved Bounds on Fourier Entropy and Min-entropy,” in 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020), Montpellier, France, 2020.
  23. Paper
    D1
    “Fast and Simple Modular Subset Sum,” 2020. [Online]. Available: https://arxiv.org/abs/2008.10577.
  24. Conference paper
    D1
    “Low Diameter Graph Decompositions by Approximate Distance Computation,” in 11th Innovations in Theoretical Computer Science Conference (ITCS 2020), Seattle, WA, USA, 2020.
  25. Article
    D1
    “Tracking Routes in Communication Networks,” Theoretical Computer Science, vol. 844, 2020.
  26. Paper
    D1
    “Physarum Multi-Commodity Flow Dynamics,” 2020. [Online]. Available: https://arxiv.org/abs/2009.01498.
  27. Conference paper
    D1
    “(k, l)-Medians Clustering of Trajectories Using Continuous Dynamic Time Warpin,” in 28th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS 2020), Seattle, WA, USA (Online), 2020.
  28. Paper
    D1
    “When Lipschitz Walks Your Dog: Algorithm Engineering of the Discrete Fréchet Distance under Translation,” 2020. [Online]. Available: https://arxiv.org/abs/2008.07510.
  29. Conference paper
    D1
    “Top-k-convolution and the Quest for Near-linear Output-sensitive Subset Sum,” in STOC ’20, 52nd Annual ACM SIGACT Symposium on Theory of Computing, Chicago, IL, USA, 2020.
  30. Conference paper
    D1
    “Faster Minimization of Tardy Processing Time on a Single Machine,” in 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), Saarbrücken, Germany (Virtual Conference), 2020.
  31. Conference paper
    D1
    “When Lipschitz Walks Your Dog: Algorithm Engineering of the Discrete Fréchet Distance Under Translation,” in 28th Annual European Symposium on Algorithms (ESA 2020), Pisa, Italy (Virtual Conference), 2020.
  32. Paper
    D1
    “Faster Minimization of Tardy Processing Time on a Single Machine,” 2020. [Online]. Available: https://arxiv.org/abs/2003.07104.
  33. Article
    D1
    “Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (unless APSP can),” ACM Transactions on Algorithms, vol. 16, no. 4, 2020.
  34. Article
    D1
    “Multivariate Analysis of Orthogonal Range Searching and Graph Distances Parameterized by Treewidth,” Algorithmica, vol. 82, no. 8, 2020.
  35. Paper
    D1
    “On Near-Linear-Time Algorithms for Dense Subset Sum,” 2020. [Online]. Available: https://arxiv.org/abs/2010.09096.
  36. Article
    D1
    “Synchronizer-Free Digital Link Controller,” IEEE Transactions on Circuits and Systems / I, Regular Papers, vol. 27, no. 10, 2020.
  37. Paper
    D1
    “PALS: Plesiochronous and Locally Synchronous Systems,” 2020. [Online]. Available: https://arxiv.org/abs/2003.05542.
  38. Conference paper
    D1
    “PALS: Plesiochronous and Locally Synchronous Systems,” in 26th IEEE International Symposium on Asynchronous Circuits and Systems, Salt Lake City, UT, USA, 2020.
  39. Article
    D1
    “Optimal Metastability-Containing Sorting via Parallel Prefix Computation,” IEEE Transactions on Computers, vol. 69, no. 2, 2020.
  40. Article
    D1
    “From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More,” SIAM Journal on Computing, vol. 49, no. 4, 2020.
  41. Paper
    D1
    “Faster Approximate Pattern Matching: A Unified Approach,” 2020. [Online]. Available: https://arxiv.org/abs/2004.08350.
  42. Article
    D1
    “Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions),” SIAM Journal on Computing, vol. 49, no. 2, 2020.
  43. Conference paper
    D1
    “Resource-Aware Protocols for Network Cost-Sharing Games,” in EC ’20, 21st ACM Conference on Economics and Computation, Virtual Event, Hungary, 2020.
  44. Paper
    D1
    “On the Computational Tractability of a Geographic Clustering Problem Arising in Redistricting,” 2020. [Online]. Available: https://arxiv.org/abs/2009.00188.
  45. Paper
    D1
    “A Breezing Proof of the KMW Bound,” 2020. [Online]. Available: https://arxiv.org/abs/2002.06005.
  46. Paper
    D1
    “Foraging-based Optimization of Menu Systems,” 2020. .
  47. Book chapter / section
    D1
    “Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs,” in Treewidth, Kernels, and Algorithms, Berlin: Springer, 2020.
  48. Article
    D1
    “A Framework for Exponential-Time-Hypothesis-Tight Algorithms and Lower Bounds in Geometric Intersection Graphs,” SIAM Journal on Computing, vol. 49, no. 6, 2020.
  49. Paper
    D1
    “Optimal Testing of Discrete Distributions with High Probability,” 2020. [Online]. Available: https://arxiv.org/abs/2009.06540.
  50. Article
    D1
    “Improved Protocols and Hardness Results for the Two-Player Cryptogenography Problem,” IEEE Transactions on Information Theory, vol. 66, no. 9, 2020.
  51. Paper
    D1
    “Sampling Hypergraphs with Given Degrees,” 2020. [Online]. Available: https://arxiv.org/abs/2006.12021.
  52. Article
    D1
    “Convergence of the Non-Uniform Directed Physarum Model,” Theoretical Computer Science, vol. 816, 2020.
  53. Conference paper
    D1
    “Quasi-popular Matchings, Optimality, and Extended Formulations,” in Proceedings of the Thirty-First ACM-SIAM Symposium on Discrete Algorithms (SODA 2020), Salt Lake City, UT, USA, 2020.
  54. Article
    D1
    “The Computational Complexity of Plethysm Coefficients,” Computational Complexity, vol. 29, no. 2, 2020.
  55. Conference paper
    D1
    “Parameterized Complexity of Directed Spanner Problems,” in 15th International Symposium on Parameterized and Exact Computation (IPEC 2020), Hong Kong, China (Virtual Conference), 2020.
  56. Conference paper
    D1
    “On the Complexity of Recovering Incidence Matrices,” in 28th Annual European Symposium on Algorithms (ESA 2020), Pisa, Italy (Virtual Conference), 2020.
  57. Conference paper
    D1
    “Computing and Testing Small Connectivity in Near-Linear Time and Queries via Fast Local Cut Algorithms,” in Proceedings of the Thirty-First ACM-SIAM Symposium on Discrete Algorithms (SODA 2020), Salt Lake City, UT, USA, 2020.
  58. Conference paper
    D1
    “Hitting Long Directed Cycles Is Fixed-Parameter Tractable,” in 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), Saarbrücken, Germany (Virtual Conference), 2020.
  59. Paper
    D1
    “Parameterized Algorithms for Generalizations of Directed Feedback Vertex Set,” 2020. [Online]. Available: https://arxiv.org/abs/2003.02483.
  60. Paper
    D1
    “Hitting Long Directed Cycles is Fixed-Parameter Tractable,” 2020. [Online]. Available: https://arxiv.org/abs/2003.05267.
  61. Paper
    D1
    “Isomorphism Testing for Graphs Excluding Small Minors,” 2020. [Online]. Available: https://arxiv.org/abs/2004.07671.
  62. Conference paper
    D1
    “On the Parameterized Approximability of Contraction to Classes of Chordal Graphs,” in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020), Virtual Conference, 2020.
  63. Paper
    D1
    “The Maximum-Level Vertex in an Arrangement of Lines,” 2020. [Online]. Available: http://arxiv.org/abs/2003.00518.
  64. Article
    D1
    “Conflict Free Version of Covering Problems on Graphs: Classical and Parameterized,” Theory of Computing Systems, vol. 64, 2020.
  65. Thesis
    D1IMPR-CS
    “Of Keyboards and Beyond,” Universität des Saarlandes, Saarbrücken, 2020.
  66. Conference paper
    D1
    “Reading Articles Online,” in Combinatorial Optimization and Applications (COCOA 2020), Dallas, TX, USA (Virtual Conference), 2020.
  67. Article
    D1
    “Convergence of the Non-Uniform Physarum Dynamics,” Theoretical Computer Science, vol. 816, 2020.
  68. Article
    D1
    “Complex Societies and the Growth of the Law,” Scientific Reports, vol. 10, 2020.
  69. Paper
    D1
    “A Gap-ETH-Tight Approximation Scheme for Euclidean TSP,” 2020. [Online]. Available: https://arxiv.org/abs/2011.03778.
  70. Conference paper
    D1
    “Hyperbolic Intersection Graphs and (Quasi)-Polynomial Time,” in Proceedings of the Thirty-First ACM-SIAM Symposium on Discrete Algorithms (SODA 2020), Salt Lake City, UT, USA, 2020.
  71. Article
    D1
    “Nearly ETH-tight Algorithms for Planar Steiner Tree with Terminals on Few Faces,” ACM Transactions on Algorithms, vol. 16, no. 3, 2020.
  72. Conference paper
    D1
    “A Quasi-Polynomial Algorithm for Well-Spaced Hyperbolic TSP,” in 36th International Symposium on Computational Geometry (SoCG 2020), Zürich, Switzerland (Virtual Conference), 2020.
  73. Article
    D1
    “Switch-Based Markov Chains for Sampling Hamiltonian Cycles in Dense Graphs,” The Electronic Journal of Combinatorics, vol. 27, no. 4, 2020.
  74. Paper
    D1
    “Topological Price of Anarchy Bounds for Clustering Games on Networks,” 2020. [Online]. Available: https://arxiv.org/abs/2011.09717.
  75. Conference paper
    D1
    “Finding Small Satisfying Assignments Faster Than Brute Force: A Fine-Grained Perspective into Boolean Constraint Satisfaction,” in 35th Computational Complexity Conference (CCC 2020), Saarbrücken, Germany (Virtual Conference), 2020.
  76. Paper
    D1
    “Finding Small Satisfying Assignments Faster Than Brute Force: A Fine-grained Perspective into Boolean Constraint Satisfaction,” 2020. [Online]. Available: https://arxiv.org/abs/2005.11541.
  77. Paper
    D1
    “TRIX: Low-Skew Pulse Propagation for Fault-Tolerant Hardware,” 2020. [Online]. Available: https://arxiv.org/abs/2010.01415.
  78. Conference paper
    D1
    “Brief Announcement: TRIX: Low-Skew Pulse Propagation for Fault-Tolerant Hardware,” in Stabilization, Safety, and Security of Distributed Systems (SSS 2020), Austin, TX, USA (Virtual Event), 2020.
  79. Article
    D1
    “Scanning the Issue,” Proceedings of the IEEE, vol. 108, no. 3, 2020.
  80. Article
    D1
    “Sublinear-Time Algorithms for Compressive Phase Retrieval,” IEEE Transactions on Information Theory, vol. 66, no. 11, 2020.
  81. Conference paper
    D1
    “Deterministic Sparse Fourier Transform with an ℓ_{∞} Guarantee,” in 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), Saarbrücken, Germany (Virtual Conference), 2020.
  82. Conference paper
    D1
    “Fault Tolerant Subgraphs with Applications in Kernelization,” in 11th Innovations in Theoretical Computer Science Conference (ITCS 2020), Seattle, WA, USA, 2020.
  83. Conference paper
    D1
    “A (2 + ε)-Factor Approximation Algorithm for Split Vertex Deletion,” in 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), Saarbrücken, Germany (Virtual Conference), 2020.
  84. Conference paper
    D1
    “2-Approximating Feedback Vertex Set in Tournaments,” in Proceedings of the Thirty-First ACM-SIAM Symposium on Discrete Algorithms (SODA 2020), Salt Lake City, UT, USA, 2020.
  85. Conference paper
    D1
    “An Exponential Time Parameterized Algorithm for Planar Disjoint Paths,” in STOC ’20, 52nd Annual ACM SIGACT Symposium on Theory of Computing, Chicago, IL, USA, 2020.
  86. Paper
    D1
    “Incompressibility of H-free Edge Modification Problems: Towards a Dichotomy,” 2020. [Online]. Available: https://arxiv.org/abs/2004.11761.
  87. Book chapter / section
    D1
    “Four Shorts Stories on Surprising Algorithmic Uses of Treewidth,” in Treewidth, Kernels, and Algorithms, Berlin: Springer, 2020.
  88. Paper
    D1
    “Four Short Stories on Surprising Algorithmic Uses of Treewidth,” 2020. [Online]. Available: https://arxiv.org/abs/2008.07968.
  89. Conference paper
    D1
    “Quick Separation in Chordal and Split Graphs,” in 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020), Prague, Czech Republic (Virtual Event), 2020.
  90. Article
    D1
    “Nearly Optimal Sparse Polynomial Multiplication,” IEEE Transactions on Information Theory, vol. 66, no. 11, 2020.
  91. Conference paper
    D1
    “Hypergraph Isomorphism for Groups with Restricted Composition Factors,” in 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), Saarbrücken, Germany (Virtual Conference), 2020.
  92. Article
    D1
    “Voronoi Diagrams for a Moderate-Sized Point-Set in a Simple Polygon,” Discrete & Computational Geometry, vol. 63, no. 2, 2020.
  93. Article
    D1
    “Combinatorial Optimization of Graphical User Interface Designs,” Proceedings of the IEEE, vol. 108, no. 3, 2020.
  94. Paper
    D1
    “Fair and Efficient Allocations under Subadditive Valuations,” 2020. [Online]. Available: https://arxiv.org/abs/2005.06511.
  95. Conference paper
    D1
    “EFX Exists for Three Agents,” in EC ’20, 21st ACM Conference on Economics and Computation, Virtual Event, Hungary, 2020.
  96. Paper
    D1
    “Competitive Allocation of a Mixed Manna,” 2020. [Online]. Available: https://arxiv.org/abs/2008.02753.
  97. Paper
    D1
    “EFX exists for three agents,” 2020. [Online]. Available: http://arxiv.org/abs/2002.05119.
  98. Conference paper
    D1
    “A Little Charity Guarantees Almost Envy-Freeness,” in Proceedings of the Thirty-First ACM-SIAM Symposium on Discrete Algorithms (SODA 2020), Salt Lake City, UT, USA, 2020.
  99. Conference paper
    D1
    “Seeing Far vs. Seeing Wide: Volume Complexity of Local Graph Problems Share on,” in PODC ’20, 39th Symposium on Principles of Distributed Computing, Virtual Event, Italy, 2020.
  100. Paper
    D1
    “Seeing Far vs. Seeing Wide: Volume Complexity of Local Graph Problems,” 2020. [Online]. Available: https://arxiv.org/abs/1907.08160.
  101. Conference paper
    D1
    “Counting and Finding Homomorphisms is Universal for Parameterized Complexity Theory,” in Proceedings of the Thirty-First ACM-SIAM Symposium on Discrete Algorithms (SODA 2020), Salt Lake City, UT, USA, 2020.
  102. Paper
    D1
    “Detecting and Counting Small Subgraphs, and Evaluating a Parameterized Tutte Polynomial: Lower Bounds via Toroidal Grids and Cayley Graph Expanders,” 2020. [Online]. Available: https://arxiv.org/abs/2011.03433.
  103. Paper
    D1
    “Counting Small Induced Subgraphs Satisfying Monotone Properties,” 2020. [Online]. Available: https://arxiv.org/abs/2004.06595.
  104. Conference paper
    D1
    “On the Parameterized Complexity of Grid Contraction,” in 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020), Tórshavn, Faroe Islands, 2020.
  105. Conference paper
    D1
    “On the Parameterized Complexity of Maximum Degree Contraction Problem,” in 15th International Symposium on Parameterized and Exact Computation (IPEC 2020), Hong Kong, China (Virtual Conference), 2020.
  106. Conference paper
    D1
    “Fine-Grained Complexity of Regular Expression Pattern Matching and Membership,” in 28th Annual European Symposium on Algorithms (ESA 2020), Pisa, Italy (Virtual Conference), 2020.
  107. Thesis
    D1IMPR-CS
    “Approximation Algorithms for Network Design and Cut Problems in Bounded-Treewidth,” Universität des Saarlandes, Saarbrücken, 2020.

2019

  1. Conference paper
    D1
    “SETH-Based Lower Bounds for Subset Sum and Bicriteria Path,” in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019), San Diego, CA, USA, 2019.
  2. Paper
    D1
    “Trustworthy Graph Algorithms,” 2019. [Online]. Available: http://arxiv.org/abs/1907.04065.
  3. Conference paper
    D1
    “Trustworthy Graph Algorithms,” in 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019), Aachen, Germany, 2019.
  4. Article
    D1
    “The Query Complexity of a Permutation-based Variant of Mastermind,” Discrete Applied Mathematics, vol. 260, 2019.
  5. Article
    D1
    “On Romeo and Juliet Problems: Minimizing Distance-to-Sight,” Computational Geometry: Theory and Applications, vol. 84, 2019.
  6. Article
    D1
    “Minimum-width Annulus with Outliers: Circular, Square, and Rectangular Cases,” Information Processing Letters, vol. 145, 2019.
  7. Paper
    D1
    “Ratio-Balanced Maximum Flows,” 2019. [Online]. Available: http://arxiv.org/abs/1902.11047.
  8. Article
    D1
    “Ratio-Balanced Maximum Flows,” Information Processing Letters, vol. 150, 2019.
  9. Article
    D1
    “Distributed Dominating Set Approximations beyond Planar Graphs,” ACM Transactions on Algorithms, vol. 15, no. 3, 2019.
  10. Article
    D1
    “Routing with Congestion in Acyclic Digraphs,” Information Processing Letters, vol. 151, 2019.
  11. Conference paper
    D1
    “On Polynomial-Time Congestion-Free Software-Defined Network Updates,” in IFIP Networking Conference, Warsaw, Poland, 2019.
  12. Article
    D1
    “A Fully Polynomial-Time Approximation Scheme for Speed Scaling with Sleep State,” Algorithmica, vol. 81, no. 9, 2019.
  13. Article
    D1
    “A o(n)-Competitive Deterministic Algorithm for Online Matching on a Line,” Algorithmica, vol. 81, no. 7, 2019.
  14. Conference paper
    D1
    “On the Complexity of Anchored Rectangle Packing,” in 27th Annual European Symposium on Algorithms (ESA 2019), Munich/Garching, Germany, 2019.
  15. Conference paper
    D1
    “A PTAS for Euclidean TSP with Hyperplane Neighborhoods,” in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019), San Diego, CA, USA, 2019.
  16. Article
    D1
    “The Geometry of Rank Decompositions of Matrix Multiplication II: 3 x 3 Matrices,” Journal of Pure and Applied Algebra, vol. 223, no. 8, 2019.
  17. Paper
    D1
    “Locality of Not-So-Weak Coloring,” 2019. [Online]. Available: http://arxiv.org/abs/1904.05627.
  18. Conference paper
    D1
    “Locality of Not-so-Weak Coloring,” in Structural Information and Communication Complexity (SIROCCO 2019), L’Aquila, Italy, 2019.
  19. Conference paper
    D1
    “A PTAS for l_p-Low Rank Approximation,” in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019), San Diego, CA, USA, 2019.
  20. Article
    D1
    “Self-Stabilizing Repeated Balls-into-Bins,” Distributed Computing, vol. 32, no. 1, 2019.
  21. Conference paper
    D1
    “Distributed Algorithms for Low Stretch Spanning Trees,” in 33rd International Symposium on Distributed Computing (DISC 2019), Budapest, Hungary, 2019.
  22. Paper
    D1
    “Low Diameter Graph Decompositions by Approximate Distance Computation,” 2019. [Online]. Available: http://arxiv.org/abs/1909.09002.
  23. Article
    D1
    “Two Results on Slime Mold Computations,” Theoretical Computer Science, vol. 773, 2019.
  24. Article
    D1
    “Earning and Utility Limits in Fisher Markets,” ACM Transactions on Economics and Computation, vol. 7, no. 2, 2019.
  25. Conference paper
    D1
    “Finding and Counting Permutations via CSPs,” in 14th International Symposium on Parameterized and Exact Computation (IPEC 2019), Munich, Germany, 2019.
  26. Article
    D1
    “A Game Characterisation of Tree-like Q-Resolution Size,” Journal of Computer and System Sciences, vol. 104, 2019.
  27. Conference paper
    D1
    “A Deterministic PTAS for the Algebraic Rank of Bounded Degree Polynomials,” in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019), San Diego, CA, USA, 2019.
  28. Conference paper
    D1
    “Tracking Routes in Communication Networks,” in Structural Information and Communication Complexity (SIROCCO 2019), L’Aquila, Italy, 2019.
  29. Paper
    D1
    “Variety Membership Testing, Algebraic Natural Proofs, and Geometric Complexity Theory,” 2019. [Online]. Available: http://arxiv.org/abs/1911.02534.
  30. Article
    D1
    “Minimizing Message Size in Stochastic Communication Patterns: Fast Self-Stabilizing Protocols with 3 bits,” Distributed Computing, vol. 32, no. 3, 2019.
  31. Article
    D1
    “KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation,” Journal of Experimental Algorithmics, vol. 24, no. 1, 2019.
  32. Article
    D1
    “Motivo: Fast Motif Counting via Succinct Color Coding and Adaptive Sampling,” Proccedings of the VLDB Endowment, vol. 12, no. 11, 2019.
  33. Conference paper
    D1
    “Multivariate Analysis of Orthogonal Range Searching and Graph Distances Parameterized by Treewidth,” in 13th International Symposium on Parameterized and Exact Computation (IPEC 2018), Helsinki, Finland, 2019.
  34. Conference paper
    D1
    “Walking the Dog Fast in Practice: Algorithm Engineering of the Fréchet Distance,” in 35th International Symposium on Computational Geometry (SoCG 2019), Portland, OR, USA, 2019.
  35. Conference paper
    D1
    “Fréchet Distance Under Translation: Conditional Hardness and an Algorithm via Offline Dynamic Grid Reachability,” in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019), San Diego, CA, USA, 2019.
  36. Conference paper
    D1
    “Fine-Grained Complexity Theory (Tutorial),” in 36th Symposium on Theoretical Aspects of Computer Science (STACS 2019), Berlin, Germany, 2019.
  37. Paper
    D1
    “Approximating APSP without Scaling: Equivalence of Approximate Min-Plus and Exact Min-Max,” 2019. [Online]. Available: http://arxiv.org/abs/1907.11078.
  38. Article
    D1
    “Geometric Inhomogeneous Random Graphs,” Theoretical Computer Science, vol. 760, 2019.
  39. Conference paper
    D1
    “Polyline Simplification has Cubic Complexity,” in 35th International Symposium on Computational Geometry (SoCG 2019), Portland, OR, USA, 2019.
  40. Conference paper
    D1
    “A Fine-Grained Analogue of Schaefer’s Theorem in P: Dichotomy of ∃k∀-Quantified First-Order Graph Properties,” in 34th Computational Complexity Conference (CCC 2019), New Brunswick, NJ, USA, 2019.
  41. Paper
    D1
    “Walking the Dog Fast in Practice: Algorithm Engineering of the Fréchet Distance,” 2019. [Online]. Available: http://arxiv.org/abs/1901.01504.
  42. Article
    D1
    “Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product,” SIAM Journal on Computing, vol. 48, no. 2, 2019.
  43. Conference paper
    D1
    “On Geometric Set Cover for Orthants,” in 27th Annual European Symposium on Algorithms (ESA 2019), Munich/Garching, Germany, 2019.
  44. Conference paper
    D1
    “Few Matches or Almost Periodicity: Faster Pattern Matching with Mismatches in Compressed Texts,” in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019), San Diego, CA, USA, 2019.
  45. Conference paper
    D1
    “Approximating APSP without Scaling: Equivalence of Approximate Min-Plus and Exact Min-Max,” in STOC ’19, 51st Annual ACM Symposium on the Theory of Computing, Phoenix, AZ, USA, 2019.
  46. Conference paper
    D1
    “klcluster: Center-based Clustering of Trajectories,” in 27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS 2019), Chicago, IL, USA, 2019.
  47. Paper
    D1
    “Optimal Metastability-Containing Sorting via Parallel Prefix Computation,” 2019. [Online]. Available: http://arxiv.org/abs/1911.00267.
  48. Conference paper
    D1
    “Fault Tolerant Gradient Clock Synchronization,” in PODC ’19, ACM Symposium on Principles of Distributed Computing, Toronto, Canada, 2019.
  49. Paper
    D1
    “Fault Tolerant Gradient Clock Synchronization,” 2019. [Online]. Available: http://arxiv.org/abs/1902.08042.
  50. Article
    D1
    “No Occurrence Obstructions in Geometric Complexity Theory,” Journal of the American Mathematical Society, vol. 32, 2019.
  51. Conference paper
    D1
    “A Tight Extremal Bound on the Lovász Cactus Number in Planar Graphs,” in 36th Symposium on Theoretical Aspects of Computer Science (STACS 2019), Berlin, Germany, 2019.
  52. Article
    D1
    “Hadwiger’s Conjecture for Squares of 2-Trees,” European Journal of Combinatorics, vol. 76, 2019.
  53. Conference paper
    D1
    “A General Framework for Handling Commitment in Online Throughput Maximization,” in Integer Programming and Combinatorial Optimization (IPCO 2019), Ann Arbor, MI, USA, 2019.
  54. Article
    D1
    “Secretary Markets with Local Information,” Distributed Computing, vol. 32, no. 5, 2019.
  55. Conference paper
    D1
    “Tracing Equilibrium in Dynamic Markets via Distributed Adaptation,” in AAMAS ’19, 18th International Conference on Autonomous Agents and Multiagent Systems, Montreal, Canada, 2019.
  56. Article
    D1
    “The Geometry of Rank Decompositions of Matrix Multiplication I: 2x2 Matrices,” Experimental Mathematics, vol. 28, no. 3, 2019.
  57. Article
    D1
    “Polynomial-Sized Topological Approximations Using the Permutahedron,” Discrete & Computational Geometry, vol. 61, no. 1, 2019.
  58. Article
    D1
    “Delaunay Simplices in Diagonally Distorted Lattices,” Computational Geometry: Theory and Applications, vol. 81, 2019.
  59. Conference paper
    D1
    “Improved Topological Approximations by Digitization,” in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019), San Diego, CA, USA, 2019.
  60. Article
    D1
    “Designing Networks with Good Equilibria under Uncertainty,” SIAM Journal on Computing, vol. 48, no. 4, 2019.
  61. Article
    D1
    “Recent Developments in Prophet Inequalities,” ACM SIGecom Exchanges, vol. 17, no. 1, 2019.
  62. Book
    D1
    Juristische Netzwerkforschung : Modellierung, Quantifizierung und Visualisierung relationaler Daten im Recht. Tübingen: Mohr Siebeck, 2019.
  63. Conference paper
    D1
    “Distributed Community Detection via Metastability of the 2-Choices Dynamics,” in Thirty-Third AAAI Conference on Artificial Intelligence, Honolulu, HI, USA, 2019.
  64. Article
    D1
    “Altitude Terrain Guarding and Guarding Uni-monotone Polygons,” Computational Geometry: Theory and Applications, vol. 84, 2019.
  65. Conference paper
    D1
    “On One-Round Discrete Voronoi Games,” in 30th International Symposium on Algorithms and Computation (ISAAC 2019), Shanghai, China, 2019.
  66. Conference paper
    D1
    “Counting Answers to Existential Questions,” in 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), Patras, Greece, 2019.
  67. Conference paper
    D1
    “Distribution-Independent PAC Learning of Halfspaces with Massart Noise,” in Advances in Neural Information Processing Systems 32 (NeurIPS 2019), Vancouver, Canada, 2019.
  68. Paper
    D1
    “On Geometric Complexity Theory: Multiplicity Obstructions are Stronger than Occurrence Obstructions,” 2019. [Online]. Available: http://arxiv.org/abs/1901.04576.
  69. Conference paper
    D1
    “Counting Induced Subgraphs: An Algebraic Approach to #W[1]-hardness,” in 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019), Aachen, Germany, 2019.
  70. Article
    D1
    “Tight Conditional Lower Bounds for Longest Common Increasing Subsequence,” Algorithmica, vol. 81, no. 10, 2019.
  71. Paper
    D1
    “The Arboricity Captures the Complexity of Sampling Edges,” 2019. [Online]. Available: http://arxiv.org/abs/1902.08086.
  72. Paper
    D1
    “Convergence of the Non-Uniform Directed Physarum Model,” 2019. [Online]. Available: http://arxiv.org/abs/1906.07781.
  73. Article
    D1
    “Noisy Rumor Spreading and Plurality Consensus,” Distributed Computing, vol. 32, no. 4, 2019.
  74. Conference paper
    D1
    “PATHFINDER: Storage and Indexing of Massive Trajectory Sets,” in SSTD ’19, 16th International Symposium on Spatial and Temporal Databases, Vienna, Austria, 2019.
  75. Conference paper
    D1
    “Optimal Sorting with Persistent Comparison Errors,” in 27th Annual European Symposium on Algorithms (ESA 2019), Munich/Garching, Germany, 2019.
  76. Conference paper
    D1
    “Dual-Mode Greedy Algorithms Can Save Energy,” in 30th International Symposium on Algorithms and Computation (ISAAC 2019), Shanghai, China, 2019.
  77. Article
    D1
    “A Stable Marriage Requires Communication,” Games and Economic Behavior, vol. 118, 2019.
  78. Conference paper
    D1
    “O(log 2 k/ log log k)-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial-Time Algorithm,” in STOC ’19, 51st Annual ACM Symposium on the Theory of Computing, Phoenix, AZ, USA, 2019.
  79. Article
    D1
    “Faster Approximation Schemes for the Two-dimensional Knapsack Problem,” ACM Transactions on Algorithms, vol. 15, no. 4, 2019.
  80. Conference paper
    D5D1
    “Bridging Quantities in Tables and Text,” in ICDE 2019, 35th IEEE International Conference on Data Engineering, Macau, China, 2019.
  81. Article
    D1
    “On the Complexity of Hazard-free Circuits,” Journal of the ACM, vol. 66, no. 4, 2019.
  82. Thesis
    D1IMPR-CS
    “On Some Covering, Partition and Connectivity Problems in Graphs,” Universität des Saarlandes, Saarbrücken, 2019.
  83. Conference paper
    D1
    “On the Complexity of Symmetric Polynomials,” in 10th Innovations in Theoretical Computer Science (ITCS 2019), San Diego, CA, USA, 2019.
  84. Conference paper
    D1
    “Dynamic Sparsification for Quadratic Assignment Problems,” in Mathematical Optimization Theory and Operations Research (MOTOR 2019), Ekaterinburg, Russia, 2019.
  85. Paper
    D1
    “Convergence of the Non-Uniform Physarum Dynamics,” 2019. [Online]. Available: http://arxiv.org/abs/1901.07231.
  86. Article
    D1
    “Self-Stabilizing Byzantine Clock Synchronization with Optimal Precision,” Theory of Computing Systems, vol. 63, no. 2, 2019.
  87. Conference paper
    D1
    “A Fresh Look at the Design of Low Jitter Hard Limiters,” in Joint Conference of the European Frequency and Time Forum and IEEE International Frequency Control Symposium (EFTF/IFC 2019), Orlando, FL, USA, 2019.
  88. Conference paper
    D1
    “A Physical Sine-to-Square Converter Noise Model,” in IEEE International Frequency Control Symposium (IFCS 2018), Olympic Valley, CA, USA, 2019.
  89. Conference paper
    D1
    “How Does Object Fatness Impact the Complexity of Packing in d Dimensions?,” in 30th International Symposium on Algorithms and Computation (ISAAC 2019), Shanghai, China, 2019.
  90. Article
    D1
    “Subquadratic Algorithms for Succinct Stable Matching,” Algorithmica, vol. 81, no. 7, 2019.
  91. Conference paper
    D1
    “Parallel Balanced Allocations: The Heavily Loaded Case,” in SPAA’19, 31st ACM Symposium on Parallelism in Algorithms and Architectures, Phoenix, AZ, USA, 2019.
  92. Article
    D1
    “Near-Optimal Self-stabilising Counting and Firing Squads,” Distributed Computing, vol. 32, no. 4, 2019.
  93. Article
    D1
    “Self-Stabilising Byzantine Clock Synchronisation is Almost as Easy as Consensus,” Journal of the ACM, vol. 66, no. 5, 2019.
  94. Paper
    D1
    “Parallel Balanced Allocations: The Heavily Loaded Case,” 2019. [Online]. Available: http://arxiv.org/abs/1904.07532.
  95. Article
    D1
    “Distributed Distance Computation and Routing with Small Messages,” Distributed Computing, vol. 32, no. 2, 2019.
  96. Conference paper
    D1
    “Resilient Dictionaries for Randomly Unreliable Memory,” in 27th Annual European Symposium on Algorithms (ESA 2019), Munich/Garching, Germany, 2019.
  97. Paper
    D1
    “With Great Speed Come Small Buffers: Space-Bandwidth Tradeoffs for Routing,” 2019. [Online]. Available: http://arxiv.org/abs/1902.08069.
  98. Conference paper
    D1
    “With Great Speed Come Small Buffers: Space-Bandwidth Tradeoffs for Routing,” in PODC ’19, ACM Symposium on Principles of Distributed Computing, Toronto, Canada, 2019.
  99. Article
    D1
    “Computing the Center Region and its Variants,” Theoretical Computer Science, vol. 789, 2019.
  100. Article
    D1
    “Assigning Weights to Minimize the Covering Radius in the Plane,” Computational Geometry: Theory and Applications, vol. 81, 2019.
  101. Article
    D1
    “A New Balanced Subdivision of a Simple Polygon for Time-Space Trade-Off Algorithms,” Algorithmica, vol. 81, no. 7, 2019.
  102. Conference paper
    D1
    “Optimal Algorithm for Geodesic Nearest-point Voronoi Diagrams in Simple Polygons,” in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019), San Diego, CA, USA, 2019.
  103. Conference paper
    D1
    “Space-Optimal Packet Routing on Trees,” in IEEE Conference on Computer Communications (IEEE INFOCOM 2019), Paris, France, 2019.
  104. Paper
    D1
    “A Little Charity Guarantees Almost Envy-Freeness,” 2019. [Online]. Available: http://arxiv.org/abs/1907.04596.
  105. Book
    D1
    Sequential and Parallel Algorithms and Data Structures. Cham: Springer, 2019.
  106. Thesis
    D1IMPR-CS
    “Plane and Simple,” Universität des Saarlandes, Saarbrücken, 2019.
  107. Article
    D1
    “Optimal Online Algorithms for the Portfolio Selection Problem, Bi-Directional Trading and -Search with Interrelated Prices,” RAIRO - Operations Research, vol. 53, no. 2, 2019.

2018

  1. Paper
    D1
    “Tighter Connections Between Formula-SAT and Shaving Logs,” 2018. [Online]. Available: http://arxiv.org/abs/1804.08978.
  2. Conference paper
    D1
    “More Consequences of Falsifying SETH and the Orthogonal Vectors Conjecture,” in STOC’18, 50th Annual ACM SIGACT Symposium on Theory of Computing, Los Angeles, CA, USA, 2018.
  3. Paper
    D1
    “SETH-Based Lower Bounds for Subset Sum and Bicriteria Path,” 2018. [Online]. Available: http://arxiv.org/abs/1704.04546.
  4. Paper
    D1
    “Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-And-Solve,” 2018. [Online]. Available: http://arxiv.org/abs/1803.00796.
  5. Conference paper
    D1
    “Tighter Connections Between Formula-SAT and Shaving Logs,” in 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), Prague, Czech Republic, 2018.
  6. Paper
    D1
    “Fast Fencing,” 2018. [Online]. Available: http://arxiv.org/abs/1804.00101.
  7. Conference paper
    D1
    “Fast Fencing,” in STOC’18, 50th Annual ACM SIGACT Symposium on Theory of Computing, Los Angeles, CA, USA, 2018.
  8. Conference paper
    D1
    “Approximating Airports and Railways,” in 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018), Caen, France, 2018.
  9. Article
    D1
    “Submodular Unsplittable Flow on Trees,” Mathematical Programming / B, vol. 172, no. 1–2, 2018.
  10. Conference paper
    D1
    “Walking Through Waypoints,” in LATIN 2018: Theoretical Informatics, Buenos Aires, Argentinia, 2018.
  11. Conference paper
    D1
    “Distributed Domination on Graph Classes of Bounded Expansion,” in SPAA’18, 30th ACM Symposium on Parallelism in Algorithms and Architectures, Vienna, Austria, 2018.
  12. Conference paper
    D1
    “Congestion-Free Rerouting of Flows on DAGs,” in 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), Prague, Czech Republic, 2018.
  13. Article
    D1
    “Charting the Algorithmic Complexity of Waypoint Routing,” ACM SIGCOMM Computer Communication Review, vol. 48, no. 1, 2018.
  14. Conference paper
    D1
    “A Collection of Lower Bounds for Online Matching on the Line,” in LATIN 2018: Theoretical Informatics, Buenos Aires, Argentinia, 2018.
  15. Conference paper
    D1
    “A Tight Lower Bound for Online Convex Optimization with Switching Costs,” in Approximation and Online Algorithms (WAOA 2017), Vienna, Austria, 2018.
  16. Conference paper
    D1
    “Near Optimal Mechanism for Energy Aware Scheduling,” in Algorithmic Game Theory (SAGT 2018), Beijing, China, 2018.
  17. Paper
    D1
    “A PTAS for Euclidean TSP with Hyperplane Neighborhoods,” 2018. [Online]. Available: http://arxiv.org/abs/1804.03953.
  18. Paper
    D1
    “Improved Bounds on Fourier Entropy and Min-entropy,” 2018. [Online]. Available: http://arxiv.org/abs/1809.09819.
  19. Paper
    D1
    “A Fast Implementation of Near Neighbors Queries for Fréchet Distance (GIS Cup),” 2018. [Online]. Available: http://arxiv.org/abs/1803.00806.
  20. Paper
    D1
    “The Geometry of Rank Decompositions of Matrix Multiplication II: 3 x 3 Matrices,” 2018. [Online]. Available: http://arxiv.org/abs/1801.00843.
  21. Paper
    D1
    “A PTAS for l p-Low Rank Approximation,” 2018. [Online]. Available: http://arxiv.org/abs/1807.06101.
  22. Paper
    D1
    “Finding a Bounded-Degree Expander Inside a Dense One,” 2018. [Online]. Available: http://arxiv.org/abs/1811.10316.
  23. Conference paper
    D1
    “Pooling or Sampling: Collective Dynamics for Electrical Flow Estimation,” in AAMAS’18, 17th International Conference on Autonomous Agents and MultiAgent Systems, Stockholm, Sweden, 2018.
  24. Conference paper
    D1
    “Average Whenever You Meet: Opportunistic Protocols for Community Detection,” in 26th Annual European Symposium on Algorithms (ESA 2018), Helsinki, Finland, 2018.
  25. Article
    D1
    “A Simple Near-Optimal Subdivision Algorithm for Complex Root Isolation based on the Pellet Test and Newton Iteration,” Journal of Symbolic Computation, vol. 86, 2018.
  26. Article
    D1
    “Sampling in Space Restricted Settings,” Algorithmica, vol. 80, no. 5, 2018.
  27. Conference paper
    D1
    “Generalized Matrix Completion and Algebraic Natural Proofs,” in STOC’18, 50th Annual ACM SIGACT Symposium on Theory of Computing, Los Angeles, CA, USA, 2018.
  28. Article
    D1
    “A Deterministic PTAS for Commutative Rank of Matrix Spaces,” Theory of Computing, vol. 14, 2018.
  29. Article
    D1
    “Generalized Matrix Completion and Algebraic Natural Proofs Contact Add Comment RSS-Feed,” Electronic Colloquium on Computational Complexity (ECCC): Report Series, vol. 18–064, 2018.
  30. Conference paper
    D1
    “Limits for Rumor Spreading in Stochastic Populations,” in 9th Innovations in Theoretical Computer Science (ITCS 2018), Cambridge, MA, USA, 2018.
  31. Article
    D1
    “Limits on Reliable Information Flows through Stochastic Populations,” PLoS Computational Biology, vol. 14, no. 6, 2018.
  32. Article
    D1
    “Delaunay Triangulation of Manifolds,” Foundations of Computational Mathematics, vol. 18, no. 2, 2018.
  33. Article
    D1
    “A Note on Hardness of Diameter Approximation,” Information Processing Letters, vol. 133, 2018.
  34. Paper
    D1
    “Fréchet Distance Under Translation: Conditional Hardness and an Algorithm via Offline Dynamic Grid Reachability,” 2018. [Online]. Available: http://arxiv.org/abs/1810.10982.
  35. Conference paper
    D1
    “Multivariate Fine-Grained Complexity of Longest Common Subsequence,” in Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), New Orleans, LA, USA, 2018.
  36. Paper
    D1
    “Clique-Based Lower Bounds for Parsing Tree-Adjoining Grammars,” 2018. [Online]. Available: http://arxiv.org/abs/1803.00804.
  37. Conference paper
    D1
    “Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (unless APSP can),” in Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), New Orleans, LA, USA, 2018.
  38. Article
    D1
    “On Algebraic Branching Programs of Small Width,” Journal of the ACM, vol. 65, no. 5, 2018.
  39. Paper
    D1
    “Multivariate Fine-Grained Complexity of Longest Common Subsequence,” 2018. [Online]. Available: http://arxiv.org/abs/1803.00938.
  40. Paper
    D1
    “Sketching, Streaming, and Fine-Grained Complexity of (Weighted) LCS,” 2018. [Online]. Available: http://arxiv.org/abs/1810.01238.
  41. Paper
    D1
    “Maximum Volume Subset Selection for Anchored Boxes,” 2018. [Online]. Available: http://arxiv.org/abs/1803.00849.
  42. Paper
    D1
    “Multivariate Analysis of Orthogonal Range Searching and Graph Distances Parameterized by Treewidth,” 2018. [Online]. Available: http://arxiv.org/abs/1805.07135.
  43. Article
    D1
    “De-anonymization of Heterogeneous Random Graphs in Quasilinear Time,” Algorithmica, vol. 80, no. 11, 2018.
  44. Conference paper
    D1
    “Sketching, Streaming, and Fine-Grained Complexity of (Weighted) LCS,” in 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018), Ahmedabad, India, 2018.
  45. Conference paper
    D1
    “Optimal Metastability-containing Sorting Networks,” in Proceedings of the 2018 Design, Automation & Test in Europe (DATE 2018), Dresden, Germany, 2018.
  46. Paper
    D1
    “Optimal Metastability-Containing Sorting Networks,” 2018. [Online]. Available: http://arxiv.org/abs/1801.07549.
  47. Paper
    D1
    “Small Hazard-free Transducers,” 2018. [Online]. Available: http://arxiv.org/abs/1811.12369.
  48. Paper
    D1
    “A Tight Extremal Bound on the Lovász Cactus Number in Planar Graphs,” 2018. [Online]. Available: http://arxiv.org/abs/1804.03485.
  49. Conference paper
    D1
    “Multi-Finger Binary Search Trees,” in 29th International Symposium on Algorithms and Computation (ISAAC 2018), Jiaoxi, Yilan, Taiwan, 2018.
  50. Paper
    D1
    “Survivable Network Design for Group Connectivity in Low-Treewidth Graphs,” 2018. [Online]. Available: http://arxiv.org/abs/1802.10403.
  51. Conference paper
    D1
    “Survivable Network Design for Group Connectivity in Low-Treewidth Graphs,” in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018), Princeton, NJ, USA, 2018.
  52. Conference paper
    D1
    “Spanning Tree Congestion and Computation of Generalized Györi-Lovász Partition,” in 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), Prague, Czech Republic, 2018.
  53. Conference paper
    D1
    “Algorithms and Bounds for Very Strong Rainbow Coloring,” in LATIN 2018: Theoretical Informatics, Buenos Aires, Argentinia, 2018.
  54. Conference paper
    D1
    “Stabbing Rectangles by Line Segments - How Decomposition Reduces the Shallow-Cell Complexity,” in 29th International Symposium on Algorithms and Computation (ISAAC 2018), Jiaoxi, Yilan, Taiwan, 2018.
  55. Conference paper
    D1
    “Amortized Analysis of Asynchronous Price Dynamics,” in 26th Annual European Symposium on Algorithms (ESA 2018), Helsinki, Finland, 2018.
  56. Conference paper
    D1
    “Multiplicative Weights Updates with Constant Step-Size in Graphical Constant-Sum Games,” in Advances in Neural Information Processing Systems 31 (NeurIPS 2018), Montréal, Canada, 2018.
  57. Paper
    D1
    “Parallel Stochastic Asynchronous Coordinate Descent: Tight Bounds on the Possible Parallelism,” 2018. [Online]. Available: http://arxiv.org/abs/1811.05087.
  58. Paper
    D1
    “Tracing Equilibrium in Dynamic Markets via Distributed Adaptation,” 2018. [Online]. Available: http://arxiv.org/abs/1804.08017.
  59. Conference paper
    D1
    “Steiner Point Removal - Distant Terminals Don’t (Really) Bother,” in Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), New Orleans, LA, USA, 2018.
  60. Conference paper
    D1
    “Dynamics of Distributed Updating in Fisher Markets,” in ACM EC’18, Nineteenth ACM Conference on Economics and Computation, Ithaca, NY, USA, 2018.
  61. Paper
    D1
    “(Near) Optimal Parallelism Bound for Fully Asynchronous Coordinate Descent with Linear Speedup,” 2018. [Online]. Available: http://arxiv.org/abs/1811.03254.
  62. Article
    D1
    “Polynomials and the Exponent of Matrix Multiplication,” Bulletin of the London Mathematical Society, vol. 50, no. 3, 2018.
  63. Conference paper
    D1
    “Coxeter Triangulations Have Good Quality,” in EuroCG 18 Extended Abstracts, Berlin, Germany, 2018.
  64. Conference paper
    D1
    “A Tight Analysis of the Parallel Undecided-State Dynamics with Two Colors,” in 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), Liverpool, UK, 2018.
  65. Paper
    D1
    “Consensus Needs Broadcast in Noiseless Models but can be Exponentially Easier in the Presence of Noise,” 2018. [Online]. Available: http://arxiv.org/abs/1807.05626.
  66. Article
    D1
    “On Testing Substitutability,” Information Processing Letters, vol. 138, 2018.
  67. Paper
    D1
    “On Testing Substitutability,” 2018. [Online]. Available: http://arxiv.org/abs/1805.07642.
  68. Article
    D1
    “On the Metastability of Quadratic Majority Dynamics on Clustered Graphs and its Biological Implications,” Bulletin of the EATCS, vol. 125, 2018.
  69. Conference paper
    D1
    “On the Emergent Behavior of the 2-Choices Dynamics,” in Proceedings of the 19th Italian Conference on Theoretical Computer Science (ICTCS 2018), Urbino, Italy, 2018.
  70. Paper
    D1
    “Phase Transition of the 2-Choices Dynamics on Core-Periphery Networks,” 2018. [Online]. Available: http://arxiv.org/abs/1804.07223.
  71. Article
    D1
    “Phase Transition of the 2-Choices Dynamics on Core-Periphery Networks,” Bulletin of the EATCS, vol. 125, 2018.
  72. Conference paper
    D1
    “Phase Transition of the 2-Choices Dynamics on Core-Periphery Networks,” in AAMAS’18, 17th International Conference on Autonomous Agents and MultiAgent Systems, Stockholm, Sweden, 2018.
  73. Paper
    D1
    “On Subexponential Running Times for Approximating Directed Steiner Tree and Related Problems,” 2018. [Online]. Available: http://arxiv.org/abs/1811.00710.
  74. Article
    D1
    “Fast Hamiltonicity Checking Via Bases of Perfect Matchings,” Journal of the ACM, vol. 65, no. 3, 2018.
  75. Conference paper
    D1
    “On the Complexity of Closest Pair via Polar-Pair of Point-Sets,” in 34th International Symposium on Computational Geometry (SoCG 2018), Budapest, Hungary, 2018.
  76. Conference paper
    D1
    “Testing Bounded Arboricity,” in Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), New Orleans, LA, USA, 2018.
  77. Conference paper
    D1
    “Online Generalized Caching with Varying Weights and Costs,” in SPAA’18, 30th ACM Symposium on Parallelism in Algorithms and Architectures, Vienna, Austria, 2018.
  78. Conference paper
    D1
    “Distributed Set Cover Approximation: Primal-Dual with Optimal Locality,” in 32nd International Symposium on Distributed Computing (DISC 2018), New Orleans, LA, USA, 2018.
  79. Conference paper
    D1
    “A Sublinear Tester for Outerplanarity (and Other Forbidden Minors) With One-Sided Error,” in 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), Prague, Czech Republic, 2018.
  80. Article
    D1
    “New Algorithms for Maximum Disjoint Paths Based on Tree-likeness,” Mathematical Programming / A, vol. 171, no. 1–2, 2018.
  81. Article
    D1
    “Parallel Metric Tree Embedding based on an Algebraic View on Moore-Bellman-Ford,” Journal of the ACM, vol. 65, no. 6, 2018.
  82. Article
    D1
    “Metastability-Containing Circuits,” IEEE Transactions on Computers, vol. 67, no. 8, 2018.
  83. Conference paper
    D1
    “Fast All-Digital Clock Frequency Adaptation Circuit for Voltage Droop Tolerance,” in 24th IEEE International Symposium on Asynchronous Circuits and Systems, Vienna, Austria, 2018.
  84. Conference paper
    D1
    “Approximating the Nash Social Welfare with Budget-Additive Valuations,” in Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), New Orleans, LA, USA, 2018.
  85. Article
    D1
    “Near-Optimal Distributed Maximum Flow,” SIAM Journal on Computing, vol. 47, no. 6, 2018.
  86. Conference paper
    D1
    “A(5/3+ε)-Approximation for Unsplittable Flow on a Path: Placing Small Tasks into Boxes,” in STOC’18, 50th Annual ACM SIGACT Symposium on Theory of Computing, Los Angeles, CA, USA, 2018.
  87. Paper
    D1
    “O(log 2 k/ log log k)-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial-Time Algorithm,” 2018. [Online]. Available: http://arxiv.org/abs/1811.03020.
  88. Article
    D1
    “Macroscopic Equivalence for Microscopic Motion in a Turbulence Driven Three-dimensional Self-assembly Reactor,” Journal of Applied Physics, vol. 123, no. 2, 2018.
  89. Conference paper
    D1
    “Rainbow Vertex Coloring Bipartite Graphs and Chordal Graphs,” in 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), Liverpool, UK, 2018.
  90. Thesis
    D1IMPR-CS
    “A Tale of Two Packing Problems: Improved Algorithms and Tighter Bounds for Online Bin Packing and the Geometric Knapsack Problem,” Universität des Saarlandes, Saarbrücken, 2018.
  91. Paper
    D1
    “A Classification of Spherical Schubert Varieties in the Grassmannian,” 2018. [Online]. Available: http://arxiv.org/abs/1809.08003.
  92. Article
    D1
    “Dynamics in Matching and Coalition Formation Games with Structural Constraints,” Artificial Intelligence, vol. 262, 2018.
  93. Article
    D1
    “How Unsplittable-flow-covering Helps Scheduling with Job-dependent Cost Functions,” Algorithmica, vol. 80, no. 4, 2018.
  94. Article
    D1
    “On the Relative Power of Reduction Notions in Arithmetic Circuit Complexity,” Information Processing Letters, vol. 130, 2018.
  95. Conference paper
    D1
    “On the Complexity of Hazard-free Circuits,” in STOC’18, 50th Annual ACM SIGACT Symposium on Theory of Computing, Los Angeles, CA, USA, 2018.
  96. Conference paper
    D1
    “On the Parameterized Complexity of Approximating Dominating Set,” in STOC’18, 50th Annual ACM SIGACT Symposium on Theory of Computing, Los Angeles, CA, USA, 2018.
  97. Conference paper
    D1
    “Price of Anarchy for Mechanisms with Risk-Averse Agents,” in 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), Prague, Czech Republic, 2018.
  98. Thesis
    D1IMPR-CS
    “Algorithmic Results for Clustering and Refined Physarum Analysis,” Universität des Saarlandes, Saarbrücken, 2018.
  99. Article
    D1
    “Corrigendum to ‘Faster algorithms for computing Hong’s bound on absolute positiveness’ [J. Symb. Comput. 45 (2010) 677–683],” Journal of Symbolic Computation, vol. 87, 2018.
  100. Paper
    D1
    “Optimal Gradient Clock Synchronization in Dynamic Networks (Version 3),” 2018. [Online]. Available: http://arxiv.org/abs/1005.2894.
  101. Conference paper
    D1
    “On Nondeterministic Derandomization of Freivalds’ Algorithm: Consequences, Avenues and Algorithmic Progress,” in 26th Annual European Symposium on Algorithms (ESA 2018), Helsinki, Finland, 2018.
  102. Paper
    D1
    “On Nondeterministic Derandomization of Freivalds’ Algorithm: Consequences, Avenues and Algorithmic Progress,” 2018. [Online]. Available: http://arxiv.org/abs/1806.09189.
  103. Article
    D1
    “Semidefinite and Linear Programming Integrality Gaps for Scheduling Identical Machines,” Mathematical Programming / B, vol. 172, no. 1–2, 2018.
  104. Conference paper
    D2D1
    “Partial Optimality and Fast Lower Bounds for Weighted Correlation Clustering,” in Proceedings of the 35th International Conference on Machine Learning (ICML 2018), Stockholm, Sweden, 2018.
  105. Conference paper
    D1
    “A Centralized Local Algorithm for the Sparse Spanning Graph Problem,” in 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), Prague, Czech Republic, 2018.
  106. Article
    D1
    “Simple Proof of Optimal Epsilon Nets,” Combinatorica, vol. 38, no. 5, 2018.
  107. Article
    D1
    “On the Computational Power of Simple Dynamics,” Bulletin of the EATCS, vol. 124, 2018.
  108. Conference paper
    D1
    “Polygon Queries for Convex Hulls of Points,” in Computing and Combinatorics (COCOON 2018), QingDao, China, 2018.
  109. Conference paper
    D1
    “Approximate Range Queries for Clustering,” in 34th International Symposium on Computational Geometry (SoCG 2018), Budapest, Hungary, 2018.
  110. Conference paper
    D1
    “Point Location in Dynamic Planar Subdivisions,” in 34th International Symposium on Computational Geometry (SoCG 2018), Budapest, Hungary, 2018.
  111. Conference paper
    D1
    “Point Location in Incremental Planar Subdivisions,” in 29th International Symposium on Algorithms and Computation (ISAAC 2018), Jiaoxi, Yilan, Taiwan, 2018.
  112. Conference paper
    D1
    “Minimizing Distance-to-Sight in Polygonal Domains,” in 29th International Symposium on Algorithms and Computation (ISAAC 2018), Jiaoxi, Yilan, Taiwan, 2018.
  113. Conference paper
    D1
    “The Itinerant List Update Problem,” in Approximation and Online Algorithms (WAOA 2018), Helsiniki, Finland, 2018.
  114. Book chapter / section
    D1
    “Combinatorial Optimization for UI Design,” in Computational Interaction, Oxford, UK: Oxford University Press, 2018.
  115. Article
    D1
    “Algebraic Independence over Positive Characteristic: New Criterion and Applications to Locally Low Algebraic Rank Circuits,” Computational Complexity, vol. 27, no. 4, 2018.
  116. Article
    D1
    “Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs,” ACM Transactions on Algorithms, vol. 14, no. 4, 2018.
  117. Paper
    D1
    “On Fair Division of Indivisible Items,” 2018. [Online]. Available: http://arxiv.org/abs/1805.06232.
  118. Conference paper
    D1
    “On Fair Division for Indivisible Items,” in 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018), Ahmedabad, India, 2018.
  119. Paper
    D1
    “Combinatorial Algorithms for General Linear Arrow-Debreu Markets,” 2018. [Online]. Available: http://arxiv.org/abs/1810.01237.
  120. Conference paper
    D1
    “Combinatorial Algorithms for General Linear Arrow-Debreu Markets,” in 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018), Ahmedabad, India, 2018.
  121. Article
    D1
    “Computing 2-Walks in Polynomial Time,” ACM Transactions on Algorithms, vol. 14, no. 2, 2018.
  122. Conference paper
    D1
    “Computing Tutte Paths,” in 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), Prague, Czech Republic, 2018.
  123. Article
    D1
    “Independent Set of Convex Polygons: From nϵ to 1+ϵ via Shrinking,” Algorithmica, vol. 80, no. 3, 2018.

2017

  1. Conference paper
    D1
    “Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-And-Solve,” in 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2017), Berkeley, CA, USA, 2017.
  2. Conference paper
    D1
    “Fully Dynamic All-Pairs Shortest Paths with Worst-Case Update-Time Revisited,” in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), Barcelona, Spain, 2017.
  3. Article
    D1
    “Reordering Buffer Management with Advice,” Journal of Scheduling, vol. 20, no. 5, 2017.
  4. Article
    D1
    “Sign Rank versus Vapnik-Chervonenkis Dimension,” Sbornik: Mathematics, vol. 208, no. 12, 2017.
  5. Article
    D1RG1
    “Verification of Linear Hybrid Systems with Large Discrete State Spaces Using Counterexample-guided Abstraction Refinement,” Science of Computer Programming, vol. 148, 2017.
  6. Article
    D1
    “Minimizing Maximum (Weighted) Flow-Time on Related and Unrelated Machines,” Algorithmica, vol. 77, no. 2, 2017.
  7. Conference paper
    D1
    “A QPTAS for the General Scheduling Problem with Identical Release Dates,” in 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), Warsaw, Poland, 2017.
  8. Article
    D1
    “Efficient Computation of Optimal Energy and Fractional Weighted Flow Trade-Off Schedules,” Algorithmica, vol. 79, no. 2, 2017.
  9. Article
    D1
    “Continuous Speed Scaling with Variability: A simple and Direct Approach,” Theoretical Computer Science, vol. 678, 2017.
  10. Article
    D1
    “Truthful Mechanism Design via Correlated Tree Rounding,” Mathematical Programming / A, vol. 163, no. 1–2, 2017.
  11. Conference paper
    D1
    “A Fast Implementation of Near Neighbors Queries for Fréchet Distance (GIS Cup),” in 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (GIS 2017), Redondo Beach, CA, USA, 2017.
  12. Article
    D1
    “Simple Dynamics for Plurality Consensus,” Distributed Computing, vol. 30, no. 4, 2017.
  13. Conference paper
    D1
    “Find Your Place: Simple Distributed Algorithms for Community Detection,” in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), Barcelona, Spain, 2017.
  14. Paper
    D1
    “Counting Solutions of a Polynomial System Locally and Exactly,” 2017. [Online]. Available: http://arxiv.org/abs/1712.05487.
  15. Conference paper
    D1
    “Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models,” in 31st International Symposium on Distributed Computing (DISC 2017), Vienna, Austria, 2017.
  16. Thesis
    D1IMPR-CS
    “On Flows, Paths, Roots, and Zeros,” Universität des Saarlandes, Saarbrücken, 2017.
  17. Paper
    D1
    “Two Results on Slime Mold Computations,” 2017. [Online]. Available: http://arxiv.org/abs/1707.06631.
  18. Conference paper
    D1
    “Earning Limits in Fisher Markets with Spending-Constraint Utilities,” in Algorithmic Game Theory (SAGT 2017), L’Aquila, Italy, 2017.
  19. Conference paper
    D1
    “Optimization of Bootstrapping in Circuits,” in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), Barcelona, Spain, 2017.
  20. Conference paper
    D1
    “Ignore or Comply?: On Breaking Symmetry in Consensus,” in PODC’17, ACM Symposium on Principles of Distributed Computing, Washington, DC, USA, 2017.
  21. Conference paper
    D1
    “Greedy Strikes Again: A Deterministic PTAS for Commutative Rank of Matrix Spaces,” in 32nd Computational Complexity Conference (CCC 2017), Riga, Latvia, 2017.
  22. Conference paper
    D1
    “Minimizing Message Size in Stochastic Communication Patterns: Fast Self-Stabilizing Protocols with 3 bits,” in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), Barcelona, Spain, 2017.
  23. Conference paper
    D1
    “Software Defined Radio Platform for Time and Frequency Metrology,” in Joint Conference of the European Frequency and Time Forum and IEEE International Frequency Control Symposium (EFTF/IFC 2017), Besançon, France, 2017.
  24. Conference paper
    D1
    “Damped Sine Based Time Interval Counter,” in Joint Conference of the European Frequency and Time Forum and IEEE International Frequency Control Symposium (EFTF/IFC 2017), Besançon, France, 2017.
  25. Paper
    D1
    “On Algebraic Branching Programs of Small Width,” 2017. [Online]. Available: http://arxiv.org/abs/1702.05328.
  26. Conference paper
    D1
    “On Algebraic Branching Programs of Small Width,” in 32nd Computational Complexity Conference (CCC 2017), Riga, Latvia, 2017.
  27. Conference paper
    D1
    “Clique-Based Lower Bounds for Parsing Tree-Adjoining Grammars,” in 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017), Warsaw, Poland, 2017.
  28. Conference paper
    D1
    “A Dichotomy for Regular Expression Membership Testing,” in 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2017), Berkeley, CA, USA, 2017.
  29. Conference paper
    D1
    “Greedy Routing and the Algorithmic Small-World Phenomenon,” in PODC’17, ACM Symposium on Principles of Distributed Computing, Washington, DC, USA, 2017.
  30. Paper
    D1
    “Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (unless APSP can),” 2017. [Online]. Available: http://arxiv.org/abs/1703.08940.
  31. Conference paper
    D1
    “Maximum Volume Subset Selection for Anchored Boxes,” in 33rd International Symposium on Computational Geometry (SoCG 2017), Brisbane, Australia, 2017.
  32. Conference paper
    D1
    “Improved Algorithms for Computing the Cycle of Minimum Cost-to-Time Ratio in Directed Graphs,” in 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), Warsaw, Poland, 2017.
  33. Paper
    D1
    “A Note on Hardness of Diameter Approximation,” 2017. [Online]. Available: http://arxiv.org/abs/1705.02127.
  34. Article
    D1
    “On Algebraic Branching Programs of Small Width,” Electronic Colloquium on Computational Complexity (ECCC) : Report Series, vol. 34 (Revision 1), 2017.
  35. Conference paper
    D1
    “A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum,” in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), Barcelona, Spain, 2017.
  36. Article
    D1
    “Improved Approximation for Fréchet Distance on c-packed Curves Matching Conditional Lower Bounds,” International Journal of Computational Geometry and Applications, vol. 27, no. 1/2, 2017.
  37. Conference paper
    D1
    “Approximation Algorithms for l_0-Low Rank Approximation,” in Advances in Neural Information Processing Systems 30 (NIPS 2017), Long Beach, CA, USA, 2017.
  38. Article
    D1
    “Efficient Sampling Methods for Discrete Distributions,” Algorithmica, vol. 79, no. 2, 2017.
  39. Conference paper
    D1
    “Sampling Geometric Inhomogeneous Random Graphs in Linear Time,” in 25th Annual European Symposium on Algorithms (ESA 2017), Vienna, Austria, 2017.
  40. Paper
    D1
    “Improved Algorithms for Computing the Cycle of Minimum Cost-to-Time Ratio in Directed Graphs,” 2017. [Online]. Available: http://arxiv.org/abs/1704.08122.
  41. Conference paper
    D1
    “Near-Optimal Metastability-Containing Sorting Networks,” in Proceedings of the 2017 Design, Automation & Test in Europe (DATE 2017), Lausanne, Switzerland, 2017.
  42. Article
    D1
    “Permanent versus Determinant: Not via Saturations,” Proceedings of the American Mathematical Society, vol. 145, 2017.
  43. Article
    D1
    “Fundamental Invariants of Orbit Closures,” Journal of Algebra, vol. 477, 2017.
  44. Conference paper
    D1
    “Beyond Metric Embedding: Approximating Group Steiner Trees on Bounded Treewidth Graphs,” in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), Barcelona, Spain, 2017.
  45. Conference paper
    D1
    “Finding Triangles for Maximum Planar Subgraphs,” in WALCOM: Algorithms and Computation, Hsinchu, Taiwan, 2017.
  46. Conference paper
    D1
    “New Integrality Gap Results for the Firefighters Problem on Trees,” in Approximation and Online Algorithms (WAOA 2016), Aarhus, Denmark, 2017.
  47. Conference paper
    D1
    “On the Parameterized Complexity of Biclique Cover and Partition,” in 11th International Symposium on Parameterized and Exact Computation (IPEC 2016), Aarhus, Denmark, 2017.
  48. Conference paper
    D1
    “Improved Approximate Rips Filtrations with Shifted Integer Lattices,” in 25th Annual European Symposium on Algorithms (ESA 2017), Vienna, Austria, 2017.
  49. Thesis
    D1IMPR-CS
    “Approximation Algorithms for Vietoris-Rips and Ĉech Filtrations,” Universität des Saarlandes, Saarbrücken, 2017.
  50. Thesis
    D1IMPR-CS
    “Graph Models for Rational Social Interaction,” Universität des Saarlandes, Saarbrücken, 2017.
  51. Article
    D1
    “Polynomial Kernelization for Removing Induced Claws and Diamonds,” Theory of Computing Systems, vol. 60, no. 4, 2017.
  52. Article
    D1
    “Complexity of Metric Dimension on Planar Graphs,” Journal of Computer and System Sciences, vol. 83, no. 1, 2017.
  53. Thesis
    D1IMPR-CS
    “Preliminaries for Distributed Natural Computing Inspired by the Slime Mold Physarum Polycephalum,” Universität des Saarlandes, Saarbrücken, 2017.
  54. Article
    D1
    “Characterizing Networks Formed by P. Polycephalum,” Journal of Physics D: Applied Physics, vol. 50, no. 22, 2017.
  55. Article
    D1
    “Introducing the Slime Mold Graph Repository,” Journal of Physics D: Applied Physics, vol. 50, no. 26, 2017.
  56. Conference paper
    D1
    “Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Non-Stochastic Inputs,” in 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2017), Berkeley, CA, USA, 2017.
  57. Paper
    D1
    “Tight Conditional Lower Bounds for Longest Common Increasing Subsequence,” 2017. [Online]. Available: http://arxiv.org/abs/1709.10075.
  58. Conference paper
    D1
    “Tight Conditional Lower Bounds for Longest Common Increasing Subsequence,” in 12th International Symposium on Parameterized and Exact Computation (IPEC 2017), Vienna, Austria, 2017.
  59. Conference paper
    D1
    “Shallow Packings, Semialgebraic Set Systems, Macbeath Regions and Polynomial Partitioning,” in 33rd International Symposium on Computational Geometry (SoCG 2017), Brisbane, Australia, 2017.
  60. Conference paper
    D1
    “Best-Response Dynamics in Combinatorial Auctions with Item Bidding,” in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), Barcelona, Spain, 2017.
  61. Article
    D1
    “Algorithms for Art Gallery Illumination,” Journal of Global Optimization, vol. 68, no. 1, 2017.
  62. Paper
    D1
    “Faster and Simpler Distributed Algorithms for Testing and Correcting Graph Properties in the CONGEST-Model,” 2017. [Online]. Available: http://arxiv.org/abs/1705.04898.
  63. Article
    D1
    “Online Packet-Routing in Grids with Bounded Buffers,” Algorithmica, vol. 78, no. 3, 2017.
  64. Conference paper
    D1
    “Three Notes on Distributed Property Testing,” in 31st International Symposium on Distributed Computing (DISC 2017), Vienna, Austria, 2017.
  65. Conference paper
    D1
    “Sublinear Random Access Generators for Preferential Attachment Graphs,” in 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), Warsaw, Poland, 2017.
  66. Thesis
    D1IMPR-CS
    “Metastability-Containing Circuits, Parallel Distance Problems, and Terrain Guarding,” Unversität des Saarlandes, Saarbrücken, 2017.
  67. Conference paper
    D1
    “Metastability-Aware Memory-Efficient Time-to-Digital Converters,” in 23rd IEEE International Symposium on Asynchronous Circuits and Systems (ASYNC 2017), San Diego, CA, USA, 2017.
  68. Conference paper
    D1
    “Approximating Geometric Knapsack via L-Packings,” in 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2017), Berkeley, CA, USA, 2017.
  69. Paper
    D1
    “Approximating the Nash Social Welfare with Budget-Additive Valuations,” 2017. [Online]. Available: http://arxiv.org/abs/1707.04428.
  70. Article
    D1
    “Geometric Complexity Theory and Matrix Powering,” Differential Geometry and its Applications, vol. 55, 2017.
  71. Conference paper
    D1
    “Distance Sensitive Bloom Filters Without False Negatives,” in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), Barcelona, Spain, 2017.
  72. Article
    D1
    “Computing Teichmüller Maps Between Polygons,” Foundations of Computational Mathematics, vol. 17, no. 2, 2017.
  73. Conference paper
    D1
    “To Augment or Not to Augment: Solving Unsplittable Flow on a Path by Creating Slack,” in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), Barcelona, Spain, 2017.
  74. Conference paper
    D1
    “Faster Approximation Schemes for the Two-dimensional Knapsack Problem,” in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), Barcelona, Spain, 2017.
  75. Paper
    D1
    “Combinatorial Secretary Problems with Ordinal Information,” 2017. [Online]. Available: http://arxiv.org/abs/1702.01290.
  76. Conference paper
    D1
    “Combinatorial Secretary Problems with Ordinal Information,” in 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), Warsaw, Poland, 2017.
  77. Article
    D1
    “Locally Stable Marriage with Strict Preferences,” SIAM Journal on Discrete Mathematics, vol. 31, no. 1, 2017.
  78. Article
    D1
    “On the Complexity of the Permanent in Various Computational Models,” Journal of Pure and Applied Algebra, vol. 221, no. 12, 2017.
  79. Paper
    D1
    “Strassen’s 2x2 Matrix Multiplication Algorithm: A Conceptual Perspective,” 2017. [Online]. Available: http://arxiv.org/abs/1708.08083.
  80. Article
    D1
    “On Vanishing of Kronecker Coefficients,” Computational Complexity, vol. 26, no. 4, 2017.
  81. Article
    D1
    “Rectangular Kronecker Coefficients and Plethysms in Geometric Complexity Theory,” Advances in Mathematics, vol. 319, 2017.
  82. Paper
    D1
    “On the Complexity of Hazard-free Circuits,” 2017. [Online]. Available: http://arxiv.org/abs/1711.01904.
  83. Conference paper
    D1
    “Density Independent Algorithms for Sparsifying k-Step Random Walks,” in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017), Berkeley, CA, USA, 2017.
  84. Paper
    D1
    “Efficiently Computing Real Roots of Sparse Polynomials,” 2017. [Online]. Available: http://arxiv.org/abs/1704.06979.
  85. Conference paper
    D1
    “Efficiently Computing Real Roots of Sparse Polynomials,” in ISSAC’17, International Symposium on Symbolic and Algebraic Computation, Kaiserslautern, Germany, 2017.
  86. Paper
    D1
    “Density Independent Algorithms for Sparsifying k-Step Random Walks,” 2017. [Online]. Available: http://arxiv.org/abs/1702.06110.
  87. Conference paper
    D1
    “Fractional Brownian Motion and its Application in the Simulation of Noise in Atomic Clocks,” in Joint Conference of the European Frequency and Time Forum and IEEE International Frequency Control Symposium (EFTF/IFC 2017), Besançon, France, 2017.
  88. Conference paper
    D1
    “The Use of Fault-tolerant Clock Synchronization Algorithms for Time Scales,” in Joint Conference of the European Frequency and Time Forum and IEEE International Frequency Control Symposium (EFTF/IFC 2017), Besançon, France, 2017.
  89. Thesis
    D1IMPR-CS
    “Incentives in Dynamic Markets,” Universität des Saarlandes, Saarbrücken, 2017.
  90. Paper
    D1
    “Self-stabilising Byzantine Clock Synchronisation is Almost as Easy as Consensus,” 2017. [Online]. Available: http://arxiv.org/abs/1705.06173.
  91. Paper
    D1
    “Robust Routing Made Easy,” 2017. [Online]. Available: http://arxiv.org/abs/1705.04042.
  92. Article
    D1
    “Searching without Communicating: Tradeoffs between Performance and Selection Complexity,” Distributed Computing, vol. 30, no. 3, 2017.
  93. Article
    D1
    “Efficient Counting with Optimal Resilience,” SIAM Journal on Computing, vol. 46, no. 4, 2017.
  94. Conference paper
    D1
    “Brief Announcement: A Centralized Local Algorithm for the Sparse Spanning Graph Problem,” in 31st International Symposium on Distributed Computing (DISC 2017), Vienna, Austria, 2017.
  95. Paper
    D1
    “A Local Algorithm for the Sparse Spanning Graph Problem,” 2017. [Online]. Available: http://arxiv.org/abs/1703.05418.
  96. Conference paper
    D1
    “Self-Stabilising Byzantine Clock Synchronisation is Almost as Easy as Consensus,” in 31st International Symposium on Distributed Computing (DISC 2017), Vienna, Austria, 2017.
  97. Conference paper
    D1
    “Robust Routing Made Easy,” in Stabilization, Safety, and Security of Distributed Systems (SSS 2017), Boston, MA, USA, 2017.
  98. Article
    D1
    “Constructing Near Spanning Trees with Few Local Inspections,” Random Structures and Algorithms, vol. 50, 2017.
  99. Article
    D1
    “Certifying 3-Edge-Connectivity,” Algorithmica, vol. 77, no. 2, 2017.
  100. Paper
    D1
    “Engineering DFS-Based Graph Algorithms,” 2017. [Online]. Available: http://arxiv.org/abs/1703.10023.
  101. Article
    D1
    “Polynomial Kernels for Deletion to Classes of Acyclic Digraphs,” Discrete Optimization, vol. 25, 2017.
  102. Conference paper
    D1
    “Dynamic spanning forest with worst-case update time: adaptive, Las Vegas, and O(n1/2 - ε)-time,” in STOC ’17, 49th Annual ACM SIGACT Symposium on Theory of Computing, Montreal, Canada, 2017.
  103. Article
    D1
    “Computational Support for Functionality Selection in Interaction Design,” ACM Transactions on Computer-Human Interaction, vol. 24, no. 5, 2017.
  104. Article
    D1
    “Shortcutting Directed and Undirected Networks with a Degree Constraint,” Discrete Applied Mathematics, vol. 220, 2017.
  105. Conference paper
    D1
    “Metastability Tolerant Computing,” in 23rd IEEE International Symposium on Asynchronous Circuits and Systems (ASYNC 2017), San Diego, CA, USA, 2017.
  106. Conference paper
    D1
    “From DQBF to QBF by Dependency Elimination,” in Theory and Applications of Satisfiability Testing -- SAT 2017, Melbourne, Australia, 2017.
  107. Conference paper
    D1D5
    “Efficiency-aware Answering of Compositional Questions using Answer Type Prediction,” in The 8th International Joint Conference on Natural Language Processing (IJCNLP 2017), Taipei, Taiwan, 2017.

2016

  1. Paper
    D1
    “Fully Dynamic All-pairs Shortest Paths with Worst-case Update-time revisited,” 2016. [Online]. Available: http://arxiv.org/abs/1607.05132.
  2. Conference paper
    D1
    “On Fully Dynamic Graph Sparsifiers,” in FOCS 2016, New Brunswick, NJ, USA, 2016.
  3. Paper
    D1
    “On Fully Dynamic Graph Sparsifiers,” 2016. [Online]. Available: http://arxiv.org/abs/1604.02094.
  4. Article
    D1
    “Concurrent Imitation Dynamics in Congestion Games,” Distributed Computing, vol. 29, no. 2, 2016.
  5. Conference paper
    D1
    “Submodular Unsplittable Flow on Trees,” in Integer Programming and Combinatorial Optimization (IPCO 2016), Liège, Belgium, 2016.
  6. Conference paper
    D1
    “Airports and Railways: Facility Location Meets Network Design,” in 33rd International Symposium on Theoretical Aspects of Computer Science (STACS 2016), Orléans, France, 2016.
  7. Conference paper
    D1
    “Sign Rank Versus VC Dimension,” in 29th Annual Conference on Learning Theory (COLT 2016), New York, NY, USA, 2016.
  8. Report
    D1RG1IMPR-CS
    “Verification of Linear Hybrid Systems with Large Discrete State Spaces: Exploring the Design Space for Optimization,” SFB/TR 14 AVACS, ATR103, 2016.
  9. Conference paper
    D1
    “Chasing Convex Bodies and Functions,” in LATIN 2016: Theoretical Informatics, Ensenada, Mexico, 2016.
  10. Paper
    D1
    “On Induced Colourful Paths in Triangle-free Graphs,” 2016. [Online]. Available: http://arxiv.org/abs/1604.06070.
  11. Paper
    D1
    “Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models,” 2016. [Online]. Available: http://arxiv.org/abs/1607.05127.
  12. Conference paper
    D1
    “Complexity Analysis of Root Clustering for a Complex Polynomial,” in ISSAC 2016, 41st International Symposium on Symbolic and Algebraic Computation, Waterloo, Canada, 2016.
  13. Paper
    D1
    “A Simple Near-Optimal Subdivision Algorithm for Complex Root Isolation based on the Pellet Test and Newton Iteration,” 2016. [Online]. Available: http://arxiv.org/abs/1509.06231.
  14. Paper
    D1
    “An Integer Interior Point Method for Min-Cost Flow Using Arc Contractions and Deletions,” 2016. [Online]. Available: http://arxiv.org/abs/1612.04689.
  15. Conference paper
    D1
    “A Novel Dual Ascent Algorithm for Solving the Min-Cost Flow Problem,” in Proceedings of the Eighteenth Workshop on Algorithm Engineering and Experiments (ALENEX 2016), Arlington, VA, USA, 2016.
  16. Conference paper
    D1
    “Learning Market Parameters Using Aggregate Demand Queries,” in Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, Phoenix, AZ, USA, 2016.
  17. Conference paper
    D1
    “Ascending-Price Algorithms for Unknown Markets,” in EC’16, ACM Conference on Economics and Computation, Maastricht, The Netherlands, 2016.
  18. Conference paper
    D1
    “Computing Equilibria in Markets with Budget-Additive Utilities,” in 24th Annual European Symposium on Algorithms (ESA 2016), Aarhus, Denmark, 2016.
  19. Paper
    D1
    “Computing Equilibria in Markets with Budget-Additive Utilities,” 2016. [Online]. Available: http://arxiv.org/abs/1603.07210.
  20. Article
    D1
    “(1,j)-set Problem in Graphs,” Discrete Mathematics, vol. 339, no. 10, 2016.
  21. Article
    D1
    “Greedy Strikes Again: A Deterministic PTAS for Commutative Rank of Matrix Spaces,” Electronic Colloquium on Computational Complexity (ECCC): Report Series, vol. 145, 2016.
  22. Paper
    D1
    “Fully Dynamic Spanners with Worst-Case Update Time,” 2016. [Online]. Available: http://arxiv.org/abs/1606.07864.
  23. Conference paper
    D1
    “Fully Dynamic Spanners with Worst-Case Update Time,” in 24th Annual European Symposium on Algorithms (ESA 2016), Aarhus, Denmark, 2016.
  24. Article
    D1
    “Solving Bivariate Systems Using Rational Univariate Representations,” Journal of Complexity, vol. 37, 2016.
  25. Conference paper
    D1
    “On the Complexity of Solving Zero-Dimensional Polynomial Systems via Projection,” in ISSAC 2016, 41st International Symposium on Symbolic and Algebraic Computation, Waterloo, Canada, 2016.
  26. Paper
    D1
    “On the Complexity of Solving Zero-Dimensional Polynomial Systems via Projection,” 2016. [Online]. Available: http://arxiv.org/abs/1604.08944.
  27. Conference paper
    D1
    “Cliques in Regular Graphs and the Core-Periphery Problem in Social Networks,” in Combinatorial Optimization and Applications (COCOA 2016), Hong Kong, China, 2016.
  28. Conference paper
    D1
    “Truly Sub-cubic Algorithms for Language Edit Distance and RNA-Folding via Fast Bounded-Difference Min-Plus Product,” in FOCS 2016, New Brunswick, NJ, USA, 2016.
  29. Article
    D1
    “Parameterized Complexity Dichotomy for Steiner Multicut,” Journal of Computer and System Sciences, 2016.
  30. Paper
    D1
    “A Dichotomy for Regular Expression Membership Testing,” 2016. [Online]. Available: http://arxiv.org/abs/1611.00918.
  31. Paper
    D1
    “Geometric Inhomogeneous Random Graphs,” 2016. [Online]. Available: http://arxiv.org/abs/1511.00576.
  32. Conference paper
    D1
    “Hitting Set for Hypergraphs of Low VC-dimension,” in 24th Annual European Symposium on Algorithms (ESA 2016), Aarhus, Denmark, 2016.
  33. Paper
    D1
    “Greedy Routing and the Algorithmic Small-World Phenomenom,” 2016. [Online]. Available: http://arxiv.org/abs/1612.05539.
  34. Article
    D1
    “Balls into Bins via Local Search: Cover Time and Maximum Load,” Random Structures and Algorithms, vol. 48, no. 4, 2016.
  35. Article
    D1
    “Approximability of the Discrete Fréchet Distance,” Journal on Computational Geometry, vol. 7, no. 2, 2016.
  36. Paper
    D1
    “Average Distance in a General Class of Scale-Free Networks with Underlying Geometry,” 2016. [Online]. Available: http://arxiv.org/abs/1602.05712.
  37. Article
    D1
    “Topological Separations in Inductive Inference,” Theoretical Computer Science, vol. 260, 2016.
  38. Article
    D1
    “Algebraic Methods in the Congested Clique,” Distributed Computing, vol. 32, 2016.
  39. Article
    D1
    “A Note on Fractional Coloring and the Integrality gap of LP for Maximum Weight Independent Set,” Electronic Notes in Discrete Mathematics (Proc. CTW 2016), vol. 55, 2016.
  40. Paper
    D1
    “The Landscape of Bounds for Binary Search Trees,” 2016. [Online]. Available: http://arxiv.org/abs/1603.04892.
  41. Conference paper
    D1
    “Hadwiger’s Conjecture and Squares of Chordal Graphs,” in Computing and Combinatorics (COCOON 2016), Ho Chi Minh City, Vietnam, 2016.
  42. Conference paper
    D1
    “Fast, Robust, Quantizable Approximate Consensus,” in 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), Rome, Italy, 2016.
  43. Paper
    D1
    “A Unified Approach to Analyzing Asynchronous Coordinate Descent and Tatonnement,” 2016. [Online]. Available: http://arxiv.org/abs/1612.09171.
  44. Paper
    D1
    “The Geometry of Rank Decompositions of Matrix Multiplication I: 2x2 Matrices,” 2016. [Online]. Available: http://arxiv.org/abs/1610.08364.
  45. Conference paper
    D1
    “Polynomial-Sized Topological Approximations Using the Permutahedron,” in 32nd International Symposium on Computational Geometry (SoCG 2016), Boston, MA, USA, 2016.
  46. Paper
    D1
    “Polynomial-Sized Topological Approximations Using The Permutahedron,” 2016. [Online]. Available: http://arxiv.org/abs/1601.02732.
  47. Article
    D1
    “Rumor Spreading in Random Evolving Graphs,” Random Structures and Algorithms, vol. 48, no. 2, 2016.
  48. Conference paper
    D1
    “Bipartite Digraphs Debates,” in 9th Multidisciplinary Workshop on Advances in Preference Handling (MPref 2015), Buenos Aires, Argentinia, 2016.
  49. Conference paper
    D1
    “Opposition Frameworks,” in Logics in Artificial Intelligence (JELIA 2016), Larnaca, Cyprus, 2016.
  50. Conference paper
    D1
    “Polynomial Kernelization for Removing Induced Claws and Diamonds,” in Graph-Theoretic Concepts in Computer Science (WG 2015), Garching, Germany, 2016.
  51. Article
    D1
    “Jamming-resistant Learning in Wireless Networks,” IEEE/ACM Transactions on Networking, vol. 24, no. 5, 2016.
  52. Thesis
    IMPR-CSD1
    “Market Equilibrium Computation for the Linear Arrow-Debreu Model,” Universität des Saarlandes, Saarbrücken, 2016.
  53. Article
    D1
    “Improved Balanced Flow Computation Using Parametric Flow,” Information Processing Letters, vol. 116, no. 9, 2016.
  54. Book chapter / section
    D1
    “Engineering Art Galleries,” in Algorithm Engineering, Berlin: Springer, 2016.
  55. Article
    D1
    “Playing Mastermind with Many Colors,” Journal of the ACM, vol. 63, no. 5, 2016.
  56. Article
    D1
    “Simple and Optimal Randomized Fault-tolerant Rumor Spreading,” Distributed Computing, vol. 29, no. 2, 2016.
  57. Article
    D1
    “Simple and Optimal Fault-tolerant Rumor Spreading,” Distributed Computing, vol. 29, no. 2, 2016.
  58. Conference paper
    D1
    “Improved Protocols and Hardness Results for the Two-Player Cryptogenography Problem,” in 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), Rome, Italy, 2016.
  59. Article
    D1
    “Synchronous Counting and Computational Algorithm Design,” Journal of Computer and System Sciences, vol. 82, no. 2, 2016.
  60. Article
    D1
    “HEX: Scaling Honeycombs is Easier than Scaling Clock Trees,” Journal of Computer and System Sciences, vol. 82, no. 5, 2016.
  61. Conference paper
    D1
    “An Improved Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market,” in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016), Arlington, VA, USA, 2016.
  62. Conference paper
    D1
    “On Subgraphs of Bounded Degeneracy in Hypergraphs,” in Graph-Theoretic Concepts in Computer Science (WG 2016), Istanbul, Turkey, 2016.
  63. Article
    D1
    “Improved Bounds on Induced Acyclic Subgraphs in Random Digraphs,” SIAM Journal on Discrete Mathematics, vol. 30, no. 3, 2016.
  64. Article
    D1
    “Two Proofs for Shallow Packings,” Discrete & Computational Geometry, vol. 56, no. 4, 2016.
  65. Paper
    D1
    “Posted Prices, Smoothness, and Combinatorial Prophet Inequalities,” 2016. [Online]. Available: http://arxiv.org/abs/1612.03161.
  66. Paper
    D1
    “Best-Response Dynamics in Combinatorial Auctions with Item Bidding,” 2016. [Online]. Available: http://arxiv.org/abs/1607.04149.
  67. Article
    D1
    “Towards More Practical Linear Programming-based Techniques for Algorithmic Mechanism Design,” Theory of Computing Systems, vol. 59, no. 4, 2016.
  68. Article
    D1
    “Dynamic Range Majority Data Structures,” Theoretical Computer Science, vol. 647, 2016.
  69. Article
    D1
    “Lower Bounds for Projections of Power Symmetric Polynomials,” Electronic Colloquium on Computational Complexity (ECCC): Report Series, vol. 153, 2016.
  70. Conference paper
    D1
    “A Constant Approximation Algorithm for Scheduling Packets on Line Networks,” in 24th Annual European Symposium on Algorithms (ESA 2016), Aarhus, Denmark, 2016.
  71. Conference paper
    D1
    “On-Line Path Computation and Function Placement in SDNs,” in Stabilization, Safety, and Security of Distributed Systems (SSS 2016), Lyon, France, 2016.
  72. Paper
    D1
    “Sublinear Random Access Generators for Preferential Attachment Graphs,” 2016. [Online]. Available: http://arxiv.org/abs/1602.06159.
  73. Article
    D1
    “The Firefighter Problem on Graph Classes,” Theoretical Computer Science, vol. 613, 2016.
  74. Article
    D1
    “The Multiple-orientability Thresholds for Random Hypergraphs,” Combinatorics, Probability and Computing, vol. 25, no. 6, 2016.
  75. Article
    D1
    “The Continuous 1.5D Terrain Guarding Problem: Discretization, Optimal Solutions, and PTAS,” Journal of Computational Geometry, vol. 7, no. 1, 2016.
  76. Conference paper
    D1
    “Parallel Metric Tree Embedding based on an Algebraic View on Moore-Bellman-Ford,” in SPAA’16, 28th ACM Symposium on Parallelism in Algorithms and Architectures, Pacific Grove, CA, USA, 2016.
  77. Paper
    D1
    “Metastability-Containing Circuits,” 2016. [Online]. Available: http://arxiv.org/abs/1606.06570.
  78. Article
    D1
    “Unfaithful Glitch Propagation in Existing Binary Circuit Models,” IEEE Transactions on Computers, vol. 65, no. 3, 2016.
  79. Conference paper
    D1
    “Raising The Bar For Vertex Cover: Fixed-parameter Tractability Above A Higher Guarantee,” in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016), Arlington, VA, USA, 2016.
  80. Paper
    D1
    “Geometric complexity theory and matrix powering,” 2016. [Online]. Available: http://arxiv.org/abs/1611.00827.
  81. Article
    D1
    “Induced Disjoint Paths in Circular-Arc Graphs in Linear Time,” Theoretical Computer Science, vol. 640, 2016.
  82. Conference paper
    D1
    “Non-local Probes Do Not Help with Many Graph Problems,” in Distributed Computing (DISC 2016), Paris, France, 2016.
  83. Article
    D1
    “Routing Games with Progressive Filling,” IEEE/ACM Transactions on Networking, vol. 24, no. 4, 2016.
  84. Conference paper
    D1
    “A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths,” in Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2016), Cambridge, MA, USA, 2016.
  85. Paper
    D1
    “Improved Lower Bounds for Online Hypercube Packing,” 2016. [Online]. Available: http://arxiv.org/abs/1607.01229.
  86. Conference paper
    D1
    “Beating the Harmonic Lower Bound for Online Bin Packing,” in 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), Rome, Italy, 2016.
  87. Conference paper
    D1
    “Smoothness for Simultaneous Composition of Mechanisms with Admission,” in Web and Internet Economics (WINE 2016), Montréal, Canada, 2016.
  88. Article
    D1
    “Truthfulness and Stochastic Dominance with Monetary Transfers,” ACM Transactions on Economics and Computation, vol. 4, no. 2, 2016.
  89. Article
    D1
    “Preface to Special Issue on Algorithmic Game Theory,” Theory of Computing Systems, vol. 59, no. 4, 2016.
  90. Article
    D1
    “Fair Matchings and Related Problems,” Algorithmica, vol. 74, no. 3, 2016.
  91. Conference paper
    D1
    “A Combinatorial Approximation Algorithm for Graph Balancing with Light Hyper Edges,” in 24th Annual European Symposium on Algorithms (ESA 2016), Aarhus, Denmark, 2016.
  92. Paper
    D1
    “On the Relative Power of Reduction Notions in Arithmetic Circuit Complexity,” 2016. [Online]. Available: http://arxiv.org/abs/1609.05942.
  93. Paper
    D1
    “On the Complexity of the Permanent in Various Computational Models,” 2016. [Online]. Available: http://arxiv.org/abs/1610.00159.
  94. Article
    D1
    “One-variable Word Equations in Linear Time,” Algorithmica, vol. 74, no. 1, 2016.
  95. Conference paper
    D1
    “A Novel SDP Relaxation for the Quadratic Assignment Problem Using Cut Pseudo Bases,” in Combinatorial Optimization (ISCO 2016), Vietri sul Mare, Italy, 2016.
  96. Conference paper
    D1
    “Parameterized Algorithms for Recognizing Monopolar and 2-Subcolorable Graphs,” in 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016), Reykjavik, Iceland, 2016.
  97. Conference paper
    D1
    “Geometry Helps to Compare Persistence Diagrams,” in Proceedings of the Eighteenth Workshop on Algorithm Engineering and Experiments (ALENEX 2016), Arlington, VA, USA, 2016.
  98. Paper
    D1
    “Geometry Helps to Compare Persistence Diagrams,” 2016. [Online]. Available: http://arxiv.org/abs/1606.03357.
  99. Conference paper
    D1
    “Persistent Homology and Nested Dissection,” in Proceedings of the Twenty-Seventh ACM-SIAM Annual Symposium on Discrete Algorithms (SODA 2016), Arlington, VA, USA, 2016.
  100. Paper
    D1
    “Think Eternally: Improved Algorithms for the Temp Secretary Problem and Extensions,” 2016. [Online]. Available: http://arxiv.org/abs/1606.06926.
  101. Conference paper
    D1
    “Think Eternally: Improved Algorithms for the Temp Secretary Problem and Extensions,” in 24th Annual European Symposium on Algorithms (ESA 2016), Aarhus, Denmark, 2016.
  102. Paper
    D1
    “Submodular Secretary Problems: Cardinality, Matching, and Linear Constraints,” 2016. [Online]. Available: http://arxiv.org/abs/1607.08805.
  103. Paper
    D1
    “Self-stabilizing Byzantine Clock Synchronization with Optimal Precision,” 2016. [Online]. Available: http://arxiv.org/abs/1609.09281.
  104. Conference paper
    D1
    “Self-stabilizing Byzantine Clock Synchronization with Optimal Precision,” in Stabilization, Safety, and Security of Distributed Systems (SSS 2016), Lyon, France, 2016.
  105. Conference paper
    D1
    “Fault-Tolerant Clock Synchronization with High Precision,” in ISVLSI 2016, Pittsburgh, PA, USA, 2016.
  106. Paper
    D1
    “Computing Real Roots of Real Polynomials ... and now For Real!,” 2016. [Online]. Available: http://arxiv.org/abs/1605.00410.
  107. Conference paper
    D1
    “Computing Real Roots of Real Polynomials ... and now For Real!,” in ISSAC 2016, 41st International Symposium on Symbolic and Algebraic Computation, Waterloo, Canada, 2016.
  108. Conference paper
    D1
    “A Note On Spectral Clustering,” in 24th Annual European Symposium on Algorithms (ESA 2016), Aarhus, Denmark, 2016.
  109. Article
    D1
    “Direct Sum Fails for Zero-Error Average Communication,” Algorithmica, vol. 76, no. 3, 2016.
  110. Article
    D1
    “Parameterized Complexity and Kernelizability of Max Ones and Exact Ones Problems,” ACM Transactions on Computation Theory, vol. 8, no. 1, 2016.
  111. Article
    D1
    “Point Line Cover: The Easy Kernel is Essentially Tight,” ACM Transactions on Algorithms, vol. 12, no. 3, 2016.
  112. Article
    D1
    “Small Depth Proof Systems,” ACM Transactions on Computation Theory, vol. 9, no. 1, 2016.
  113. Book chapter / section
    D1
    “Schnellere Approximationsalgorithmen zur Partiell-Dynamischen Berechnung Kürzester Wege,” in Ausgezeichnete Informatikdissertationen 2015, Bonn: GI, 2016.
  114. Thesis
    D1IMPR-CS
    “Tight(er) Bounds for Similarity Measures, Smoothed Approximation and Broadcasting,” Universität des Saarlandes, Saarbrücken, 2016.
  115. Conference paper
    D1
    “Semidefinite and Linear Programming Integrality Gaps for Scheduling Identical Machines,” in Integer Programming and Combinatorial Optimization (IPCO 2016), Liège, Belgium, 2016.
  116. Conference paper
    D1
    “Efficient Metastability-Containing Gray Code 2-Sort,” in 22nd IEEE International Symposium on Asynchronous Circuits and Systems, Porto Alegre, Brazil, 2016.
  117. Paper
    D1
    “Near-Optimal Self-Stabilising Counting and Firing Squads,” 2016. [Online]. Available: http://arxiv.org/abs/1608.00214.
  118. Conference paper
    D1
    “Near-Optimal Self-stabilising Counting and Firing Squads,” in Stabilization, Safety, and Security of Distributed Systems (SSS 2016), Lyon, France, 2016.
  119. Paper
    D1
    “CLEX: Yet Another Supercomputer Architecture?,” 2016. [Online]. Available: http://arxiv.org/abs/1607.00298.
  120. Conference paper
    D1
    “A Local Algorithm for Constructing Spanners in Minor-Free Graphs,” in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016), Paris, France, 2016.
  121. Paper
    D1
    “A Local Algorithm for Constructing Spanners in Minor-Free Graphs,” 2016. [Online]. Available: http://arxiv.org/abs/1604.07038.
  122. Conference paper
    D1
    “Independence and Efficient Domination on P6-free Graphs,” in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016), Arlington, VA, USA, 2016.
  123. Article
    D1
    “Building Above Read-Once Polynomials: Identity Testing and Hardness of Representation,” Algorithmica, vol. 76, no. 4, 2016.
  124. Article
    D1
    “The Power of Recourse for Online MST and TSP,” SIAM Journal on Computing, vol. 45, no. 3, 2016.
  125. Article
    D1
    “Algorithms and Programs: Erasmus Lecture 2014,” European Review, vol. 24, no. 1, 2016.
  126. Article
    D1
    “A Still Simpler Way of Introducing the Interior-Point Method for Linear Programming,” Computer Science Review, vol. 22, 2016.
  127. Article
    D1
    “Randomized Rumor Spreading in Poorly Connected Small-world Networks,” Random Structures and Algorithms, vol. 49, no. 1, 2016.
  128. Conference paper
    D1
    “Polynomial Kernels for Deletion to Classes of Acyclic Digraphs,” in 33rd International Symposium on Theoretical Aspects of Computer Science (STACS 2016), Orléans, France, 2016.
  129. Conference paper
    D1
    “Labeled Compression Schemes for Extremal Classes,” in Algorithmic Learning Theory (ALT 2016), Bari, Italy, 2016.
  130. Article
    D1
    “A Note on Average-case Sorting,” Order, vol. 33, no. 1, 2016.
  131. Conference paper
    D1D4
    “Shattered Sets and the Hilbert Function,” in 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), Kraków, Poland, 2016.
  132. Article
    D1
    “Sample Compression Schemes for VC Classes,” Journal of the ACM, vol. 63, no. 3, 2016.
  133. Conference paper
    D1
    “Fooling Pairs in Randomized Communication Complexity,” in Structural Information and Communication Complexity (SIROCCO 2016), Helsinki, Finland, 2016.
  134. Article
    D1
    “Succinct Posets,” Algorithmica, vol. 76, no. 2, 2016.
  135. Conference paper
    D1
    “On Approximating Strip Packing with a Better Ratio than 3/2,” in Proceedings of the Twenty-Seventh ACM-SIAM Annual Symposium on Discrete Algorithms (SODA 2016), Arlington, VA, USA, 2016.
  136. Conference paper
    D1
    “Trend Detection Based Regret Minimization for Bandit Problems,” in 3rd IEEE International Conference on Data Science and Advanced Analytics (DSAA 2016), Montréal, Canada, 2016.
  137. Article
    D1
    “Identification of Key Player Genes in Gene Regulatory Networks,” BMC Systems Biology, vol. 10, 2016.
  138. Paper
    D1
    “This House Proves that Debating is Harder than Soccer,” 2016. [Online]. Available: http://arxiv.org/abs/1605.03063.
  139. Conference paper
    D1
    “This House Proves That Debating is Harder Than Soccer,” in 8th International Conference on Fun with Algorithms, La Maddalena, Italy, 2016.
  140. Conference paper
    D1
    “Supervised Learning Through the Lens of Compression,” in Advances in Neural Information Processing Systems 29 (NIPS 2016), Barcelona, Spain, 2016.
  141. Thesis
    D1IMPR-CS
    “Algorithms for Classical and Modern Scheduling Problems,” Universität des Saarlandes, Saarbrücken, 2016.
  142. Conference paper
    D1D4
    “Algebraic Independence over Positive Characteristic: New Criterion and Applications to Locally Low Algebraic Rank Circuits,” in 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), Kraków, Poland, 2016.
  143. Thesis
    D1
    “ScheduleMe: personal assistant,” Universität des Saarlandes, Saarbrücken, 2016.
  144. Paper
    D1
    “Approximation and Parameterized Algorithms for Geometric Independent Set with Shrinking,” 2016. [Online]. Available: http://arxiv.org/abs/1611.06501.
  145. Paper
    D1
    “Homotopy Equivalence Between Voronoi Medusa and Delaunay Medusa,” 2016. [Online]. Available: http://arxiv.org/abs/1604.03302.
  146. Article
    D1
    “Computing Real Roots of Real Polynomials,” Journal of Symbolic Computation, vol. 73, 2016.
  147. Conference paper
    D1
    “Independent Set of Convex Polygons: From nϵ to 1+ϵ via Shrinking,” in LATIN 2016: Theoretical Informatics, Ensenada, Mexico, 2016.

2015

  1. Thesis
    D1IMPR-CS
    “Coordinating Selfish Players in Scheduling Games,” Universität des Saarlandes, Saarbrücken, 2015.
  2. Conference paper
    D1
    “On Guillotine Cutting Sequences,” in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015), Princeton, NJ, USA, 2015.
  3. Article
    D1
    “Coordinating Oligopolistic Players in Unrelated Machine Scheduling,” Theoretical Computer Science, vol. 570, 2015.
  4. Conference paper
    D1
    “How to Tame Rectangles: Solving Independent Set and Coloring of Rectangles via Shrinking,” in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015), Princeton, NJ, USA, 2015.
  5. Article
    D1
    “Algorithmic and Hardness Results for the Colorful Components Problems,” Algorithmica, vol. 73, no. 2, 2015.
  6. Conference paper
    D1
    “A Quasi-PTAS for the Two-dimensional Geometric Knapsack Problem,” in Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), San Diego, CA, USA, 2015.
  7. Conference paper
    D1
    “Approximation and Hardness Results for the Maximum Edges in Transitive Closure Problem,” in Combinatorial Algorithms (IWOCA 2014), Duluth, MN, USA, 2015.
  8. Article
    D1
    “Dense Flag Triangulations of 3-manifolds via Extremal Graph Theory,” Transactions of the American Mathematical Society, vol. 367, no. 4, 2015.
  9. Article
    D1
    “Face Numbers of Down-sets,” American Mathematical Monthly, vol. 122, no. 4, 2015.
  10. Article
    D1
    “On Multi-processor Speed Scaling with Migration,” Journal of Computer and System Sciences, vol. 81, no. 7, 2015.
  11. Conference paper
    D1
    “Improving Interpolants for Linear Arithmetic,” in Automated Technology for Verification and Analysis (ATVA 2015), Shanghai, China, 2015.
  12. Article
    D1
    “Counting Triangulations and Other Crossing-free Structures Approximately,” Computational Geometry: Theory and Applications, vol. 48, no. 5, 2015.
  13. Article
    D1
    “Counting Triangulations and Other Crossing-free Structures via Onion Layers,” Discrete & Computational Geometry, vol. 53, no. 4, 2015.
  14. Conference paper
    D1
    “A Fully Polynomial-Time Approximation Scheme for Speed Scaling with Sleep State,” in Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), San Diego, CA, USA, 2015.
  15. Conference paper
    D1
    “A o(n)-Competitive Deterministic Algorithm for Online Matching on a Line,” in Approximation and Online Algorithms (WAOA 2014), Wrocław, Poland, 2015.
  16. Conference paper
    D1
    “Truthful Mechanism Design via Correlated Tree Rounding,” in EC’15, Sixteenth ACM Conference on Economics and Computation, Portland, OR, USA, 2015.
  17. Conference paper
    D1
    “Wavelet Trees Meet Suffix Trees,” in Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), San Diego, CA, USA, 2015.
  18. Conference paper
    D1
    “New Approximation Schemes for Unsplittable Flow on a Path,” in Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), San Diego, CA, USA, 2015.
  19. Conference paper
    D1
    “Internal Compression of Protocols to Entropy,” in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015), Princeton, NJ, USA, 2015.
  20. Conference paper
    D1
    “Solving Linear Programming with Constraints Unknown,” in Automata, Languages, and Programming (ICALP 2015), Kyoto, Japan, 2015.
  21. Conference paper
    D1
    “Queries on LZ-Bounded Encodings,” in DCC 2015, Data Compression Conference, Snowbird, UT, USA, 2015.
  22. Conference paper
    D1
    “The 1-2-3-Toolkit for Building Your Own Balls-into-Bins Algorithm,” in Proceedings of the Seventeenth Workshop on Algorithm Engineering and Experiments (ALENEX 2015), San Diego, CA, USA, 2015.
  23. Article
    D1
    “Correction of Noisy Labels via Mutual Consistency Check,” Neurocomputing, vol. 160, 2015.
  24. Conference paper
    D1
    “Sampling in Space Restricted Settings,” in Computing and Combinatorics (COCOON 2015), Beijing, China, 2015.
  25. Conference paper
    D1
    “Maintaining Near-popular Matchings,” in Automata, Languages, and Programming (ICALP 2015), Kyoto, Japan, 2015.
  26. Conference paper
    D1
    “Uniformity of Point Samples in Metric Spaces Using Gap Ratio,” in Theory and Applications of Models of Computation (TAMC 2015), Singapore, 2015.
  27. Paper
    D1
    “A Probabilistic Approach to Reducing the Algebraic Complexity of Computing Delaunay Triangulations,” 2015. [Online]. Available: http://arxiv.org/abs/1505.05454.
  28. Conference paper
    D1
    “A Probabilistic Approach to Reducing Algebraic Complexity of Delaunay Triangulations,” in Algorithms -- ESA 2015, Patras, Greece, 2015.
  29. Article
    D1
    “What’s the Frequency, Kenneth?: Sublinear Fourier Sampling Off the Grid,” Algorithmica, vol. 73, no. 2, 2015.
  30. Article
    D1
    “Using Patterns to Form Homogeneous Teams,” Algorithmica, vol. 71, no. 2, 2015.
  31. Conference paper
    D1
    “Parameterized Complexity Dichotomy for Steiner Multicut,” in 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015), Munich, Germany, 2015.
  32. Conference paper
    D1
    “Improved Approximation for Fréchet Distance on c-packed Curves Matching Conditional Lower Bounds,” in Algorithms and Computation (ISAAC 2015), Nagoya, Japan, 2015.
  33. Conference paper
    D1
    “Ultra-fast Load Balancing on Scale-free Networks,” in Automata, Languages, and Programming (ICALP 2015), Kyoto, Japan, 2015.
  34. Conference paper
    D1IMPR-CS
    “Approximability of the Discrete Fréchet Distance,” in 31st International Symposium on Computational Geometry (SoCG 2015), Eindhoven, The Netherlands, 2015.
  35. Article
    D1
    “Online Checkpointing with Improved Worst-case Guarantees,” INFORMS Journal on Computing, vol. 27, no. 3, 2015.
  36. Article
    D1
    “Random Shortest Paths: Non-Euclidean Instances for Metric Optimization Problems,” Algorithmica, vol. 73, no. 1, 2015.
  37. Conference paper
    D1
    “Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping,” in FOCS 2015, IEEE 56th Annual Symposium on Foundations of Computer Science, Berkeley, CA, USA, 2015.
  38. Article
    D1
    “Sampling from Discrete Distributions and Computing Fréchet Distances,” Bulletin of the EATCS, vol. 116, 2015.
  39. Article
    D1
    “The Interval Constrained 3-coloring Problem,” Theoretical Computer Science, vol. 593, 2015.
  40. Article
    D1
    “Macroscopic Quantum Information Processing Using Spin Coherent States,” Optics Communications, vol. 337, 2015.
  41. Paper
    D1
    “Algebraic Methods in the Congested Clique,” 2015. [Online]. Available: http://arxiv.org/abs/1503.04963.
  42. Conference paper
    D1
    “Algebraic Methods in the Congested Clique,” in PODC’15, ACM Symposium on Principles of Distributed Computing, Donostia-San Sebastián, Spain, 2015.
  43. Article
    D1
    “Two Lower Bounds for Shortest Double-Base Number System,” IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences - Series A, vol. E98, no. 6, 2015.
  44. Conference paper
    D1
    “Pattern-avoiding Access in Binary Search Trees,” in FOCS 2015, IEEE 56th Annual Symposium on Foundations of Computer Science, Berkeley, CA, USA, 2015.
  45. Paper
    D1
    “Greedy Is an Almost Optimal Deque,” 2015. [Online]. Available: http://arxiv.org/abs/1506.08319.
  46. Conference paper
    D1
    “Greedy Is an Almost Optimal Deque,” in Algorithms and Data Structures (WADS 2015), Victoria, Canada, 2015.
  47. Conference paper
    D1
    “Self-Adjusting Binary Search Trees: What Makes Them Tick?,” in Algorithms -- ESA 2015, Patras, Greece, 2015.
  48. Paper
    D1
    “Pattern-avoiding Access in Binary Search Trees,” 2015. [Online]. Available: http://arxiv.org/abs/1507.06953.
  49. Paper
    D1
    “Self-Adjusting Binary Search Trees: What Makes Them Tick?,” 2015. [Online]. Available: http://arxiv.org/abs/1503.03105.
  50. Conference paper
    D1
    “Social Network Monetization via Sponsored Viral Marketing,” in SIGMETRICS’15, International Conference on Measurement and Modeling of Computer Systems, Portland, OR, USA, 2015.
  51. Conference paper
    D1
    “On Survivable Set Connectivity,” in Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), San Diego, CA, USA, 2015.
  52. Conference paper
    D1
    “Approximate Consensus in Highly Dynamic Networks: The Role of Averaging Algorithms,” in Automata, Languages, and Programming (ICALP 2015), Kyoto, Japan, 2015.
  53. Conference paper
    D1
    “Secretary Markets with Local Information,” in Automata, Languages, and Programming (ICALP 2015), Kyoto, Japan, 2015.
  54. Conference paper
    D1
    “Combinatorial Auctions with Conflict-based Externalities,” in Web and Internet Economics (WINE 2015), Amsterdam, The Netherlands, 2015.
  55. Conference paper
    D1
    “Local Doubling Dimension of Point Sets,” in Proceedings of the 27th Canadian Conference on Computational Geometry (CCCG 2015), Kingston, Canada, 2015.
  56. Article
    D1
    “On the Geometric Ramsey Number of Outerplanar Graphs,” Discrete & Computational Geometry, vol. 53, no. 1, 2015.
  57. Article
    D1
    “Clique Partitioning with Value-monotone Submodular Cost,” Discrete Optimization, vol. 15, 2015.
  58. Article
    D1
    “A Note on Quasi-Kernels in Digraphs,” Information Processing Letters, vol. 115, no. 11, 2015.
  59. Article
    D1
    “A Quantization Framework for Smoothed Analysis of Euclidean Optimization Problems,” Algorithmica, vol. 73, no. 3, 2015.
  60. Paper
    D1
    “Polynomial Kernelization for Removing Induced Claws and Diamonds,” 2015. [Online]. Available: http://arxiv.org/abs/1503.00704.
  61. Article
    D1
    “Scheduling in Wireless Networks with Rayleigh-fading Interference,” IEEE Transactions on Mobile Computing, vol. 14, no. 7, 2015.
  62. Paper
    D1
    “Improved Balanced Flow Computation Using Parametric Flow,” 2015. [Online]. Available: http://arxiv.org/abs/1512.05974.
  63. Paper
    D1
    “Memory-Adjustable Navigation Piles with Applications to Sorting and Convex Hulls,” 2015. [Online]. Available: http://arxiv.org/abs/1510.07185.
  64. Article
    D1
    “NEFI: Network Extraction From Images,” Scientific Reports, vol. 5, 2015.
  65. Article
    D1
    “From Black-Box Complexity to Designing New Genetic Algorithms,” Theoretical Computer Science, vol. 567, 2015.
  66. Article
    D1
    “Optimizing Linear Functions with the Evolutionary Algorithm -- Different Asymptotic Runtimes for Different Instances,” Theoretical Computer Science, vol. 561, 2015.
  67. Article
    D1
    “Fault-tolerant Distributed Systems in Hardware,” Bulletin of EATCS, vol. 116, 2015.
  68. Article
    D1
    “A Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market,” Information and Computation, vol. 243, 2015.
  69. Paper
    D1
    “An Improved Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market,” 2015. [Online]. Available: http://arxiv.org/abs/1510.02694.
  70. Article
    D1
    “Combinatorics of Finite Abelian Groups and Weil Representations,” Pacific Journal of Mathematics, vol. 275, no. 2, 2015.
  71. Conference paper
    D1
    “Two Proofs for Shallow Packings,” in 31st International Symposium on Computational Geometry (SoCG 2015), Eindhoven, The Netherlands, 2015.
  72. Conference paper
    D1
    and É. Tardos, “Algorithms as Mechanisms: The Price of Anarchy of Relax-and-Round,” in EC’15, Sixteenth ACM Conference on Economics and Computation, Portland, OR, USA, 2015.
  73. Article
    D1
    and É. Tardos, “Algorithms as Mechanisms: The Price of Anarchy of Relax-and-Round,” ACM SIGecom Exchanges, vol. 14, no. 2, 2015.
  74. Conference paper
    D1
    “Algorithms against Anarchy: Understanding Non-truthful Mechanisms,” in EC’15, Sixteenth ACM Conference on Economics and Computation, Portland, OR, USA, 2015.
  75. Paper
    D1
    “Node-balancing by Edge-increments,” 2015. [Online]. Available: http://arxiv.org/abs/1504.06919.
  76. Conference paper
    D1
    “Node-balancing by Edge-increments,” in Algorithms -- ESA 2015, Patras, Greece, 2015.
  77. Conference paper
    D1
    “Towards More Practical Linear Programming-Based Techniques for Algorithmic Mechanism Design,” in Algorithmic Game Theory (SAGT 2015), Saarbrücken, Germany, 2015.
  78. Article
    D1
    “On Randomized Fictitious Play for Approximating Saddle Points Over Convex Sets,” Algorithmica, vol. 73, no. 2, 2015.
  79. Conference paper
    D1
    “Algorithms in the Ultra-Wide Word Model,” in Theory and Applications of Models of Computation (TAMC 2015), Singapore, 2015.
  80. Article
    D1
    “Facets for Art Gallery Problems,” Algorithmica, vol. 73, no. 2, 2015.
  81. Conference paper
    D1
    “Area- and Boundary-Optimal Polygonalization of Planar Point Sets,” in EuroCG 2015, 31st European Workshop on Computational Geometry, Ljubljana, Slovenia, 2015.
  82. Article
    D1
    “On the Parameterized Complexity of Vertex Cover and Edge Cover with Connectivity Constraints,” Theoretical Computer Science, vol. 565, 2015.
  83. Conference paper
    D1
    “Backtracking-Assisted Multiplication,” in ArcticCrypt 2016, Longyearbyen, Norway, 2015.
  84. Article
    D1
    “Minimum Fill-in of Sparse Graphs: Kernelization and Approximation,” Algorithmica, vol. 71, no. 1, 2015.
  85. Conference paper
    D1
    “Exact solutions for the continuous 1.5D Terrain Guarding Problem,” in EuroCG 2015, 31st European Workshop on Computational Geometry, Ljubljana, Slovenia, 2015.
  86. Paper
    D1
    “Parallel Metric Tree Embedding based on an Algebraic View on Moore-Bellman-Ford,” 2015. [Online]. Available: http://arxiv.org/abs/1509.09047.
  87. Paper
    D1
    “The Continuous 1.5D Terrain Guarding Problem: Discretization, Optimal Solutions, and PTAS,” 2015. [Online]. Available: http://arxiv.org/abs/1509.08285.
  88. Conference paper
    D1
    “Medial Axis Based Routing Has Constant Load Balancing Factor,” in Algorithms -- ESA 2015, Patras, Greece, 2015.
  89. Article
    D1
    “Orientability Thresholds for Random Hypergraph,” Combinatorics, Probability and Computing, vol. 24, no. 5, 2015.
  90. Conference paper
    D1
    “Log-Concavity and Lower Bounds for Arithmetic Circuits,” in Mathematical Foundations of Computer Science 2015 (MFCS 2015), Milan, Italy, 2015.
  91. Conference paper
    D1
    “ETR-Completeness for Decision Versions of Multi-player (Symmetric) Nash Equilibria,” in Automata, Languages, and Programming (ICALP 2015), Kyoto, Japan, 2015.
  92. Conference paper
    D1
    “Markets with Production: A Polynomial Time Algorithm and a Reduction to Pure Exchange,” in EC’15, Sixteenth ACM Conference on Economics and Computation, Portland, OR, USA, 2015.
  93. Paper
    D1
    “Raising The Bar For Vertex Cover: Fixed-parameter Tractability Above A Higher Guarantee,” 2015. [Online]. Available: http://arxiv.org/abs/1509.03990.
  94. Conference paper
    D1
    “Optimal Encodings for Range Min-Max and Top-k,” in Automata, Languages, and Programming (ICALP 2015), Kyoto, Japan, 2015.
  95. Conference paper
    D1
    “Near-Optimal Distributed Maximum Flow: Extended Abstract,” in PODC’15, ACM Symposium on Principles of Distributed Computing, Donostia-San Sebastián, Spain, 2015.
  96. Paper
    D1
    “Near-Optimal Distributed Maximum Flow,” 2015. [Online]. Available: http://arxiv.org/abs/1508.04747.
  97. Conference paper
    D1
    “Online Appointment Scheduling in the Random Order Model,” in Algorithms -- ESA 2015, Patras, Greece, 2015.
  98. Article
    D1
    “Induced Disjoint Paths in Claw-Free Graphs,” SIAM Journal on Discrete Mathematics, vol. 29, no. 1, 2015.
  99. Conference paper
    D1
    “Approximate Range Emptiness in Constant Time and Optimal Space,” in Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), San Diego, CA, USA, 2015.
  100. Conference paper
    D1
    “Robust Reoptimization of Steiner Trees,” in 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015), Bangalore, India, 2015.
  101. Conference paper
    D1
    “Gossip vs. Markov Chains, and Randomness-efficient Rumor Spreading,” in Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), San Diego, CA, USA, 2015.
  102. Conference paper
    D1
    “The Offset Filtration of Convex Objects,” in Algorithms -- ESA 2015, Patras, Greece, 2015.
  103. Article
    D1
    “Improved Lower Bound for Online Strip Packing,” Theory of Computing Systems, vol. 56, no. 1, 2015.
  104. Article
    D1
    “Finding Disjoint Paths in Split Graphs,” Theory of Computing Systems, vol. 57, no. 1, 2015.
  105. Article
    D1
    “A Completeness Theory for Polynomial (Turing) Kernelization,” Algorithmica, vol. 71, no. 3, 2015.
  106. Article
    D1
    “Dividing Connected Chores Fairly,” Theoretical Computer Science, vol. 593, 2015.
  107. Article
    D1
    “Secondary Spectrum Auctions for Symmetric and Submodular Bidders,” ACM Transactions on Economics and Computation, vol. 3, no. 2, 2015.
  108. Conference paper
    D1
    “Hedonic Coalition Formation in Networks,” in Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence and the Twenty-Seventh Innovative Applications of Artificial Intelligence Conference, Austin, TX, USA, 2015.
  109. Article
    D1
    “The Saxl Conjecture and the Dominance Order,” Discrete Mathematics, vol. 338, no. 11, 2015.
  110. Article
    D1
    “Faster Fully Compressed Pattern Matching by Recompression,” ACM Transactions on Algorithms, vol. 11, no. 3, 2015.
  111. Paper
    D1
    “An Efficient Parallel Algorithm for Spectral Sparsification of Laplacian and SDDM Matrix Polynomials,” 2015. [Online]. Available: http://arxiv.org/abs/1507.07497.
  112. Paper
    D1
    “What Graphs are 2-Dot Product Graphs?,” 2015. [Online]. Available: http://arxiv.org/abs/1511.05009.
  113. Article
    D1
    “What Graphs are 2-Dot Product Graphs?,” Electronic Notes in Discrete Mathematics (Proc. EuroComb 2015), 2015.
  114. Article
    D1
    “Algorithms to Measure Diversity and Clustering in Social Networks through Dot Product Graphs,” Social Networks, vol. 41, 2015.
  115. Article
    D1
    “Root Refinement for Real Polynomials using Quadratic Interval Refinement,” Journal of Computational and Applied Mathematics, vol. 280, 2015.
  116. Conference paper
    D1
    “Secretary Problems with Non-Uniform Arrival Order,” in STOC’15, Forty-Seventh Annual ACM Symposium on Theory of Computing, Portland, OR, USA, 2015.
  117. Conference paper
    D1
    and É. Tardos, “Smooth Online Mechanisms: A Game-theoretic Problem in Renewable Energy Markets,” in EC’15, Sixteenth ACM Conference on Economics and Computation, Portland, OR, USA, 2015.
  118. Article
    D1
    “A Single-exponential FPT Algorithm for the K4-MINOR COVER Problem,” Journal of Computer and System Sciences, vol. 81, no. 1, 2015.
  119. Article
    D1
    “On the Complexity of Computing with Planar Algebraic Curves,” Journal of Complexity, vol. 31, no. 2, 2015.
  120. Paper
    D1
    “A Note On Spectral Clustering,” 2015. [Online]. Available: http://arxiv.org/abs/1509.09188.
  121. Article
    D1
    “Fixed-parameter Tractability of Multicut in Directed Acyclic Graphs,” SIAM Journal on Discrete Mathematics, vol. 29, no. 1, 2015.
  122. Conference paper
    D1
    “Demo Abstract: Voltage Scheduling of Peripheral Components on Wireless Sensor Nodes,” in 12th European Conference on Wireless Sensor Networks (EWSN 2015), Porto, Portugal, 2015.
  123. Conference paper
    D1
    “Towards Understanding the Smoothed Approximation Ratio of the 2-Opt Heuristic,” in Automata, Languages, and Programming (ICALP 2015), Kyoto, Japan, 2015.
  124. Conference paper
    D1
    “Fast Partial Distance Estimation and Applications,” in PODC’15, ACM Symposium on Principles of Distributed Computing, Donostia-San Sebastián, Spain, 2015.
  125. Conference paper
    D1
    “Towards Optimal Synchronous Counting,” in PODC’15, ACM Symposium on Principles of Distributed Computing, Donostia-San Sebastián, Spain, 2015.
  126. Conference paper
    D1
    “Efficient Counting with Optimal Resilience,” in Distributed Computing (DISC 2015), Tokyo, Japan, 2015.
  127. Article
    D1
    “PulseSync: An Efficient and Scalable Clock Synchronization Protocol,” IEEE/ACM Transactions on Networking, vol. 23, no. 3, 2015.
  128. Paper
    D1
    “Towards Optimal Synchronous Counting,” 2015. [Online]. Available: http://arxiv.org/abs/1503.06702.
  129. Paper
    D1
    “Efficient Counting with Optimal Resilience,” 2015. [Online]. Available: http://arxiv.org/abs/1508.02535.
  130. Paper
    D1
    “Independence and Efficient Domination on P6-free Graphs,” 2015. [Online]. Available: http://arxiv.org/abs/1507.02163.
  131. Article
    D1
    “Assigning Sporadic Tasks to Unrelated Machines,” Mathematical Programming / A, vol. 152, no. 1–2, 2015.
  132. Paper
    D1
    “A Still Simpler Way of Introducing the Interior-Point Method for Linear Programming,” 2015. [Online]. Available: http://arxiv.org/abs/1510.03339.
  133. Article
    D1
    “From Approximate Factorization to Root Isolation with Application to Cylindrical Algebraic Decomposition,” Journal of Symbolic Computation, vol. 66, 2015.
  134. Book chapter / section
    D1
    “On the Implementation of Combinatorial Algorithms for the Linear Exchange Market,” in Algorithms, Probability, Networks, and Games, Berlin: Springer, 2015.
  135. Book chapter / section
    D1
    “From Theory to Library of Efficient Data Types and Algorithms (LEDA) and Algorithm Engineering,” in The Human Face of Computing, London: Imperial College Press, 2015.
  136. Conference paper
    D1
    “A (2+epsilon)-Approximation Algorithm for the Storage Allocation,” in Automata, Languages, and Programming (ICALP 2015), Kyoto, Japan, 2015.
  137. Conference paper
    D1
    “Compressing and Teaching for Low VC-Dimension,” in FOCS 2015, IEEE 56th Annual Symposium on Foundations of Computer Science, Berkeley, CA, USA, 2015.
  138. Conference paper
    D1
    “Experimental Validation of a Faithful Binary Circuit Model,” in GLSVLSI’15, 25th Edition on Great Lakes Symposium on VLSI, Pittsburgh, PA, USA, 2015.
  139. Thesis
    D1IMPR-CS
    “On Efficiency and Reliability in Computer Science,” Universität des Saarlandes, Saarbrücken, 2015.
  140. Article
    D1
    “Scheduling with an Orthogonal Resource Constraint,” Algorithmica, vol. 71, no. 4, 2015.
  141. Article
    D1
    “Randomized Rumour Spreading: The Effect of the Network Topology,” Combinatorics, Probability and Computing, vol. 24, no. 2, 2015.
  142. Article
    D1
    “Faster Rumor Spreading with Multiple Calls,” The Electronic Journal of Combinatorics, vol. 22, no. 1, 2015.
  143. Article
    D1
    “Randomized Rumor Spreading: the Effect of the Network Topology,” Combinatorics, Probability and Computing, vol. 24, no. 2, 2015.
  144. Conference paper
    D1
    “B-Chromatic Number: Beyond NP-Hardness,” in 10th International Symposium on Parameterized and Exact Computation (IPEC 2015), Patras, Greece, 2015.
  145. Conference paper
    D1
    “Generalized Pseudoforest Deletion: Algorithms and Uniform Kernel,” in Mathematical Foundations of Computer Science 2015 (MFCS 2015), Milan, Italy, 2015.
  146. Thesis
    D1IMPR-CS
    “Random Walk-based Algorithms on Networks,” Universität des Saarlandes, Saarbrücken, 2015.
  147. Thesis
    D1IMPR-CS
    “Application of Multiplicative Weights Update Method in Algorithmic Game Theory,” Universität des Saarlandes, Saarbrücken, 2015.
  148. Article
    D1
    “Large-scale Habitat Corridors for Biodiversity Conservation: A Forest Corridor in Madagascar,” PLoS ONE, vol. 10, no. 7, 2015.
  149. Thesis
    D1IMPR-CS
    “Verification of Program Computations,” Universität des Saarlandes, Saarbrücken, 2015.
  150. Conference paper
    D1
    “Computing 2-Walks in Polynomial Time,” in 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015), Munich, Germany, 2015.
  151. Conference paper
    D1
    “k-Stacks: High-Density Valet Parking for Automated Vehicles,” in IV2015, IEEE Intelligent Vehicles Symposium, Seoul, Korea, 2015.
  152. Thesis
    D1
    “Implementation and Experimental Evaluation of a Combinatorial Min-Cost Flow Algorithm,” Universität des Saarlandes, Saarbrücken, 2015.
  153. Article
    D1
    “Representation of the Non-dominated Set in Biobjective Discrete Optimization,” Computers & Operations Research, vol. 63, 2015.
  154. Article
    D1
    “Efficient Optimization of many Objectives by Approximation-guided Evolution,” European Journal of Operational Research, vol. 243, no. 2, 2015.

2014

  1. Conference paper
    D1
    “Optimal Coordination Mechanisms for Multi-job Scheduling Games,” in Algorithms - ESA 2014, Wrocław, Poland, 2014.
  2. Paper
    D1
    “Near-optimal Asymmetric Binary Matrix Partitions,” 2014. [Online]. Available: http://arxiv.org/abs/1407.8170.
  3. Conference paper
    D1
    “A QPTAS for Maximum Weight Independent Set of Polygons with Polylogarithmically Many Vertices,” in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014), Portland, OR, USA, 2014.
  4. Conference paper
    D1
    “Algorithmic and Hardness Results for the Colorful Components Problems,” in LATIN 2014: Theoretical Informatics, Montevideo, Uruguay, 2014.
  5. Conference paper
    D1
    “Reordering Buffer Management with Advice,” in Approximation and Online Algorithms (WAOA 2013), Sophia Antipolis, France, 2014.
  6. Paper
    D1
    “Nerve Complexes of Circular Arcs,” 2014. [Online]. Available: http://arxiv.org/abs/1410.4336.
  7. Paper
    D1
    “Transitivity is Not a (Big) Restriction on Homotopy Types,” 2014. [Online]. Available: http://arxiv.org/abs/1409.4966.
  8. Thesis
    D1
    “Shortest and Alternative Paths in Road Networks,” Universität des Saarlandes, Saarbrücken, 2014.
  9. Article
    D1
    “A Framework for the Verification of Certifying Computations,” Journal of Automated Reasoning, vol. 52, no. 3, 2014.
  10. Article
    D1
    “Sign Rank, VC Dimension and Spectral Gaps,” Electronic Colloquium on Computational Complexity (ECCC) : Report Series, vol. 135, 2014.
  11. Conference paper
    D1
    “A Mazing 2+ε Approximation for Unsplittable Flow on a Path,” in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014), Portland, OR, USA, 2014.
  12. Conference paper
    D1
    “Complexity-theoretic Obstacles to Achieving Energy Savings with Near-threshold Computing,” in 2014 International Green Computing Conference Proceedings (IGCC 2014), Dallas, TX, USA, 2014.
  13. Paper
    D1
    “A Fully Polynomial-Time Approximation Scheme for Speed Scaling with Sleep State,” 2014. [Online]. Available: http://arxiv.org/abs/1407.0892.
  14. Conference paper
    D1
    “Computing Minimal and Maximal Suffixes of a Substring Revisited,” in Combinatorial Pattern Matching (CPM 2014), Moscow, Russia, 2014.
  15. Paper
    D1
    “Wavelet Trees Meet Suffix Trees,” 2014. [Online]. Available: http://arxiv.org/abs/1408.6182.
  16. Article
    D1
    “Internal Compression of Protocols to Entropy,” Electronic Colloquium on Computational Complexity (ECCC) : Report Series, vol. 101, 2014.
  17. Book chapter / section
    D1
    “Clear and Compress: Computing Persistent Homology in Chunks,” in Topological Methods in Data Analysis and Visualization III, Cham: Springer International, 2014.
  18. Conference paper
    D1
    “PHAT - Persistent Homology Algorithms Toolbox,” in Mathematical Software - ICMS 2014, Seoul, South Korea, 2014.
  19. Conference paper
    D1
    “Distributed Computation of Persistent Homology,” in ALENEX14, Sixteenth Workshop on Algorithm Engineering and Experiments, Portland, OR, USA, 2014.
  20. Conference paper
    D1
    “A Simple Efficient Interior Point Method for Min-cost Flow,” in Algorithms and Computation (ISAAC 2014), Jeonju, Korea, 2014.
  21. Thesis
    D1
    “A Simple Efficient Interior Point Method for Min-cost Flow,” Universität des Saarlandes, Saarbrücken, 2014.
  22. Conference paper
    D1
    “The Batched Predecessor Problem in External Memory,” in Algorithms - ESA 2014, Wrocław, Poland, 2014.
  23. Conference paper
    D1
    “Robustly and Efficiently Computing Algebraic Curves and Surfaces,” in Mathematical Software - ICMS 2014, Seoul, South Korea, 2014.
  24. Conference paper
    D1
    “CGAL - Reliable Geometric Computing for Academia and Industry,” in Mathematical Software - ICMS 2014, Seoul, South Korea, 2014.
  25. Article
    D1
    “Distributed Selfish Load Balancing on Networks,” ACM Transactions on Algorithms, vol. 11, no. 1, 2014.
  26. Article
    D1
    “Randomised Broadcasting: Memory vs. Randomness,” Theoretical Computer Science, vol. 520, 2014.
  27. Conference paper
    D1
    “Brief Announcement: The 1-2-3-Toolkit for Building Your Own Balls-into-Bins Algorithm,” in Distributed Computing (DISC 2014), Austin, TX, USA, 2014, pp. 557–558.
  28. Paper
    D1
    “The 1-2-3-Toolkit for Building Your Own Balls-into-Bins Algorithm,” 2014. [Online]. Available: http://arxiv.org/abs/1407.8433.
  29. Conference paper
    D1
    “Coordination Mechanisms for Selfish Routing over Time on a Tree,” in Automata, Languages, and Programming (ICALP 2014), Copenhagen, Denmark, 2014.
  30. Conference paper
    D1
    “New Approximability Results for the Robust k-Median Problem,” in Algorithm Theory -- SWAT 2014, Copenhagen, Denmark, 2014.
  31. Conference paper
    D1
    “Coordination Mechanisms from (almost) all Scheduling Policies,” in ITCS’14, 5th Conference on Innovations in Theoretical Computer Science, Princeton, NJ, USA, 2014.
  32. Paper
    D1
    “(1,j)-set Problem in Graphs,” 2014. [Online]. Available: http://arxiv.org/abs/1410.3091.
  33. Paper
    D1
    “Uniformity of Point Samples in Metric Spaces using Gap Ratio,” 2014. [Online]. Available: http://arxiv.org/abs/1411.7819.
  34. Paper
    D1
    “Linear Kernels for k-Tuple and Liar’s Domination in Bounded Genus Graphs,” 2014. [Online]. Available: http://arxiv.org/abs/1309.5461.
  35. Conference paper
    D1
    “A New Deterministic Algorithm for Sparse Multivariate Polynomial Interpolation,” in ISSAC 2014, 39th International Symposium on Symbolic and Algebraic Computation, Kobe, Japan, 2014.
  36. Paper
    D1
    “Only Distances are Required to Reconstruct Submanifolds,” 2014. [Online]. Available: http://arxiv.org/abs/1410.7012.
  37. Article
    D1
    “A Constant-factor Approximation Algorithm for Unsplittable Flow on Paths,” SIAM Journal on Computing, vol. 43, no. 2, 2014.
  38. Article
    D1
    “The Effect of Homogeneity on the Computational Complexity of Combinatorial Data Anonymization,” Data Mining and Knowledge Discovery, vol. 28, no. 1, 2014.
  39. Conference paper
    D1
    “Why Walking the Dog Takes Time: Frechet Distance Has no Strongly Subquadratic Algorithms Unless SETH Fails,” in FOCS 2014, 55th Annual IEEE Symposium on Foundations of Computer Science, Philadelphia, PA, USA, 2014.
  40. Paper
    D1
    “Parameterized Complexity Dichotomy for Steiner Multicut,” 2014. [Online]. Available: http://arxiv.org/abs/1404.7006.
  41. Conference paper
    D1
    “Generic Postprocessing via Subset Selection for Hypervolume and Epsilon-indicator,” in Parallel Problem Solving from Nature -- PPSN XIII, Ljublijana, Slovenia, 2014.
  42. Thesis
    D1IMPR-CS
    “Sampling from Discrete Distributions and Computing Fréchet Distances,” Universität des Saarlandes, Saarbrücken, 2014.
  43. Conference paper
    D1
    “Balls into Bins via Local Search: Cover Time and Maximum Load,” in 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), Lyon, France, 2014.
  44. Conference paper
    D1
    “De-anonymization of Heterogeneous Random Graphs in Quasilinear Time,” in Algorithms - ESA 2014, Wrocław, Poland, 2014.
  45. Paper
    D1
    “Improved Approximation for Fréchet Distance on C-packed Curves Matching Conditional Lower Bounds,” 2014. [Online]. Available: http://arxiv.org/abs/1408.1340.
  46. Paper
    D1
    “Why Walking the Dog Takes Time: Frechet Distance Has no Strongly Subquadratic Algorithms Unless SETH Fails,” 2014. [Online]. Available: http://arxiv.org/abs/1404.1448.
  47. Conference paper
    D1
    “Two-dimensional Subset Selection for Hypervolume and Epsilon-indicator,” in GECCO’14, 16th Annual Conference on Genetic and Evolutionary Computation, Vancouver, Canada, 2014.
  48. Conference paper
    D1
    “Internal DLA: Efficient Simulation of a Physical Growth Model,” in Automata, Languages, and Programming (ICALP 2014), Copenhagen, Denmark, 2014.