1 citations · 1 across the 5 of their papers we have counts for
9 papers
QuantumBoost: A lazy, yet fast, quantum algorithm for learning with weak hypotheses
Amira Abbas, Yanlin Chen, Tuyen Nguyen +1
The technique of combining multiple votes to enhance the quality of a decision is the core of boosting algorithms in machine learning. In particular, boosting provably increases de…
An Improved Quantum Algorithm for 3-Tuple Lattice Sieving
Lynn Engelberts, Yanlin Chen, Amin Shiraz Gilani +3
The assumed hardness of the Shortest Vector Problem in high-dimensional lattices is one of the cornerstones of post-quantum cryptography. The fastest known heuristic attacks on SVP…
Fine-Grained Complexity via Quantum Natural Proofs
Yanlin Chen, Yilei Chen, Rajendra Kumar +2
Buhrman, Patro, and Speelman presented a framework of conjectures that together form a quantum analogue of the strong exponential-time hypothesis and its variants. They called it t…
A Quantum Speed-Up for Approximating the Top Eigenvectors of a Matrix
Yanlin Chen, András Gilyén, Ronald de Wolf
Finding a good approximation of the top eigenvector of a given matrix is a basic and important computational problem, with many applications. We give two different…
QSETH strikes again: finer quantum lower bounds for lattice problem, strong simulation, hitting set problem, and more
Yanlin Chen, Yilei Chen, Rajendra Kumar +2
While seemingly undesirable, it is not a surprising fact that there are certain problems for which quantum computers offer no computational advantage over their respective classica…
Quantum Algorithms and Lower Bounds for Linear Regression with Norm Constraints
Yanlin Chen, Ronald de Wolf
Lasso and Ridge are important minimization problems in machine learning and statistics. They are versions of linear regression with squared loss where the vector …
Dimension-Preserving Reductions Between SVP and CVP in Different -Norms
Divesh Aggarwal, Yanlin Chen, Rajendra Kumar +2
We show a number of reductions between the Shortest Vector Problem and the Closest…
Improved Classical and Quantum Algorithms for the Shortest Vector Problem via Bounded Distance Decoding
Divesh Aggarwal, Yanlin Chen, Rajendra Kumar +1
The most important computational problem on lattices is the Shortest Vector Problem (SVP). In this paper, we present new algorithms that improve the state-of-the-art for provable c…
Space-efficient classical and quantum algorithms for the shortest vector problem
Yanlin Chen, Kai-Min Chung, Ching-Yi Lai
A lattice is the integer span of some linearly independent vectors. Lattice problems have many significant applications in coding theory and cryptographic systems for their conject…