Showing 2025Show all
3 papers · 1 filter
cs.DS2025
Improved Time-Space Tradeoffs for 3SUM-Indexing
Itai Dinur, Alexander Golovnev
3SUM-Indexing is a preprocessing variant of the 3SUM problem that has recently received a lot of attention. The best known time-space tradeoff for the problem is (u…
quant-ph2025
Quantum Advantage via Solving Multivariate Polynomials
Pierre Briaud, Itai Dinur, Riddhi Ghosal +3
In this work, we propose a new way to (non-interactively, verifiably) demonstrate quantum advantage by solving the average-case search problem of finding a solution t…
cs.CR2025
Non-Adaptive Cryptanalytic Time-Space Lower Bounds via a Shearer-like Inequality for Permutations
Itai Dinur, Nathan Keller, Avichai Marmor
The power of adaptivity in algorithms has been intensively studied in diverse areas of theoretical computer science. In this paper, we obtain a number of sharp lower bound results…