Publications

2024

  1. Article
    D1
    “New bounds on the anti-Ramsey numbers of star graphs via maximum edge q-coloring,” Discrete Mathematics, vol. 347, no. 4, 2024.
  2. Article
    D1
    “Legal Hypergraphs,” Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, vol. 382, no. 2270, 2024.
  3. Article
    D1
    “Computing Generalized Convolutions Faster Than Brute Force,” Algorithmica, vol. 86, 2024.
  4. Article
    D1
    “On Weighted Graph Separation Problems and Flow-Augmentation,” SIAM Journal on Discrete Mathematics, 2024.
  5. 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.
  6. Article
    D1
    “On the Two-Dimensional Knapsack Problem for Convex Polygons,” ACM Transactions on Algorithms, vol. 20, no. 2, 2024.
  7. Article
    D1
    “EFX Exists for Three Agents,” Journal of the ACM, vol. 71, no. 1, 2024.
  8. Article
    D1
    “MAP- and MLE-Based Teaching,” Journal of Machine Learning Research, vol. 25, 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. 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. Paper
    D1
    “Breaking the 3/4 Barrier for Approximate Maximin Share,” 2023. [Online]. Available: https://arxiv.org/abs/2307.07304.
  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. Paper
    D1
    “Improving Approximation Guarantees for Maximin Share,” 2023. [Online]. Available: https://arxiv.org/abs/2307.12916.
  8. 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.
  9. “Online Metric Algorithms with Untrusted Predictions,” ACM Transactions on Algorithms, vol. 19, no. 2, 2023.
  10. “Secretary and Online Matching Problems with Machine Learned Advice,” Discrete Optimization, vol. 48, no. 2, 2023.
  11. Conference paper
    D1
    “Balanced Substructures in Bicolored Graphs,” in SOFSEM 2023: Theory and Practice of Computer Science, Nový Smokovec, Slovakia, 2023.
  12. Paper
    D1
    “Parallel and Distributed Exact Single-Source Shortest Paths with Negative Edge Weights,” 2023. [Online]. Available: https://arxiv.org/abs/2303.00811.
  13. Article
    D1
    “Computing Longest Lyndon Subsequences and Longest Common Lyndon Subsequences,” Algorithmica, 2023.
  14. 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.
  15. Paper
    D1
    “Negative-Weight Single-Source Shortest Paths in Near-linear Time,” 2023. [Online]. Available: https://arxiv.org/abs/2203.03456.
  16. Article
    D1
    “Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover,” SIAM Journal on Computing, vol. 52, no. 5, 2023.
  17. “Sublinear Algorithms for (1.5+Epsilon)-Approximate Matching,” in STOC ’23, 55th Annual ACM Symposium on Theory of Computing, Orlando, FL, USA, 2023.
  18. “Dynamic (1.5+Epsilon)-Approximate Matching Size in Truly Sublinear Update Time,” 2023. [Online]. Available: https://arxiv.org/abs/2302.05030.
  19. 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.
  20. 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.
  21. Conference paper
    D1
    “Fast Algorithms via Dynamic-Oracle Matroids,” in STOC ’23, 55th Annual ACM Symposium on Theory of Computing, Orlando, FL, USA, 2023.
  22. Paper
    D1
    “Incremental (1 - ε)-approximate dynamic matching in O(poly(1/ε)) update time,” 2023. [Online]. Available: https://arxiv.org/abs/2302.08432.
  23. Article
    D1
    “Treedepth Vs Circumference,” Combinatorica, vol. 43, 2023.
  24. Article
    D1
    “Treedepth Versus Circumference,” Combinatorica, 2023.
  25. 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.
  26. 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.
  27. Article
    D1
    “A Linear-Time n0.4-Approximation for Longest Common Subsequence,” ACM Transactions on Algorithms, vol. 19, no. 1, 2023.
  28. 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.
  29. 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.
  30. Article
    D1
    “All the world’s a (hyper)graph: A data drama,” Digital Scholarship in the Humanities, 2023.
  31. Thesis
    D1IMPR-CS
    “Beyond Flatland : Exploring Graphs in Many Dimensions,” Universität des Saarlandes, Saarbrücken, 2023.
  32. Conference paper
    D1
    “Ollivier-Ricci Curvature for Hypergraphs: A Unified Framework,” in Eleventh International Conference on Learning Representations (ICLR 2023), Kigali, Rwanda.
  33. 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.
  34. Paper
    D1
    “Counting Small Induced Subgraphs with Edge-monotone Properties,” 2023. [Online]. Available: https://arxiv.org/abs/2311.08988.
  35. 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.
  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. Paper
    D1
    “Perfect Simulation of Las Vegas Algorithms via Local Computation,” 2023. [Online]. Available: https://arxiv.org/abs/2311.11679.
  40. Article
    D1
    “Domination and Cut Problems on Chordal Graphs with Bounded Leafage,” Algorithmica, 2023.
  41. Article
    D1
    “Parameterized Complexity of Weighted Multicut in Trees,” Theoretical Computer Science, vol. 978, 2023.
  42. Article
    D1
    “Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters,” SIAM Journal on Discrete Mathematics, vol. 37, no. 4, 2023.
  43. Paper
    D1
    “Robust and Practical Solution of Laplacian Equations by Approximate Elimination,” 2023. [Online]. Available: https://arxiv.org/abs/2303.00709.
  44. Article
    D1
    “Satiation in Fisher Markets and Approximation of Nash Social Welfare,” Mathematics of Operations Research, 2023.
  45. Article
    D1
    “Tight Bound for the Number of Distinct Palindromes in a Tree,” The Electronic Journal of Combinatorics, vol. 30, no. 2, 2023.
  46. 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.
  47. 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.
  48. 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.
  49. 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.
  50. Article
    D1
    “The Hamilton Compression of Highly Symmetric Graphs,” Annals of Combinatorics, 2023.
  51. Conference paper
    D1
    “Coloring Mixed and Directional Interval Graphs,” in Graph Drawing and Network Visualization (GD 2022), Tokyo, Japan, 2023.
  52. 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.
  53. 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.
  54. 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.
  55. 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.
  56. Article
    D1
    “Primal and Dual Combinatorial Dimensions,” Discrete Applied Mathematics, vol. 327, 2023.
  57. 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.
  58. Article
    D1
    “Near-Optimal Search Time in δ-Optimal Space,” Algorithmica, 2023.
  59. 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.
  60. 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.
  61. 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.
  62. Article
    D1
    “Sub-exponential Time Parameterized Algorithms for Graph Layout Problems on Digraphs with Bounded Independence Number,” Algorithmica, 2023.
  63. 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.
  64. Article
    D1
    “Bounding Generalized Coloring Numbers of Planar Graphs Using Coin Models,” The Electronic Journal of Combinatorics, vol. 30, no. 3, 2023.
  65. Article
    D1
    “Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space,” SIAM Journal on Discrete Mathematics, vol. 37, no. 3, 2023.
  66. 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.
  67. Article
    D1
    “Parameterized Counting and Cayley Graph Expanders,” SIAM Journal on Discrete Mathematics, vol. 37, no. 2, 2023.
  68. Article
    D1
    “Improving EFX Guarantees through Rainbow Cycle Number,” Mathematics of Operations Research, 2023.
  69. 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.
  70. 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. “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. “A Novel Prediction Setup for Online Speed-Scaling,” 2022. [Online]. Available: https://arxiv.org/abs/2112.03082.
  16. 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.
  17. Conference paper
    D1
    “Unlabeled Multi-Robot Motion Planning with Tighter Separation Bounds,” in 38th International Symposium on Computational Geometry (SoCG 2022), Berlin, Germany, 2022.
  18. Article
    D1
    “The Smoothed Number of Pareto-optimal Solutions in Bicriteria Integer Optimization,” Mathematical Programming / A, 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. “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. Paper
    D1
    “Independence Number of Intersection Graphs of Axis-Parallel Segments,” 2022. [Online]. Available: https://arxiv.org/abs/2205.15189.
  39. 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.
  40. Paper
    D1
    “Faster Pattern Matching under Edit Distance,” 2022. [Online]. Available: https://arxiv.org/abs/2204.03087.
  41. 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.
  42. Conference paper
    D1
    “Approximate Circular Pattern Matching,” in 30th Annual European Symposium on Algorithms (ESA 2022), Berlin/Potsdam, Germany, 2022.
  43. 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.
  44. Article
    D1
    “Enumeration of Far-Apart Pairs by Decreasing Distance for Faster Hyperbolicity Computation,” ACM Journal of Experimental Algorithmics, vol. 27, 2022.
  45. Paper
    D1
    “All the World’s a (Hyper)Graph: A Data Drama,” 2022. [Online]. Available: https://arxiv.org/abs/2206.08225.
  46. Paper
    D1
    “Sharing and Caring: Creating a Culture of Constructive Criticism in Computational Legal Studies,” 2022. [Online]. Available: https://arxiv.org/abs/2205.01071.
  47. Article
    D1
    “Rechtsstrukturvergleichung,” Rabels Zeitschrift für ausländisches und internationales Privatrecht, vol. 86, no. 4, 2022.
  48. Conference paper
    D1
    “Differentially Describing Groups of Graphs,” in Proceedings of the 36th AAAI Conference on Artificial Intelligence, Virtual Conference, 2022.
  49. Article
    D1
    “Law Smells - Defining and Detecting Problematic Patterns in Legal Drafting,” Artificial Intelligence and Law, 2022.
  50. Paper
    D1
    “Differentially Describing Groups of Graphs,” 2022. [Online]. Available: https://arxiv.org/abs/2201.04064.
  51. Article
    D1
    “Indepth Combinatorial Analysis of Admissible Sets for Abstract Argumentation,” Annals of Mathematics and Artificial Intelligence, vol. 90, 2022.
  52. 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.
  53. Paper
    D1
    “Parameterized Approximation for Maximum Weight Independent Set of Rectangles and Segments,” 2022. [Online]. Available: https://arxiv.org/abs/2212.01620.
  54. 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.
  55. 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.
  56. 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.
  57. Conference paper
    D1
    “Computing Generalized Convolutions Faster Than Brute Force,” in 17th International Symposium on Parameterized and Exact Computation (IPEC 2022), Potsdam, Germany, 2022.
  58. Paper
    D1
    “Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search,” 2022. [Online]. Available: https://arxiv.org/abs/2206.13481.
  59. Conference paper
    D1
    “Hypergraph Representation via Axis-Aligned Point-Subspace Cover,” in WALCOM: Algorithms and Computation, Jember, Indonesia, 2022.
  60. Article
    D1
    “Parameterized Complexity of Directed Spanner Problems,” Algorithmica, vol. 84, 2022.
  61. 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.
  62. Conference paper
    D1
    “Parameterized Complexity of Weighted Multicut in Trees,” in Graph-Theoretic Concepts in Computer Science (WG 2022), Tübingen, Germany, 2022.
  63. 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.
  64. 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.
  65. Paper
    D1
    “Parameterized Complexity of Weighted Multicut in Trees,” 2022. [Online]. Available: https://arxiv.org/abs/2205.10105.
  66. Paper
    D1
    “Domination and Cut Problems on Chordal Graphs with Bounded Leafage,” 2022. [Online]. Available: https://arxiv.org/abs/2208.02850.
  67. Paper
    D1
    “Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters,” 2022. [Online]. Available: https://arxiv.org/abs/2206.15424.
  68. Paper
    D1
    “Subexponential Parameterized Directed Steiner Network Problems on Planar Graphs: A Complete Classification,” 2022. [Online]. Available: https://arxiv.org/abs/2208.06015.
  69. Paper
    D1
    “Physarum Inspired Dynamics to Solve Semi-Definite Programs,” 2022. [Online]. Available: https://arxiv.org/abs/2111.02291.
  70. Conference paper
    D1
    “Improved Online Algorithm for Fractional Knapsack in the Random Order Model,” in Approximation and Online Algorithms, Lisbon, Portugal, 2022.
  71. 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.
  72. Paper
    D1
    “Learning-Augmented Algorithms for Online TSP on the Line,” 2022. [Online]. Available: https://arxiv.org/abs/2206.00655.
  73. Paper
    D1
    “Coloring Mixed and Directional Interval Graphs,” 2022. [Online]. Available: https://arxiv.org/abs/2208.14250.
  74. Article
    D1
    “The Maximum-Level Vertex in an Arrangement of Lines,” Discrete & Computational Geometry, vol. 67, 2022.
  75. 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.
  76. 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.
  77. 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.
  78. Paper
    D1
    “b-Coloring Parameterized by Pathwidth is XNLP-complete,” 2022. [Online]. Available: https://arxiv.org/abs/2209.07772.
  79. 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.
  80. Paper
    D1
    “On Weighted Graph Separation Problems and Flow-Augmentation,” 2022. [Online]. Available: https://arxiv.org/abs/2208.14841.
  81. Thesis
    D1IMPR-CS
    “On Time, Time Synchronization and Noise in Time Measurement Systems,” Universität des Saarlandes, Saarbrücken, 2022.
  82. Article
    D1
    “Optimal Collusion-Free Teaching,” Journal of Machine Learning Research.
  83. 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.
  84. Conference paper
    D1
    “Near-Optimal Search Time in δ-Optimal Space,” in LATIN 2022: Theoretical Informatics, Guanajuato, Mexico, 2022.
  85. Article
    D1
    “Toward a Definitive Compressibility Measure for Repetitive Sequences,” IEEE Transactions on Information Theory, vol. 69, no. 4, 2022.
  86. 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.
  87. Paper
    D1
    “The Complexity of Contracting Bipartite Graphs into Small Cycles,” 2022. [Online]. Available: https://arxiv.org/abs/2206.07358.
  88. 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.
  89. Paper
    D1
    “Near-Linear Time Approximations for Cut Problems via Fair Cuts,” 2022. [Online]. Available: https://arxiv.org/abs/2203.00751.
  90. 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.
  91. 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.
  92. Paper
    D1
    “Makespan Scheduling of Unit Jobs with Precedence Constraints in O(1.995n) time,” 2022. [Online]. Available: https://arxiv.org/abs/2208.02664.
  93. Thesis
    D1IMPR-CS
    “Fine-Grained Complexity and Algorithm Engineering of Geometric Similarity Measures,” Universität des Saarlandes, Saarbrücken, 2022.
  94. Article
    D1
    “Fair Division of Indivisible Goods for a Class of Concave Valuations,” Journal of Artificial Intelligence Research, vol. 74, 2022.
  95. Article
    D1
    “Counting Small Induced Subgraphs Satisfying Monotone Properties,” SIAM Journal on Computing, 2022.
  96. Thesis
    D1IMPR-CS
    “Pulse Propagation, Graph Cover, and Packet Forwarding,” Universität des Saarlandes, Saarbrücken, 2022.
  97. 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.
  98. 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.