vix.ing · top · new · best · stats · spec

Xu, Yinzhan

  1. More Asymmetry Yields Faster Matrix Multiplication
    2024/04/25 by Josh Alman, Ran Duan, Alman, Josh +9 · 41 citations
    Computer Science · #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Matrix Theory and Algorithms #Parallel Computing and Optimization Techniques
  2. New Bounds for Matrix Multiplication: from Alpha to Omega
    2023/07/16 by Williams, Virginia Vassilevska, Xu, Yinzhan, Xu, Zixuan +1 · 26 citations
    #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  3. Truly Subcubic Min-Plus Product for Less Structured Matrices, with Applications
    2019/10/10 by Virginia Vassilevska Williams, Yinzhan Xu, Williams, Virginia Vassilevska +1 · 6 citations
    Computer Science · #Advanced Graph Theory Research #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  4. Monochromatic Triangles, Triangle Listing and APSP
    2020/07/18 by Williams, Virginia Vassilevska, Xu, Yinzhan · 3 citations
    #Computational Complexity (cs.CC) #FOS: Computer and information sciences
  5. Removing Additive Structure in 3SUM-Based Reductions
    2022/11/14 by Ce Jin, Yinzhan Xu, Jin, Ce +1 · 4 citations
    Computer Science · #Complexity and Algorithms in Graphs #Cryptography and Data Security #Machine Learning and Algorithms
  6. Towards Optimal Output-Sensitive Clique Listing or: Listing Cliques from Smaller Cliques
    2023/07/29 by Dalirrooyfard, Mina, Mathialagan, Surya, Williams, Virginia Vassilevska +1 · 3 citations
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  7. Fredman's Trick Meets Dominance Product: Fine-Grained Complexity of Unweighted APSP, 3SUM Counting, and More
    2023/03/25 by Timothy M. Chan, Chan, Timothy M., Virginia Vassilevska Williams +3 · 3 citations
    Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Limits and Structures in Graph Theory
  8. Tight Dynamic Problem Lower Bounds from Generalized BMM and OMv
    2022/02/23 by Ce Jin, Jin, Ce, Yinzhan Xu +1 · 2 citations
    Computer Science · #Optimization and Search Problems #Complexity and Algorithms in Graphs #Cryptography and Data Security
  9. Near-Tight Algorithms for the Chamberlin-Courant and Thiele Voting Rules
    2022/12/29 by Krzysztof Sornat, Sornat, Krzysztof, Virginia Vassilevska Williams +3 · 2 citations
    Computer Science · Decision Sciences · Economics, Econometrics and Finance · #68Q17 #68T42 (Secondary) #68W05 (Primary) #91B12 #Auction Theory and Applications #Computer Science and Game Theory (cs.GT) #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #Game Theory and Voting Systems #I.2.11 #Logic, Reasoning, and Knowledge #Multiagent Systems (cs.MA)
  10. Nearly Optimal Separation Between Partially And Fully Retroactive Data Structures
    2018/04/18 by Lijie Chen, Erik D. Demaine, Chen, Lijie +9 · 1 citation
    Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems
  11. Faster Dynamic Range Mode
    2020/04/19 by Sandlund, Bryce, Xu, Yinzhan · 1 citation
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  12. Faster Monotone Min-Plus Product, Range Mode, and Single Source Replacement Paths
    2021/05/06 by Gu, Yuzhou, Polak, Adam, Williams, Virginia Vassilevska +1 · 1 citation
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  13. Hardness for Triangle Problems under Even More Believable Hypotheses:\n Reductions from Real APSP, Real 3SUM, and OV
    2022/03/15 by Timothy M. Chan, Chan, Timothy M., Virginia Vassilevska Williams +3 · 1 citation
    Computer Science · #Complexity and Algorithms in Graphs #semigroups and automata theory #Logic, programming, and type systems
  14. Optimal Bounds for Noisy Sorting
    2023/02/24 by Yuzhou Gu, Gu, Yuzhou, Yinzhan Xu +1 · 1 citation
    Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Information Theory (cs.IT) #semigroups and automata theory
  15. Faster Weighted and Unweighted Tree Edit Distance and APSP Equivalence
    2024/11/10 by Nogler, Jakob, Polak, Adam, Saha, Barna +3 · 3 citations
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  16. Simpler and Higher Lower Bounds for Shortcut Sets
    2023/10/18 by Virginia Vassilevska Williams, Williams, Virginia Vassilevska, Yinzhan Xu +3 · 1 citation
    Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Limits and Structures in Graph Theory #Optimization and Search Problems
  17. Algorithms, Reductions and Equivalences for Small Weight Variants of All-Pairs Shortest Paths
    2021/02/11 by Chan, Timothy M., Williams, Virginia Vassilevska, Xu, Yinzhan · 1 citation
    #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  18. Simpler Reductions from Exact Triangle
    2023/10/17 by Timothy M. Chan, Chan, Timothy M., Yinzhan Xu +1 · 1 citation
    Computer Science · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Logic, programming, and type systems #semigroups and automata theory
  19. Approximation Algorithms for Min-Distance Problems
    2019/04/25 by Dalirrooyfard, Mina, Williams, Virginia Vassilevska, Vyas, Nikhil +3 · 1 citation
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  20. Algorithms and Lower Bounds for Replacement Paths under Multiple Edge Failures
    2022/09/15 by Virginia Vassilevska Williams, Williams, Virginia Vassilevska, Eyob Woldeghebriel +3 · 1 citation
    Computer Science · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Distributed systems and fault tolerance #FOS: Computer and information sciences #Interconnection Networks and Systems
  21. Faster Algorithms for Text-to-Pattern Hamming Distances
    2023/10/19 by Chan, Timothy M., Jin, Ce, Williams, Virginia Vassilevska +1 · 1 citation
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  22. New Separations and Reductions for Directed Preservers and Hopsets
    2024/11/12 by Gary Hoppenworth, Yinzhan Xu, Hoppenworth, Gary +3 · 1 citation
    Computer Science · #Advanced Algebra and Logic #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  23. Fine-Grained Optimality of Partially Dynamic Shortest Paths and More
    2024/07/12 by Barna Saha, Saha, Barna, Virginia Vassilevska Williams +5 · 1 citation
    Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #Computational Complexity (cs.CC) #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #F.1.3 #F.2.2 #FOS: Computer and information sciences #Optimization and Packing Problems