Josh Alman - RankMe

90 papers A* 28A 9Journal 48Unranked 5

Year	Rank	Type	Title / Venue / Authors
2026	J	`jnl`	Every Bit Counts: A Theoretical Study of Precision-Expressivity Tradeoffs in Quantized Transformers. CoRR Sayak Chakrabarti, Toniann Pitassi, Josh Alman
2026	J	`jnl`	Learning Functions of Halfspaces. CoRR Josh Alman, Shyamal Patel, Rocco A. Servedio
2026	J	`jnl`	Poly-attention: a general scheme for higher-order self-attention. CoRR Sayak Chakrabarti, Toniann Pitassi, Josh Alman
2025	A*	`conf`	DNF Learning via Locally Mixing Random Walks. STOC Josh Alman, Shivam Nadimpalli, Shyamal Patel, Rocco A. Servedio
2025	J	`jnl`	DNF Learning via Locally Mixing Random Walks. CoRR Josh Alman, Shivam Nadimpalli, Shyamal Patel, Rocco A. Servedio
2025	J	`jnl`	Efficient Construction of Rigid Matrices Using an NP Oracle. SIAM J. Comput. Josh Alman, Lijie Chen
2025	J	`jnl`	Fast RoPE Attention: Combining the Polynomial Method and Fast Fourier Transform. CoRR Josh Alman, Zhao Song
2025	—	`conf`	Faster Algorithms for Average-Case Orthogonal Vectors and Closes Pair Problems. SOSA Josh Alman, Alexandr Andoni, Hengjie Zhang
2025	A*	`conf`	Faster Exact Learning of k-Term DNFs with Membership and Equivalence Queries. FOCS Josh Alman, Shivam Nadimpalli, Shyamal Patel, Rocco A. Servedio
2025	J	`jnl`	Faster exact learning of k-term DNFs with membership and equivalence queries. CoRR Josh Alman, Shivam Nadimpalli, Shyamal Patel, Rocco A. Servedio
2025	—	`conf`	Fine-Grained Complexity in a World Without Cryptography. EUROCRYPT (7) Josh Alman, Yizhi Huang, Kevin Yeo
2025	J	`jnl`	Fine-Grained Complexity in a World without Cryptography. IACR Cryptol. ePrint Arch. Josh Alman, Yizhi Huang, Kevin Yeo
2025	A*	`conf`	Fundamental Limitations on Subquadratic Alternatives to Transformers. ICLR Josh Alman, Hantao Yu
2025	A*	`conf`	Improving the Leading Constant of Matrix Multiplication. SODA Josh Alman, Hantao Yu
2025	A*	`conf`	Kronecker Powers, Orthogonal Vectors, and the Asymptotic Spectrum. FOCS Josh Alman, Baitian Li
2025	J	`jnl`	Kronecker Powers, Orthogonal Vectors, and the Asymptotic Spectrum. CoRR Josh Alman, Baitian Li
2025	A*	`conf`	Low Rank Matrix Rigidity: Tight Lower Bounds and Hardness Amplification. STOC Josh Alman, Jingxun Liang
2025	J	`jnl`	Low Rank Matrix Rigidity: Tight Lower Bounds and Hardness Amplification. CoRR Josh Alman, Jingxun Liang
2025	A*	`conf`	More Asymmetry Yields Faster Matrix Multiplication. SODA Josh Alman, Ran Duan, Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, Renfei Zhou
2025	J	`jnl`	Only Large Weights (And Not Skip Connections) Can Prevent the Perils of Rank Collapse. CoRR Josh Alman, Zhao Song
2025	A	`conf`	Sparsity Lower Bounds for Probabilistic Polynomials. ITCS Josh Alman, Arkadev Chattopadhyay, Ryan Williams
2025	J	`jnl`	Two Heads Are Better than One: Simulating Large Transformers with Small Ones. CoRR Hantao Yu, Josh Alman
2024	J	`jnl`	A Refined Laser Method and Faster Matrix Multiplication. TheoretiCS Josh Alman, Virginia Vassilevska Williams
2024	J	`jnl`	Faster Algorithms for Average-Case Orthogonal Vectors and Closest Pair Problems. CoRR Josh Alman, Alexandr Andoni, Hengjie Zhang
2024	A	`conf`	Finer-Grained Hardness of Kernel Density Estimation. CCC Josh Alman, Yunfeng Guan
2024	J	`jnl`	Finer-Grained Hardness of Kernel Density Estimation. CoRR Josh Alman, Yunfeng Guan
2024	J	`jnl`	Fundamental Limitations on Subquadratic Alternatives to Transformers. CoRR Josh Alman, Hantao Yu
2024	A*	`conf`	How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computation. ICLR Josh Alman, Zhao Song
2024	J	`jnl`	Improving the Leading Constant of Matrix Multiplication. CoRR Josh Alman, Hantao Yu
2024	A*	`conf`	Metric Transforms and Low Rank Representations of Kernels for Fast Attention. NeurIPS Timothy Chu, Josh Alman, Gary L. Miller, Shyam Narayanan, Mark Sellke, Zhao Song
2024	J	`jnl`	More Asymmetry Yields Faster Matrix Multiplication. CoRR Josh Alman, Ran Duan, Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, Renfei Zhou
2024	A	`conf`	Tensor Ranks and the Fine-Grained Complexity of Dynamic Programming. ITCS Josh Alman, Ethan Turok, Hantao Yu, Hengzhi Zhang
2024	A*	`conf`	The Fine-Grained Complexity of Gradient Computation for Training Large Language Models. NeurIPS Josh Alman, Zhao Song
2024	J	`jnl`	The Fine-Grained Complexity of Gradient Computation for Training Large Language Models. CoRR Josh Alman, Zhao Song
2023	A*	`conf`	Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessing. NeurIPS Josh Alman, Jiehao Liang, Zhao Song, Ruizhe Zhang, Danyang Zhuo
2023	A*	`conf`	Fast Attention Requires Bounded Entries. NeurIPS Josh Alman, Zhao Song
2023	J	`jnl`	Fast Attention Requires Bounded Entries. CoRR Josh Alman, Zhao Song
2023	—	`conf`	Faster Walsh-Hadamard Transform and Matrix Multiplication over Finite Fields using Lookup Tables. SOSA Josh Alman
2023	A*	`conf`	Faster Walsh-Hadamard and Discrete Fourier Transforms from Matrix Non-rigidity. STOC Josh Alman, Kevin Rao
2023	A*	`conf`	Generalizations of Matrix Multiplication can solve the Light Bulb Problem. FOCS Josh Alman, Hengjie Zhang
2023	J	`jnl`	Generalizations of Matrix Multiplication can solve the Light Bulb Problem. CoRR Josh Alman, Hengjie Zhang
2023	J	`jnl`	How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computation. CoRR Josh Alman, Zhao Song
2023	J	`jnl`	Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication. SIAM J. Comput. Josh Alman, Virginia Vassilevska Williams
2023	J	`jnl`	Matrix Multiplication and Number On the Forehead Communication. CoRR Josh Alman, Jaroslaw Blasiok
2023	A	`conf`	Matrix Multiplication and Number on the Forehead Communication. CCC Josh Alman, Jaroslaw Blasiok
2023	A*	`conf`	Smaller Low-Depth Circuits for Kronecker Powers. SODA Josh Alman, Yunfeng Guan, Ashwin Padaki
2023	J	`jnl`	Tensors Ranks and the Fine-Grained Complexity of Dynamic Programming. CoRR Josh Alman, Ethan Turok, Hantao Yu, Hengzhi Zhang
2022	J	`jnl`	Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessing. CoRR Josh Alman, Jiehao Liang, Zhao Song, Ruizhe Zhang, Danyang Zhuo
2022	J	`jnl`	Faster Walsh-Hadamard Transform and Matrix Multiplication over Finite Fields using Lookup Tables. CoRR Josh Alman
2022	J	`jnl`	Faster Walsh-Hadamard and Discrete Fourier Transforms From Matrix Non-Rigidity. CoRR Josh Alman, Kevin Rao
2022	A	`conf`	Optimal-Degree Polynomial Approximations for Exponentials and Gaussian Kernel Density Estimation. CCC Amol Aggarwal, Josh Alman
2022	J	`jnl`	Optimal-Degree Polynomial Approximations for Exponentials and Gaussian Kernel Density Estimation. CoRR Amol Aggarwal, Josh Alman
2022	A*	`conf`	Parameterized Sensitivity Oracles and Dynamic Algorithms Using Exterior Algebras. ICALP Josh Alman, Dean Hirsch
2022	J	`jnl`	Parameterized Sensitivity Oracles and Dynamic Algorithms using Exterior Algebras. CoRR Josh Alman, Dean Hirsch
2022	J	`jnl`	Smaller Low-Depth Circuits for Kronecker Powers. CoRR Josh Alman, Yunfeng Guan, Ashwin Padaki
2021	A*	`conf`	A Refined Laser Method and Faster Matrix Multiplication. SODA Josh Alman, Virginia Vassilevska Williams
2021	J	`jnl`	Kronecker Products, Low-Depth Circuits, and Matrix Rigidity. CoRR Josh Alman
2021	A*	`conf`	Kronecker products, low-depth circuits, and matrix rigidity. STOC Josh Alman
2021	J	`jnl`	Limits on the Universal Method for Matrix Multiplication. Theory Comput. Josh Alman
2020	J	`jnl`	A Refined Laser Method and Faster Matrix Multiplication. CoRR Josh Alman, Virginia Vassilevska Williams
2020	A*	`conf`	Algorithms and Hardness for Linear Algebra on Geometric Graphs. FOCS Josh Alman, Timothy Chu, Aaron Schild, Zhao Song
2020	J	`jnl`	Algorithms and Hardness for Linear Algebra on Geometric Graphs. CoRR Josh Alman, Timothy Chu, Aaron Schild, Zhao Song
2020	J	`jnl`	Dynamic Parameterized Problems and Algorithms. ACM Trans. Algorithms Josh Alman, Matthias Mnich, Virginia Vassilevska Williams
2020	A*	`conf`	Faster Deterministic and Las Vegas Algorithms for Offline Approximate Nearest Neighbors in High Dimensions. SODA Josh Alman, Timothy M. Chan, R. Ryan Williams
2020	A*	`conf`	Faster Update Time for Turnstile Streaming Algorithms. SODA Josh Alman, Huacheng Yu
2020	A	`conf`	OV Graphs Are (Probably) Hard Instances. ITCS Josh Alman, Virginia Vassilevska Williams
2019	—	`conf`	An Illuminating Algorithm for the Light Bulb Problem. SOSA Josh Alman
2019	A*	`conf`	Efficient Construction of Rigid Matrices Using an NP Oracle. FOCS Josh Alman, Lijie Chen
2019	J	`jnl`	Faster Update Time for Turnstile Streaming Algorithms. CoRR Josh Alman, Huacheng Yu
2019	A	`conf`	Limits on the Universal Method for Matrix Multiplication. CCC Josh Alman
2019	—	`conf`	Predicate Encryption from Bilinear Maps and One-Sided Probabilistic Rank. TCC (1) Josh Alman, Robin Hui
2019	J	`jnl`	Predicate Encryption from Bilinear Maps and One-Sided Probabilistic Rank. IACR Cryptol. ePrint Arch. Josh Alman, Robin Hui
2018	J	`jnl`	An Illuminating Algorithm for the Light Bulb Problem. CoRR Josh Alman
2018	A*	`conf`	Cell-probe lower bounds from online communication complexity. STOC Josh Alman, Joshua R. Wang, Huacheng Yu
2018	A	`conf`	Further Limitations of the Known Approaches for Matrix Multiplication. ITCS Josh Alman, Virginia Vassilevska Williams
2018	A*	`conf`	Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication. FOCS Josh Alman, Virginia Vassilevska Williams
2018	J	`jnl`	Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication. CoRR Josh Alman, Virginia Vassilevska Williams
2018	J	`jnl`	Limits on the Universal Method for Matrix Multiplication. CoRR Josh Alman
2017	J	`jnl`	Cell-Probe Lower Bounds from Online Communication Complexity. CoRR Josh Alman, Joshua R. Wang, Huacheng Yu
2017	J	`jnl`	Cell-Probe Lower Bounds from Online Communication Complexity. Electron. Colloquium Comput. Complex. Josh Alman, Joshua R. Wang, Huacheng Yu
2017	A*	`conf`	Dynamic Parameterized Problems and Algorithms. ICALP Josh Alman, Matthias Mnich, Virginia Vassilevska Williams
2017	J	`jnl`	Dynamic Parameterized Problems and Algorithms. CoRR Josh Alman, Matthias Mnich, Virginia Vassilevska Williams
2017	J	`jnl`	Further limitations of the known approaches for matrix multiplication. CoRR Josh Alman, Virginia Vassilevska Williams
2017	A*	`conf`	Probabilistic rank and matrix rigidity. STOC Josh Alman, R. Ryan Williams
2017	A	`conf`	Theoretical Foundations of Team Matchmaking. AAMAS Josh Alman, Dylan M. McKay
2016	A*	`conf`	Polynomial Representations of Threshold Functions and Algorithmic Applications. FOCS Josh Alman, Timothy M. Chan, R. Ryan Williams
2016	J	`jnl`	Polynomial Representations of Threshold Functions and Algorithmic Applications. CoRR Josh Alman, Timothy M. Chan, Ryan Williams
2016	J	`jnl`	Probabilistic Rank and Matrix Rigidity. CoRR Josh Alman, Ryan Williams
2015	A*	`conf`	Probabilistic Polynomials and Hamming Nearest Neighbors. FOCS Josh Alman, Ryan Williams
2015	J	`jnl`	Probabilistic Polynomials and Hamming Nearest Neighbors. CoRR Josh Alman, Ryan Williams