Publications - The Year Before Last

  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.