OKOhad Klein

Ohad Klein

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Ohad Klein has a total of 17 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Dimension-free estimates for low degree functions on the Hamming cube

    by Komla Domelevo, Polona Durcik, Valentia Fragkiadaki, Ohad Klein, Diogo Oliveira e Silva, Lenka Slavíková, Błażej Wróbel

    The main result of this paper are dimension-free $L^p$ inequalities, $1 \lt p \lt \infty $, for low degree scalar-valued functions on the Hamming cube. More precisely, for any $p \gt 2,$ $\varepsilon \gt 0,$ and $\theta =\theta (\varepsilon ,p)\in (0,

  • Open Access

    Dimension-free discretizations of the uniform norm by small product sets

    by Lars Becker, Ohad Klein, Joseph Slote, Alexander Volberg, Haonan Zhang

    Let $f$ f be an analytic polynomial of degree at most $K-1$ K − 1 . A classical inequality of Bernstein compares the supremum norm of $f$ f over the unit circle to its supremum norm over the sampling set of the $K$ K -th roots of unity. Many extensions of this inequality exist, often understood under the umbrella of Marcinkiewicz–Zygmund-type inequalities for $L^{p},1\le p\leq \infty $ L p , 1 ≤ p ≤ ∞ norms. We study dimension-free extensions of these discretization inequalities in the high-dimension regime, where existing results construct sampling sets with cardinality growing with the total degree of the polynomial. In this work we show that dimension-free discretizations are possible with sampling sets whose cardinality is independent of $\deg (f)$ deg ( f ) and is instead governed by the maximum individual degree of $f$ f ; i.e., the largest degree of $f$ f when viewed as a univariate polynomial in any coordinate. For example, we find that for $n$ n -variate analytic polynomials $f$ f of degree at most $d$ d and individual degree at most $K-1$ K − 1 , $\|f\|_{L^{\infty }(\mathbf{D}^{n})}\leq C(X)^{d}\|f\|_{L^{\infty }(X^{n})}$ ∥ f ∥ L ∞ ( D n ) ≤ C ( X ) d ∥ f ∥ L ∞ ( X n ) for any fixed $X$ X in the unit disc $\mathbf{D}$ D with $|X|=K$ | X | = K . The dependence on $d$ d in the constant is tight for such small sampling sets, which arise naturally for example when studying polynomials of bounded degree coming from functions on products of cyclic groups. As an application we obtain a proof of the cyclic group Bohnenblust–Hille inequality with an explicit constant $\mathcal{O}(\log K)^{2d}$ O ( log K ) 2 d .


  • Open Access

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

    by 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 less than \(r^{\lceil k/2 \rceil }\) time. However, in the dense regime of parameters, where the list contains more numbers and many solutions exist, the complexity of finding one of them can be significantly improved by Wagner’s k -tree algorithm. Such algorithms for k -SUM in the dense regime have many applications, notably in cryptanalysis. In this article, assuming the average-case k -SUM conjecture, we prove that known algorithms are essentially optimal for k = 3,4,5. For k > 5, we prove the optimality of the k -tree algorithm for a limited range of parameters. We also prove similar results for k -XOR, where the sum is replaced with exclusive or. Our results are obtained by a self-reduction that, given an instance of k -SUM that has a few solutions, produces from it many instances in the dense regime. We solve each of these instances using the dense k -SUM oracle and hope that a solution to a dense instance also solves the original problem. We deal with potentially malicious oracles (that repeatedly output correlated useless solutions) by an obfuscation process that adds noise to the dense instances. Using discrete Fourier analysis, we show that the obfuscation eliminates correlations among the oracle’s solutions, even though its inputs are highly correlated.


  • Open Access

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

    by 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 less than $r^{\lceil k/2 \rceil}$ time. On the other hand, in the dense regime of parameters, where the list contains more numbers and many solutions exist, the complexity of finding one of them can be significantly improved by Wagner's $k$-tree algorithm. Such algorithms for $k$-SUM in the dense regime have many applications, notably in cryptanalysis. In this paper, assuming the average-case $k$-SUM conjecture, we prove that known algorithms are essentially optimal for $k= 3,4,5$. For $k>5$, we prove the optimality of the $k$-tree algorithm for a limited range of parameters. We also prove similar results for $k$-XOR, where the sum is replaced with exclusive or. Our results are obtained by a self-reduction that, given an instance of $k$-SUM which has a few solutions, produces from it many instances in the dense regime. We solve each of these instances using the dense $k$-SUM oracle, and hope that a solution to a dense instance also solves the original problem. We deal with potentially malicious oracles (that repeatedly output correlated useless solutions) by an obfuscation process that adds noise to the dense instances. Using discrete Fourier analysis, we show that the obfuscation eliminates correlations among the oracle's solutions, even though its inputs are highly correlated.

  • Open Access

    Quantum and classical low-degree learning via a dimension-free Remez inequality

    by Ohad Klein, Joseph Slote, Alexander Volberg, Haonan Zhang

    Recent efforts in Analysis of Boolean Functions aim to extend core results to new spaces, including to the slice $\binom{[n]}{k}$, the hypergrid $[K]^n$, and noncommutative spaces (matrix algebras). We present here a new way to relate functions on the hypergrid (or products of cyclic groups) to their harmonic extensions over the polytorus. We show the supremum of a function $f$ over products of the cyclic group $\{\exp(2πi k/K)\}_{k=1}^K$ controls the supremum of $f$ over the entire polytorus $(\{z\in\mathbf{C}:|z|=1\}^n)$, with multiplicative constant $C$ depending on $K$ and $\text{deg}(f)$ only. This Remez-type inequality appears to be the first such estimate that is dimension-free (i.e., $C$ does not depend on $n$). This dimension-free Remez-type inequality removes the main technical barrier to giving $\mathcal{O}(\log n)$ sample complexity, polytime algorithms for learning low-degree polynomials on the hypergrid and low-degree observables on level-$K$ qudit systems. In particular, our dimension-free Remez inequality implies new Bohnenblust--Hille-type estimates which are central to the learning algorithms and appear unobtainable via standard techniques. Thus we extend to new spaces a recent line of work \cite{EI22, CHP, VZ22} that gave similarly efficient methods for learning low-degree polynomials on the hypercube and observables on qubits. An additional product of these efforts is a new class of distributions over which arbitrary quantum observables are well-approximated by their low-degree truncations -- a phenomenon that greatly extends the reach of low-degree learning in quantum science \cite{CHP}.

  • Open Access

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

    by Ohad Klein

    Consider the $n$-cube graph with vertices $\{-1,1\}^n$ and edges connecting vertices with hamming distance $1$. How many hyperplanes in $\mathbb{R}^n$ are needed in order to dissect all edges? We show that at least $\widetilde{\Omega}(n^{2/3})$ are needed, which improves the previous bound of $\Omega(n^{0.51})$ by Yehuda and Yehudayoff.

  • Open Access

    Probability Mass of Rademacher Sums Beyond One Standard Deviation

    by Vojtěch Dvořák, Ohad Klein

    Let $a_1, \dots, a_n \in \mathbb{R}$ satisfy $\sum_i a_i^2 = 1$, and let $\varepsilon_1, \ldots, \varepsilon_n$ be uniformly random $\pm 1$ signs and $X = \sum_{i=1}^{n} a_i \varepsilon_i$. It is conjectured that $X = \sum_{i=1}^{n} a_i \varepsilon_i$ has $\Pr[X \geq 1] \geq 7/64$. The best lower bound so far is $1/20$, due to Oleszkiewicz. In this paper we improve this to $\Pr[X \geq 1] \geq 6/64$.

  • Open Access

    Proof of Tomaszewski's Conjecture on Randomly Signed Sums

    by 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|\leq 1] \geq 1/2$. Our main novel tools are local concentration inequalities and an improved Berry-Esseen inequality for Rademacher sums.