No exponential quantum speedup for ${\mathrm{SIS}}^{\infty }$ anymore

Robin Kothari, Ryan O'Donnell, Kewen Wu

In 2021, Chen, Liu, and Zhandry presented an efficient quantum algorithm for the average-case ${\ell }_{\infty }$-Short Integer Solution (${\mathrm{SIS}}^{\infty }$) problem, in a parameter r…