Itai Dinur

activity

20172026

collaborators

Showing cs.DSShow 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 $T S^{3} = n^{6}$ (u…

cs.DS2022

Locality-Preserving Hashing for Shifts with Connections to Cryptography

Elette Boyle, Itai Dinur, Niv Gilboa +3

Can we sense our location in an unfamiliar environment by taking a sublinear-size sample of our surroundings? Can we efficiently encrypt a message that only someone physically clos…

cs.DS2020

Improved Algorithms for Solving Polynomial Systems over GF(2) by Multiple Parity-Counting

Itai Dinur

We consider the problem of finding a solution to a multivariate polynomial equation system of degree $d$ in $n$ variables over $F_{2}$ . For $d = 2$ , the best-known algorithm f…