Ohad Klein

activity

20172022

most citedQuantum speedups need structure

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

collaborators

Showing 2019Show all

2 papers · 1 filter

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…