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
Research Subjects
Ohad Klein has a total of 17 co-authors. Here are the top co-authors by number of shared publications:
- Nathan Keller
Department of Mathematics, Bar Ilan University, Ramat Gan, Israel
3 shared publications - Haonan Zhang
Institute of Science and Technology Austria (ISTA), Klosterneuburg, Austria
2 shared publications - Ilan Komargodski
The Hebrew University of Jerusalem
2 shared publications - Itai Dinur
Ben-Gurion University
2 shared publications - Joseph Slote
California Institute of Technology
2 shared publications - Nathan Keller
Department of Mathematics Bar Ilan University Ramat Gan Israel
2 shared publications
Latest Publications
- Open Access
- 1 January 2025
- Published by Institute of Mathematics, Polish Academy of Sciences in Studia Mathematica
- Vol. 280 (2) , 161-173
Dimension-free estimates for low degree functions on the Hamming cube
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,- 1 January 2025
- Published by Institute of Mathematics, Polish Academy of Sciences in Studia Mathematica
- Vol. 280 (2) , 161-173
Open AccessDimension-free estimates for low degree functions on the Hamming cube
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
- 19 December 2024
- Published by Springer Nature in Inventiones Mathematicae
- Vol. 239 (2) , 469-503
Dimension-free discretizations of the uniform norm by small product sets
Let $f$ be an analytic polynomial of degree at most $K-1$ . A classical inequality of Bernstein compares the supremum norm of $f$ over the unit circle to its supremum norm over the sampling set of the $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 $ 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)$ and is instead governed by the maximum individual degree of $f$ ; i.e., the largest degree of $f$ when viewed as a univariate polynomial in any coordinate. For example, we find that for $n$ -variate analytic polynomials $f$ of degree at most $d$ and individual degree at most $K-1$ , $\|f\|_{L^{\infty }(\mathbf{D}^{n})}\leq C(X)^{d}\|f\|_{L^{\infty }(X^{n})}$ for any fixed $X$ in the unit disc $\mathbf{D}$ with $|X|=K$ . The dependence on $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}$ .- 19 December 2024
- Published by Springer Nature in Inventiones Mathematicae
- Vol. 239 (2) , 469-503
Open AccessDimension-free discretizations of the uniform norm by small product sets
Let $f$ be an analytic polynomial of degree at most $K-1$ . A classical inequality of Bernstein compares the supremum norm of $f$ over the unit circle to its supremum norm over the sampling set of the $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 $ 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)$ and is instead governed by the maximum individual degree of $f$ ; i.e., the largest degree of $f$ when viewed as a univariate polynomial in any coordinate. For example, we find that for $n$ -variate analytic polynomials $f$ of degree at most $d$ and individual degree at most $K-1$ , $\|f\|_{L^{\infty }(\mathbf{D}^{n})}\leq C(X)^{d}\|f\|_{L^{\infty }(X^{n})}$ for any fixed $X$ in the unit disc $\mathbf{D}$ with $|X|=K$ . The dependence on $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}$ . - 2 December 2024
- Published by Springer Nature
- p. 383-412
On the (Im)possibility of Game-Theoretically Fair Leader Election Protocols
- 2 December 2024
- Published by Springer Nature
- p. 383-412
On the (Im)possibility of Game-Theoretically Fair Leader Election Protocols
- Open Access
- 11 June 2024
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 71 (3) , 1-41
Fine-grained Cryptanalysis: Tight Conditional Bounds for Dense k -SUM and k -XOR
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.- 11 June 2024
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 71 (3) , 1-41
Open AccessFine-grained Cryptanalysis: Tight Conditional Bounds for Dense k -SUM and k -XOR
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
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 AccessFine-Grained Cryptanalysis: Tight Conditional Bounds for Dense k-SUM and k-XOR
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
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 AccessQuantum and classical low-degree learning via a dimension-free Remez inequality
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}. - 9 August 2023
- Published by Springer Nature
- p. 139-170
New Bounds on the Local Leakage Resilience of Shamir’s Secret Sharing Scheme
- 9 August 2023
- Published by Springer Nature
- p. 139-170
New Bounds on the Local Leakage Resilience of Shamir’s Secret Sharing Scheme
- Open AccessSlicing all Edges of an $n$-cube Requires $n^{2/3}$ HyperplanesConsider 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 AccessSlicing all Edges of an $n$-cube Requires $n^{2/3}$ HyperplanesConsider 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
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 AccessProbability Mass of Rademacher Sums Beyond One Standard Deviation
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
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.Open AccessProof of Tomaszewski's Conjecture on Randomly Signed Sums
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.