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

Alman, Josh

  1. More Asymmetry Yields Faster Matrix Multiplication
    2024/04/25 by Josh Alman, Ran Duan, Alman, Josh +9 · 30 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. Fast Attention Requires Bounded Entries
    2023/02/26 by Josh Alman, Alman, Josh, Zhao Song +1 · 9 citations
    Computer Science · #Machine Learning and Algorithms #Optimization and Search Problems #Complexity and Algorithms in Graphs
  3. How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computation
    2023/10/06 by Josh Alman, Zhao Song, Alman, Josh +1 · 8 citations
    Computer Science · Mathematics · #Graph Theory and Algorithms #Stochastic Gradient Optimization Techniques #Tensor decomposition and applications
  4. The Fine-Grained Complexity of Gradient Computation for Training Large Language Models
    2024/02/07 by Alman, Josh, Song, Zhao · 8 citations
    #Computation and Language (cs.CL) #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG)
  5. Dynamic Parameterized Problems and Algorithms
    2017/07/02 by Alman, Josh, Mnich, Matthias, Williams, Virginia Vassilevska · 2 citations
    #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  6. Polynomial Representations of Threshold Functions and Algorithmic Applications
    2016/08/15 by Alman, Josh, Chan, Timothy M., Williams, Ryan · 1 citation
    #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  7. Algorithms and Hardness for Linear Algebra on Geometric Graphs
    2020/11/04 by Josh Alman, Timothy Chu, Alman, Josh +5 · 1 citation
    Computer Science · Engineering · Mathematics · #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Graph theory and applications #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Matrix Theory and Algorithms #Sparse and Compressive Sensing Techniques
  8. Optimal-Degree Polynomial Approximations for Exponentials and Gaussian Kernel Density Estimation
    2022/05/12 by Aggarwal, Amol, Alman, Josh · 1 citation
    #Classical Analysis and ODEs (math.CA) #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics
  9. Probabilistic Rank and Matrix Rigidity
    2016/11/17 by Josh Alman, Alman, Josh, Ryan Williams +1 · 1 citation
    Computer Science · Engineering · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
  10. Generalizations of Matrix Multiplication can solve the Light Bulb Problem
    2023/11/02 by Josh Alman, Hengjie Zhang, Alman, Josh +1 · 1 citation
    Computer Science · #Advanced Image and Video Retrieval Techniques #Advanced Neural Network Applications #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  11. Fundamental Limitations on Subquadratic Alternatives to Transformers
    2024/10/05 by Alman, Josh, Yu, Hantao · 2 citations
    #Computation and Language (cs.CL) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Machine Learning (cs.LG)
  12. Only Large Weights (And Not Skip Connections) Can Prevent the Perils of Rank Collapse
    2025/05/22 by Josh Alman, Zhao Song, Alman, Josh +1 · 6 citations
    Computer Science · #Advanced Graph Neural Networks #FOS: Computer and information sciences #Machine Learning (cs.LG) #Natural Language Processing Techniques #Topic Modeling
  13. Fast RoPE Attention: Combining the Polynomial Method and Fast Fourier Transform
    2025/05/17 by Alman, Josh, Song, Zhao · 6 citations
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG)
  14. DNF Learning via Locally Mixing Random Walks
    2025/05/24 by Alman, Josh, Nadimpalli, Shivam, Patel, Shyamal +1 · 3 citations
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  15. Smaller Low-Depth Circuits for Kronecker Powers
    2022/11/09 by Alman, Josh, Guan, Yunfeng, Padaki, Ashwin · 1 citation
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  16. Faster Walsh-Hadamard and Discrete Fourier Transforms From Matrix Non-Rigidity
    2022/11/11 by Josh Alman, Alman, Josh, Kevin Rao +1 · 1 citation
    Computer Science · Engineering · #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #PAPR reduction in OFDM #Wireless Communication Networks Research #graph theory and CDMA systems