LECTURES A GRATIS GLOBAL SERVICE
⌕ SEARCH GRATIS GLOBAL ↗
LECTURES
No Exponential Quantum Speedup for SIS^inf Anymore
SOURCE: YOUTUBE · NO TRACKING UNTIL YOU PRESS PLAY · TROUBLE PLAYING? WATCH AT THE SOURCE ↗

No Exponential Quantum Speedup for SIS^inf Anymore

128 MIN · EN · STATUS: [ STREAMING ]
RATE THIS
IAS

Kewen Wu, speaking in the Institute for Advanced Study's Computer Science/Discrete Mathematics Seminar, argues that a well known quantum speedup for the Short-Integer-Solution problem under the infinity norm no longer holds. He starts from the 2021 result of Chen, Liu, and Zhandry, which gave an efficient quantum algorithm for SIS^inf in a parameter regime with no known classical analog, a result notable because SIS^inf is an unstructured problem and their techniques departed from earlier exponential quantum speedups. Wu presents joint work with Robin Kothari and Ryan O'Donnell constructing efficient classical algorithms for SIS^inf and the more general Constrained-Integer-Solution problems studied in that paper, closing the gap and showing the exponential advantage disappears. The talk walks through the structure of the original quantum approach and the classical techniques that match it, aimed at a specialist audience in quantum algorithms, cryptography, and computational complexity.

At a glance

Lecture facts

Runtime compared with the other 734 Mathematics lectures
Runtime2 h 8 m
Compared with MathematicsLonger than 98%
Source channelInstitute for Advanced Study (YouTube)