Ohad Klein

activity

20172022

most citedQuantum speedups need structure

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

collaborators

8 papers

math.CO2022

Slicing all Edges of an $n$ -cube Requires $n^{2/3}$ Hyperplanes

Ohad Klein

Consider the $n$ -cube graph with vertices ${- 1, 1}^{n}$ and edges connecting vertices with hamming distance $1$ . How many hyperplanes in $R^{n}$ are needed in order to dissec…

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.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…

math.CO2020

Proof of Tomaszewski's Conjecture on Randomly Signed Sums

Nathan Keller, Ohad Klein

We prove the following conjecture, due to Tomaszewski (1986): Let $X = \sum_{i = 1}^{n} a_{i} x_{i}$ , where $\sum_{i} a_{i}^{2} = 1$ and each $x_{i}$ is a uniformly random sign. Then $\Pr[|X|\l…

cs.CC2019★ 1 cited

Quantum speedups need structure

Nathan Keller, Ohad Klein

We prove the following conjecture, raised by Aaronson and Ambainis in 2008: Let $f : {- 1, 1}^{n} \to [- 1, 1]$ be a multilinear polynomial of degree $d$ . Then there exists a var…

math.CO2019

A structure theorem for almost low-degree functions on the slice

Nathan Keller, Ohad Klein

The Fourier-Walsh expansion of a Boolean function $f : {0, 1}^{n} \to {0, 1}$ is its unique representation as a multilinear polynomial. The Kindler-Safra theorem (2002…

math.CO2017

Biased halfspaces, noise sensitivity, and local Chernoff inequalities

Nathan Keller, Ohad Klein

A halfspace is a function $f : {- 1, 1}^{n} \to {0, 1}$ of the form $f (x) = 1 (a \cdot x > t)$ , where $\sum_{i} a_{i}^{2} = 1$ . We show that if $f$ is a halfspace with $\mathb…

Slicing all Edges of an n-cube Requires n2/3 Hyperplanes

Locality-Preserving Hashing for Shifts with Connections to Cryptography

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

Probability Mass of Rademacher Sums Beyond One Standard Deviation

Proof of Tomaszewski's Conjecture on Randomly Signed Sums

Quantum speedups need structure

A structure theorem for almost low-degree functions on the slice

Biased halfspaces, noise sensitivity, and local Chernoff inequalities

Slicing all Edges of an $n$ -cube Requires $n^{2/3}$ Hyperplanes