Ohad Klein

activity

20172022

most citedQuantum speedups need structure

1 citations · 1 across the 7 of their papers we have counts for

collaborators

Showing 2021Show all

2 papers · 1 filter

cs.CR2021

Fine-Grained Cryptanalysis: Tight Conditional Bounds for Dense k-SUM and k-XOR

Itai Dinur, Nathan Keller, Ohad Klein

An average-case variant of the $k$ -SUM conjecture asserts that finding $k$ numbers that sum to 0 in a list of $r$ random numbers, each of the order $r^{k}$ , cannot be done in much le…

math.CO2021

Probability Mass of Rademacher Sums Beyond One Standard Deviation

Vojtěch Dvořák, Ohad Klein

Let $a_{1}, \dots, a_{n} \in R$ satisfy $\sum_{i} a_{i}^{2} = 1$ , and let $ε_{1}, \dots, ε_{n}$ be uniformly random $\pm 1$ signs and $X = \sum_{i=1}^{n} a_i \varep…