Research
Research
On Quantum Algorithms and Limitations for Convex Optimization and Lattice Problems
with Divesh Aggarwal, Rajendra Kumar, Yixin Shen, in SIAM Journal on Computing.
Also presented as a contributed talk at the 25th Conference on Quantum Information Processing, QIP, 2022.
Extended version of STACS 2021 paper with major differences.
Space-efficient Classical and Quantum Algorithms for the Shortest Vector Problem
with Kai-Min Chung, Ching-Yi Lai, in Quantum Information and Computation 2018.
with Yilei Chen, Rajendra Kumar, Subhasree Patro, Florian Speelman. To appear in APPROX 2025.
A Quantum Speed-Up for Approximating the Top Eigenvectors of a Matrix
with András Gilyén, Ronald de Wolf. In Symposium on Discrete Algorithms (SODA) 2025.
Also presented as a contributed talk at the 27th Conference on Quantum Information Processing, QIP, 2024. [Video]
Quantum algorithms and lower bounds for linear regression with norm constraints
with Ronald de Wolf. In International Colloquium on Automata, Languages and Programming (ICALP) 2023.
Also presented as a contributed talk at the 25th Conference on Quantum Information Processing, QIP, 2022. [Video]
Improved (Provable) Algorithms for the Shortest Vector Problem via Bounded Distance Decoding
with Divesh Aggarwal, Rajendra Kumar, Yixin Shen. In Symposium on Theoretical Aspects of Computer Science (STACS) 2021. [Video]
Invited to TOCS Special Issue for STACS 2021 (regretfully declined).
Dimension-preserving reductions between SVP and CVP in different p-norms
with Divesh Aggarwal, Rajendra Kumar, Zeyong Li, and Noah Stephens-Davidowitz. In Symposium on Discrete Algorithms (SODA) 2021.
A Novel Quantum Key in Distributed Networks
with Tien-Sheng Lin, Ting-Hsu Chang, Chin-Yung Lu, Sy-Yen Kuo. In 14th IEEE International Conference on Nanotechnology 2014.
Quantum Blind Signature Based on Quantum Circuit
with Tien-Sheng Lin, Ting-Hsu Chang, Chin-Yung Lu, Sy-Yen Kuo. In 14th IEEE International Conference on Nanotechnology 2014.
with Chan Ming Shen, Jei Wei Chang, Wei-Kai Lin, Li-Yi Hsu. In 16th Asian Quantum Information Science Conference.
Fine-Grained Complexity via Quantum Natural Proofs
with Yilei Chen, Rajendra Kumar, Subhasree Patro, Florian Speelman.
Lattice Problems in General Norms: Algorithms with Explicit Constants, Dimension-Preserving Reductions, and More
with Huck Bennett, Rajendra Kumar, Zeyong Li, Spencer Peters.