Improving Algorithmic Efficiency Using Cryptography - Or Zamir
Автор: Institute for Advanced Study
Загружено: 2026-01-20
Просмотров: 274
Computer Science/Discrete Mathematics Seminar II
11:30am|Simonyi 101 and Remote Access
Topic: Improving Algorithmic Efficiency Using Cryptography
Speaker: Or Zamir
Affiliation: Tel Aviv University
Date: January 20, 2026
Cryptographic primitives have been used for various non-cryptographic objectives, such as eliminating or reducing randomness and interaction. We show how to use cryptography to improve the time complexity of solving computational problems. Specifically, we show that under standard cryptographic assumptions, we can design algorithms that are asymptotically faster than existing ones while maintaining correctness.
We introduce and construct "Trapdoor Matrix Distributions", using which, we present the first uniform reduction from worst-case to approximate and average-case matrix multiplication with optimal parameters (improving on HS2025, albeit under computational assumptions), the first WC to average-case reductions for matrix inversion and other linear operations, fast general-purpose dimension reductions, as well as a speedup of inference time in classification models.
Based on joint work with Vinod Vaikuntanathan.
Доступные форматы для скачивания:
Скачать видео mp4
-
Информация по загрузке:
