Publications - The Year Before Last

  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. 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. 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. 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.