Colloquium Details
A Quantum Upheaval in Cryptography
Speaker: William Kretschmer, The Simons Institute for the Theory of Computing
Location: 60 Fifth Avenue 150
Date: March 18, 2025, 2 p.m.
Host: Marshall Ball
Synopsis:
A fundamental goal in complexity theory is to identify the minimal computational hardness assumptions that are needed to build secure cryptosystems. In view of Shor's algorithms for factoring and discrete logarithms, one would expect that a world with quantum computers necessitates stronger computational assumptions than a world without, because quantum algorithms give rise to a broader class of attacks. In this talk, I will discuss recent work of mine showing exactly the opposite: that quantum computers enable the construction of cryptography from assumptions weaker than even P ≠ NP. I'll then explain the broader implications of this work for quantum complexity theory.
Speaker Bio:
William Kretschmer is a postdoc at the Simons Institute for the Theory of Computing. Before that, he received his PhD from UT Austin under the supervision of Scott Aaronson. He studies quantum complexity theory, with a particular focus on problems involving quantum states and unitary transformations. His work was awarded best paper at CCC 2022 and best student paper at ITCS 2023.
Notes:
In-person attendance only available to those with active NYU ID cards.