Publications - Last Year

  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. 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.
  4. 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.
  5. 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.
  6. 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.
  7. Article
    D1
    “Online Metric Algorithms with Untrusted Predictions,” ACM Transactions on Algorithms, vol. 19, no. 2, 2023.
  8. Article
    D1
    “Secretary and Online Matching Problems with Machine Learned Advice,” Discrete Optimization, vol. 48, no. 2, 2023.
  9. Conference paper
    D1
    “Balanced Substructures in Bicolored Graphs,” in SOFSEM 2023: Theory and Practice of Computer Science, Nový Smokovec, Slovakia, 2023.
  10. Paper
    D1
    “Parallel and Distributed Exact Single-Source Shortest Paths with Negative Edge Weights,” 2023. [Online]. Available: https://arxiv.org/abs/2303.00811.
  11. 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.
  12. 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.
  13. Paper
    D1
    “Negative-Weight Single-Source Shortest Paths in Near-linear Time,” 2023. [Online]. Available: https://arxiv.org/abs/2203.03456.
  14. Article
    D1
    “Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover,” SIAM Journal on Computing, vol. 52, no. 5, 2023.
  15. 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.
  16. Paper
    D1
    “Dynamic (1.5+Epsilon)-Approximate Matching Size in Truly Sublinear Update Time,” 2023. [Online]. Available: https://arxiv.org/abs/2302.05030.
  17. 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.
  18. 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.
  19. Conference paper
    D1
    “Fast Algorithms via Dynamic-Oracle Matroids,” in STOC ’23, 55th Annual ACM Symposium on Theory of Computing, Orlando, FL, USA, 2023.
  20. Paper
    D1
    “Incremental (1 - ε)-approximate dynamic matching in O(poly(1/ε)) update time,” 2023. [Online]. Available: https://arxiv.org/abs/2302.08432.
  21. Article
    D1
    “Treedepth Vs Circumference,” Combinatorica, vol. 43, 2023.
  22. Article
    D1
    “Treedepth Versus Circumference,” Combinatorica, 2023.
  23. 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.
  24. 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.
  25. 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.
  26. Article
    D1
    “A Linear-Time n0.4-Approximation for Longest Common Subsequence,” ACM Transactions on Algorithms, vol. 19, no. 1, 2023.
  27. 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.
  28. 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.
  29. Article
    D1
    “All the world’s a (hyper)graph: A data drama,” Digital Scholarship in the Humanities, 2023.
  30. Thesis
    D1IMPR-CS
    “Beyond Flatland : Exploring Graphs in Many Dimensions,” Universität des Saarlandes, Saarbrücken, 2023.
  31. Conference paper
    D1
    “Ollivier-Ricci Curvature for Hypergraphs: A Unified Framework,” in Eleventh International Conference on Learning Representations (ICLR 2023), Kigali, Rwanda.
  32. 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.
  33. Paper
    D1
    “Counting Small Induced Subgraphs with Edge-monotone Properties,” 2023. [Online]. Available: https://arxiv.org/abs/2311.08988.
  34. 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.
  35. 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.
  36. Article
    D1
    “On Batch Teaching Without Collusion,” Journal of Machine Learning Research, vol. 24, 2023.
  37. Thesis
    D1IMPR-CS
    “Algorithms for Sparse Convolution and Sublinear Edit Distance,” Universität des Saarlandes, Saarbrücken, 2023.
  38. 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.
  39. Article
    D1
    “Noise-Induced Network Topologies,” Physical Review Letters, vol. 130, no. 26, 2023.
  40. Paper
    D1
    “Perfect Simulation of Las Vegas Algorithms via Local Computation,” 2023. [Online]. Available: https://arxiv.org/abs/2311.11679.
  41. Article
    D1
    “Domination and Cut Problems on Chordal Graphs with Bounded Leafage,” Algorithmica, 2023.
  42. Article
    D1
    “Parameterized Complexity of Weighted Multicut in Trees,” Theoretical Computer Science, vol. 978, 2023.
  43. Article
    D1
    “Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters,” SIAM Journal on Discrete Mathematics, vol. 37, no. 4, 2023.
  44. Paper
    D1
    “Robust and Practical Solution of Laplacian Equations by Approximate Elimination,” 2023. [Online]. Available: https://arxiv.org/abs/2303.00709.
  45. Article
    D1
    “Satiation in Fisher Markets and Approximation of Nash Social Welfare,” Mathematics of Operations Research, 2023.
  46. Article
    D1
    “Tight Bound for the Number of Distinct Palindromes in a Tree,” The Electronic Journal of Combinatorics, vol. 30, no. 2, 2023.
  47. 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.
  48. 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.
  49. 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.
  50. 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.
  51. Article
    D1
    “The Hamilton Compression of Highly Symmetric Graphs,” Annals of Combinatorics, 2023.
  52. Conference paper
    D1
    “Coloring Mixed and Directional Interval Graphs,” in Graph Drawing and Network Visualization (GD 2022), Tokyo, Japan, 2023.
  53. 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.
  54. 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.
  55. 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.
  56. 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.
  57. 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.
  58. Conference paper
    D1
    “Fitting Tree Metrics with Minimum Disagreements,” in 31st Annual European Symposium on Algorithms (ESA 2023), Amsterdam, The Netherlands, 2023.
  59. Article
    D1
    “Primal and Dual Combinatorial Dimensions,” Discrete Applied Mathematics, vol. 327, 2023.
  60. 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.
  61. 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.
  62. 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.
  63. 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.
  64. 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.
  65. Article
    D1
    “Sub-exponential Time Parameterized Algorithms for Graph Layout Problems on Digraphs with Bounded Independence Number,” Algorithmica, 2023.
  66. 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.
  67. Article
    D1
    “Bounding Generalized Coloring Numbers of Planar Graphs Using Coin Models,” The Electronic Journal of Combinatorics, vol. 30, no. 3, 2023.
  68. Article
    D1
    “Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space,” SIAM Journal on Discrete Mathematics, vol. 37, no. 3, 2023.
  69. 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.
  70. Article
    D1
    “Parameterized Counting and Cayley Graph Expanders,” SIAM Journal on Discrete Mathematics, vol. 37, no. 2, 2023.
  71. Article
    D1
    “Improving EFX Guarantees through Rainbow Cycle Number,” Mathematics of Operations Research, 2023.
  72. Conference paper
    D1
    “Tournaments, Johnson Graphs, and NC-Teaching,” in Proceedings of the 34th International Conference on Algorithmic Learning Theory (ALT 2023), Singapore, Singapore, 2023.
  73. Paper
    D1
    “KDEformer: Accelerating Transformers via Kernel Density Estimation,” 2023. [Online]. Available: https://arxiv.org/abs/2302.02451.