Yinzhan Xu

Publications

• Shaving Logs via Large Sieve Inequality: Faster Algorithms for Sparse Convolution and More
  with Ce Jin
  In 56th ACM Symposium on Theory of Computing (STOC 2024)
  [arXiv]


• Towards Optimal Output-Sensitive Clique Listing or: Listing Cliques from Smaller Cliques
  with Mina Dalirrooyfard, Surya Mathialagan and Virginia Vassilevska Williams
  In 56th ACM Symposium on Theory of Computing (STOC 2024)
  [arXiv]


• Simpler and Higher Lower Bounds for Shortcut Sets
  with Virginia Vassilevska Williams and Zixuan Xu
  In 2024 ACM-SIAM Symposium on Discrete Algorithms (SODA 2024)
  [arXiv]


• New Bounds for Matrix Multiplication: from Alpha to Omega
  with Virginia Vassilevska Williams, Zixuan Xu and Renfei Zhou
  In 2024 ACM-SIAM Symposium on Discrete Algorithms (SODA 2024)
  [arXiv]


• Simpler Reductions from Exact Triangle
  with Timothy M. Chan
  In 2024 SIAM Symposium on Simplicity in Algorithms (SOSA 2024)
  [arXiv]


• Faster Algorithms for Text-to-Pattern Hamming Distances
  with Timothy M. Chan, Ce Jin and Virginia Vassilevska Williams
  In 64th IEEE Symposium on Foundations of Computer Science (FOCS 2023)
  [arXiv]


• Optimal Bounds for Noisy Sorting
  with Yuzhou Gu
  In 55th ACM Symposium on Theory of Computing (STOC 2023)
  [arXiv]


• Removing Additive Structure in 3SUM-Based Reductions
  with Ce Jin
  In 55th ACM Symposium on Theory of Computing (STOC 2023)
  Invited to SICOMP special issue
  [arXiv]


• Fredman's Trick Meets Dominance Product: Fine-Grained Complexity of Unweighted APSP, 3SUM Counting, and More
  with Timothy M. Chan, and Virginia Vassilevska Williams
  In 55th ACM Symposium on Theory of Computing (STOC 2023)
  [arXiv]


• Differentially Private All-Pairs Shortest Path Distances: Improved Algorithms and Lower Bounds
  with Justin Y. Chen, Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Shyam Narayanan and Jelani Nelson
  In 2023 ACM-SIAM Symposium on Discrete Algorithms (SODA 2023)
  [conference version]


• Algorithms and Lower Bounds for Replacement Paths under Multiple Edge Failures
  with Virginia Vassilevska Williams, and Eyob Woldeghebriel
  In 63rd IEEE Symposium on Foundations of Computer Science (FOCS 2022)
  [arXiv]


• Near-Tight Algorithms for the Chamberlin-Courant and Thiele Voting Rules
  with Krzysztof Sornat, and Virginia Vassilevska Williams
  In 31st International Joint Conference on Artificial Intelligence (IJCAI 2022)
  [arXiv]


• Listing, Verifying and Counting Lowest Common Ancestors in DAGs: Algorithms and Fine-Grained Lower Bounds
  with Surya Mathialagan, and Virginia Vassilevska Williams
  In 49th International Colloquium on Automata, Languages and Programming (ICALP 2022)
  [arXiv]


• Hardness for Triangle Problems under Even More Believable Hypotheses: Reductions from Real APSP, Real 3SUM, and OV
  with Timothy M. Chan, and Virginia Vassilevska Williams
  In 54th Annual ACM Symposium on Theory of Computing (STOC 2022)
  [arXiv]


• Tight Dynamic Problem Lower Bounds from Generalized BMM and OMv
  with Ce Jin
  In 54th Annual ACM Symposium on Theory of Computing (STOC 2022)
  [arXiv]


• Fine-Grained Complexity and Algorithms for the Schulze Voting Method
  with Krzysztof Sornat, and Virginia Vassilevska Williams
  In 22nd ACM Conference on Economics and Computation (EC 2021)
  [arXiv]


• Algorithms, Reductions and Equivalences for Small Weight Variants of All-Pairs Shortest Paths
  with Timothy M. Chan, and Virginia Vassilevska Williams
  In 48th International Colloquium on Automata, Languages and Programming (ICALP 2021)
  [arXiv]


• Faster Monotone Min-Plus Product, Range Mode, and Single Source Replacement Paths
  with Yuzhou Gu, Adam Polak, and Virginia Vassilevska Williams
  In 48th International Colloquium on Automata, Languages and Programming (ICALP 2021)
  [arXiv]


• Monochromatic Triangles, Triangle Listing and APSP
  with Virginia Vassilevska Williams
  In 61st IEEE Symposium on Foundations of Computer Science (FOCS 2020)
  [arXiv]


• Faster Dynamic Range Mode
  with Bryce Sandlund
  In 47th International Colloquium on Automata, Languages and Programming (ICALP 2020)
  [arXiv]


• Truly Subcubic Min-Plus Product for Less Structured Matrices, with Applications
  with Virginia Vassilevska Williams
  In 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA 2020)
  [arXiv]


• Approximation Algorithms for Min-Distance Problems
  with Mina Dalirrooyfard, Virginia Vassilevska Williams, Nikhil Vyas, Nicole Wein, and Yuancheng Yu
  In 46th International Colloquium on Automata, Languages and Programming (ICALP 2019)
  [arXiv]


• Nearly Optimal Separation Between Partially and Fully Retroactive Data Structures
  with Lijie Chen, Erik D. Demaine, Yuzhou Gu, Virginia Vassilevska Williams, and Yuancheng Yu
  In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)
  [arXiv]


• Parameterizing the Hardness of Binary Search Tree Access Sequences by Inversion Counts
  with Meng He and Richard Peng
  In 16th Workshop on Analytic Algorithmics and Combinatorics (ANALCO 2018)
  [conference version]