Robin Kothari
LightNews LightNews
banner
robinkothari.bsky.social
Robin Kothari
@robinkothari.bsky.social
390 followers 35 following 13 posts
Theoretical computer scientist working on quantum algorithms and complexity at Google Quantum AI. Previously at Microsoft Quantum, MIT, U. Waterloo, and IIT Bombay.
Posts Replies Media Videos
robinkothari.bsky.social
Links:
arxiv.org/abs/2510.07515
scirate.com/arxiv/2510.0...
No exponential quantum speedup for $\mathrm{SIS}^\infty$ anymore
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 range outside the nor...
arxiv.org
October 10, 2025 at 6:08 AM
robinkothari.bsky.social
I believe they’re working on porting it over to a more permanent website.
August 6, 2025 at 12:52 AM
robinkothari.bsky.social
Rational degree is one of the rare measures that could be polynomially related to deterministic query complexity, quantum query complexity, sensitivity, and all our favorite measures (for total functions), but we just don't know! Bonus: we have an updated table of query separations!
Screenshot of the table of separations from the paper
April 25, 2025 at 11:03 PM