Sparsity Lower Bounds for Probabilistic Polynomials
with Arkadev Chattopadhyay, Ryan Williams
to appear in 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)
[link to come]
More Asymmetry Yields Faster Matrix Multiplication
with Ran Duan, Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, Renfei Zhou
to appear in 36th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2025)
[arXiv]
Improving the Leading Constant of Matrix Multiplication
with Hantao Yu
to appear in 36th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2025)
[arXiv]
Faster Algorithms for Average-Case Orthogonal Vectors and Closest Pair Problems
with Alexandr Andoni, Hengjie Zhang
to appear in 8th Symposium on Simplicity in Algorithms (SOSA 2025)
[arXiv]
Metric Transforms and Low Rank Representations of Kernels
with Timothy Chu, Gary Miller, Shyam Narayanan, Mark Sellke, Zhao Song
to appear in 38th Conference on Neural Information Processing Systems (NeurIPS 2024)
Spotlight at NeurIPS 2024
[arXiv]
The Fine-Grained Complexity of Gradient Computation for Training Large Language Models
with Zhao Song
to appear in 38th Conference on Neural Information Processing Systems (NeurIPS 2024)
[arXiv]
Finer-Grained Hardness of Kernel Density Estimation
with Yunfeng Guan
39th Computational Complexity Conference (CCC 2024)
[arXiv]
How to Capture Higher-Order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computation
with Zhao Song
12th International Conference on Learning Representations (ICLR 2024)
Spotlight at ICLR 2024
[arXiv]
Tensor Ranks and the Fine-Grained Complexity of Dynamic Programming
with Ethan Turok, Hantao Yu, Hengzhi Zhang
15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
[arXiv]
Fast Attention Requires Bounded Entries
with Zhao Song
37th Conference on Neural Information Processing Systems (NeurIPS 2023)
[arXiv]
Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessing
with Jiehao Liang, Zhao Song, Ruizhe Zhang, Danyang Zhuo
37th Conference on Neural Information Processing Systems (NeurIPS 2023)
[arXiv]
Generalizations of Matrix Multiplication can solve the Light Bulb Problem
with Hengjie Zhang
64th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2023)
[arXiv]
Matrix Multiplication and Number On the Forehead Communication
with Jarosław Błasiok
38th Computational Complexity Conference (CCC 2023)
[arXiv]
Faster Walsh-Hadamard and Discrete Fourier Transforms From Matrix Non-Rigidity
with Kevin Rao
55th Annual ACM Symposium on the Theory of Computing (STOC 2023)
[arXiv]
Smaller Low-Depth Circuits for Kronecker Powers
with Yunfeng Guan, Ashwin Padaki
34th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023)
[arXiv]
Faster Walsh-Hadamard Transform and Matrix Multiplication over Finite Fields using Lookup Tables
6th Symposium on Simplicity in Algorithms (SOSA 2023)
Best Paper Award at SOSA 2023
[arXiv]
Optimal-Degree Polynomial Approximations for Exponentials and Gaussian Kernel Density Estimation
with Amol Aggarwal
37th Computational Complexity Conference (CCC 2022)
[arXiv]
Parameterized Sensitivity Oracles and Dynamic Algorithms using Exterior Algebras
with Dean Hirsch
49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
[arXiv]
Kronecker Products, Low-Depth Circuits, and Matrix Rigidity
53rd Annual ACM Symposium on the Theory of Computing (STOC 2021)
Invited to special issue of SICOMP for STOC
[arXiv]
A Refined Laser Method and Faster Matrix Multiplication
with Virginia Vassilevska Williams
32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2021)
[arXiv]
Covered by Kevin Hartnett in Quanta Magazine!
Algorithms and Hardness for Linear Algebra on Geometric Graphs
with Timothy Chu, Aaron Schild, Zhao Song
61st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2020)
[arXiv]
OV Graphs are (Probably) Hard Instances
with Virginia Vassilevska Williams
11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
[ITCS proceedings]
Faster Update Time for Turnstile Streaming Algorithms
with Huacheng Yu
31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2020)
[arXiv]
Faster Deterministic and Las Vegas Algorithms for Offline Approximate Nearest Neighbors in High Dimensions
with Timothy M. Chan, Ryan Williams
31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2020)
[pdf]
Predicate Encryption from Bilinear Maps and One-Sided Probabilistic Rank
with Robin Hui
17th Theory of Cryptography Conference (TCC 2019)
[ePrint]
Efficient Construction of Rigid Matrices Using an NP Oracle
with Lijie Chen
SICOMP special issue for FOCS 2019 pp. 102-134
60th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2019)
Machtey Award for Best Student Paper at FOCS 2019
[pdf, journal version]
Limits on the Universal Method for Matrix Multiplication
Theory of Computing Volume 17 Article 1 pp. 1-30 (2021), special issue for CCC
34th Computational Complexity Conference (CCC 2019)
Best Student Paper Award at CCC 2019
[journal version]
An Illuminating Algorithm for the Light Bulb Problem
2nd Symposium on Simplicity in Algorithms (SOSA 2019)
[SOSA proceedings, arXiv]
Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication
with Virginia Vassilevska Williams
59th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2018)
Invited to special issue of SICOMP for FOCS
[arXiv]
Cell-Probe Lower Bounds from Online Communication Complexity
with Joshua Wang, Huacheng Yu
50th Annual ACM Symposium on the Theory of Computing (STOC 2018)
[arXiv, ECCC, STOC talk video]
Further Limitations of the Known Approaches for Matrix Multiplication
with Virginia Vassilevska Williams
9th Innovations in Theoretical Computer Science Conference (ITCS 2018)
[arXiv]
Dynamic Parameterized Problems and Algorithms
with Matthias Mnich, Virginia Vassilevska Williams
ACM Transactions on Algorithms (TALG) 16.4, 1-46 (2020)
44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
[journal version, arXiv]
Probabilistic Rank and Matrix Rigidity
with Ryan Williams
49th Annual ACM Symposium on the Theory of Computing (STOC 2017)
[arXiv, TCS+ talk video]
Theoretical Foundations of Team Matchmaking
with Dylan McKay
16th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2017)
[AAMAS proceedings, ACM DL]
Polynomial Representations of Threshold Functions and Algorithmic Applications
with Timothy M. Chan, Ryan Williams
57th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2016)
[arXiv, FOCS talk video]
Probabilistic Polynomials and Hamming Nearest Neighbors
with Ryan Williams
56th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2015)
[arXiv, Simons Institute talk video]
Laurent Phenomenon Sequences
with Cesar Cuenca, Jiaoyang Huang
Journal of Algebraic Combinatorics 43, 589-633 (2016)
[journal version, arXiv]
Circular Planar Electrical Networks: Posets and Positivity
with Carl Lian, Brandon Tran
Journal of Combinatorial Theory, Ser. A 132, 58-101 (2015)
[PDF, arXiv part 1, arXiv part 2]
THESIS
Linear Algebraic Techniques in Algorithms and Complexity
PhD Thesis, MIT EECS, August 2019
[PDF]