research
∙
07/16/2023
Fast Quantum Algorithm for Attention Computation
Large language models (LLMs) have demonstrated exceptional performance a...
share
research
∙
05/04/2023
A Hyperbolic Extension of Kadison-Singer Type Results
In 2013, Marcus, Spielman, and Srivastava resolved the famous Kadison-Si...
research
∙
03/22/2023
A General Algorithm for Solving Rank-one Matrix Sensing
Matrix sensing has many real-world applications in science and engineeri...
research
∙
01/29/2023
Diverse legal case search
In last decades, legal case search has received more and more attention....
research
∙
01/01/2023
Sharper analysis of sparsely activated wide neural networks with trainable biases
This work studies training one-hidden-layer overparameterized ReLU netwo...
research
∙
11/25/2022
Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessing
Over the last decade, deep neural networks have transformed our society,...
research
∙
10/22/2022
Quartic Samples Suffice for Fourier Interpolation
We study the problem of interpolating a noisy Fourier-sparse signal in t...
research
∙
10/12/2022
Quantum Algorithms for Sampling Log-Concave Distributions and Estimating Normalizing Constants
Given a convex function fℝ^d→ℝ, the problem of sampling from a distribut...
research
∙
09/26/2022
Quantum Speedups of Optimizing Approximately Convex Functions with Applications to Logarithmic Regret Stochastic Convex Bandits
We initiate the study of quantum algorithms for optimizing approximately...
research
∙
05/30/2022
Fast Distance Oracles for Any Symmetric Norm
In the Distance Oracle problem, the goal is to preprocess n vectors x_1,...
research
∙
05/02/2022
Sparse Fourier Transform over Lattices: A Unified Approach to Signal Reconstruction
We revisit the classical problem of band-limited signal reconstruction –...
research
∙
05/02/2022
Eigenstripping, Spectral Decay, and Edge-Expansion on Posets
Fast mixing of random walks on hypergraphs has led to myriad breakthroug...
research
∙
02/24/2022
A Dynamic Fast Gaussian Transform
The Fast Gaussian Transform (FGT) enables subquadratic-time multiplicati...
research
∙
12/14/2021
Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Time
We consider the problem of training a multi-layer over-parametrized neur...
research
∙
10/09/2021
Does Preprocessing Help Training Over-parameterized Neural Networks?
Deep neural networks have achieved impressive performance in many areas....
research
∙
08/06/2021
Quantum Meets the Minimum Circuit Size Problem
In this work, we initiate the study of the Minimum Circuit Size Problem ...
research
∙
02/02/2021
Symmetric Boolean Factor Analysis with Applications to InstaHide
In this work we examine the security of InstaHide, a recently proposed s...
research
∙
11/24/2020
InstaHide's Sample Complexity When Mixing Two Private Images
Inspired by InstaHide challenge [Huang, Song, Li and Arora'20], [Chen, S...
research
∙
08/21/2020
Hyperbolic Polynomials I : Concentration and Discrepancy
Chernoff bound is a fundamental tool in theoretical computer science. It...
research
∙
04/20/2020
Quantum Copy-Protection from Hidden Subspaces
Quantum copy-protection is an innovative idea that uses the no-cloning p...
research
∙
11/05/2019
On the Quantum Complexity of Closest Pair and Related Problems
The closest pair problem is a fundamental problem of computational geome...
research
∙
05/08/2018