Publications - Current Year

  1. Conference paper
    D1
    “Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics,” in Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC 2023), Orlando, FL, USA.
  2. Article
    D1
    “Online Metric Algorithms with Untrusted Predictions,” ACM Transactions on Algorithms, vol. 19, no. 2, 2023.
  3. Article
    D1
    “Secretary and Online Matching Problems with Machine Learned Advice,” Discrete Optimization, vol. 48, no. 2, 2023.
  4. Conference paper
    D1
    “Balanced Substructures in Bicolored Graphs,” in SOFSEM 2023: Theory and Practice of Computer Science, Nový Smokovec, Slovakia, 2023.
  5. Article
    D1
    “Computing Longest Lyndon Subsequences and Longest Common Lyndon Subsequences,” Algorithmica, 2023.
  6. 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.
  7. Conference paper
    D1
    “Sublinear Algorithms for (1.5+Epsilon)-Approximate Matching,” in Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC 2023), Orlando, FL, USA.
  8. Paper
    D1
    “Dynamic (1.5+Epsilon)-Approximate Matching Size in Truly Sublinear Update Time,” 2023. [Online]. Available: https://arxiv.org/abs/2302.05030.
  9. 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.
  10. 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.
  11. Conference paper
    D1
    “Fast Algorithms via Dynamic-Oracle Matroids,” in Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC 2023), Orlando, FL, USA.
  12. Paper
    D1
    “Incremental (1 - ε)-approximate dynamic matching in O(poly(1/ε)) update time,” 2023. [Online]. Available: https://arxiv.org/abs/2302.08432.
  13. Article
    D1
    “Treedepth Vs Circumference,” Combinatorica.
  14. Article
    D1
    “Treedepth Versus Circumference,” Combinatorica, 2023.
  15. 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.
  16. Article
    D1
    “A Linear-Time n0.4-Approximation for Longest Common Subsequence,” ACM Transactions on Algorithms, vol. 19, no. 1, 2023.
  17. Conference paper
    D1
    “Ollivier-Ricci Curvature for Hypergraphs: A Unified Framework,” in Eleventh International Conference on Learning Representations (ICLR 2023), Kigali, Rwanda.
  18. Conference paper
    D1
    “Weighted Edit Distance Computation: Strings, Trees, and Dyck,” in Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC 2023), Orlando, FL, USA.
  19. 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.
  20. Article
    D1
    “On Batch Teaching Without Collusion,” Journal of Machine Learning Research, vol. 24, 2023.
  21. Thesis
    D1
    “Algorithms for Sparse Convolution and Sublinear Edit Distance,” Universität des Saarlandes, Saarbrücken, 2023.
  22. 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.
  23. Article
    D1
    “Parameterized Complexity of Weighted Multicut in Trees,” Theoretical Computer Science, vol. 978, 2023.
  24. Paper
    D1
    “Robust and Practical Solution of Laplacian Equations by Approximate Elimination,” 2023. [Online]. Available: https://arxiv.org/abs/2303.00709.
  25. Article
    D1
    “Satiation in Fisher Markets and Approximation of Nash Social Welfare,” Mathematics of Operations Research, 2023.
  26. Article
    D1
    “Tight Bound for the Number of Distinct Palindromes in a Tree,” The Electronic Journal of Combinatorics, vol. 30, no. 2, 2023.
  27. 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.
  28. 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.
  29. 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.
  30. 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.
  31. Conference paper
    D1
    “Coloring Mixed and Directional Interval Graphs,” in Graph Drawing and Network Visualization (GD 2022), Tokyo, Japan, 2023.
  32. 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.
  33. Conference paper
    D1
    “Finding a Small Vertex Cut on Distributed Networks,” in Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC 2023), Orlando, FL, USA.
  34. 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.
  35. Article
    D1
    “Primal and Dual Combinatorial Dimensions,” Discrete Applied Mathematics, vol. 327, 2023.
  36. 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.
  37. 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.
  38. Article
    D1
    “Sub-exponential Time Parameterized Algorithms for Graph Layout Problems on Digraphs with Bounded Independence Number,” Algorithmica, 2023.
  39. Article
    D1
    “Bounding Generalized Coloring Numbers of Planar Graphs Using Coin Models,” The Electronic Journal of Combinatorics, vol. 30, no. 3, 2023.
  40. Article
    D1
    “Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space,” SIAM Journal on Discrete Mathematics, vol. 37, no. 3, 2023.
  41. 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.
  42. Article
    D1
    “Parameterized Counting and Cayley Graph Expanders,” SIAM Journal on Discrete Mathematics, vol. 37, no. 2, 2023.
  43. 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.
  44. Paper
    D1
    “KDEformer: Accelerating Transformers via Kernel Density Estimation,” 2023. [Online]. Available: https://arxiv.org/abs/2302.02451.