CS & Engineering Department, Huji
I was a PostDoc at the Hebrew University, hosted by Ilan Komargodski.
I had my PhD under the supervision of Nathan Keller.
My research interests include Combinatorics, Probability and Algorithms.
S. Evra, S. Gadot, O. Klein, I. Komargodski. Verifying Groups in Linear Time, FOCS'24.
P. Ivanisvili, O. Klein, R. Vershynin. Covering the hypercube, the uncertainty principle, and an interpolation formula, preprint.
L. Becker, O. Klein, J. Slote, A. Volberg, H. Zhang. A dimension-free discrete Remez inequality on multi-tori, ITCS'24.
O. Klein, I. Komargodski. New Bounds on the Local Leakage Resilience of Shamir's Secret Sharing Scheme, Crypto'23.
O. Klein. Slicing all Edges of an n-cube Requires n²ᐟ³ Hyperplanes, FOCS'23.
I. Dinur, N. Keller, O. Klein. Fine-Grained Cryptanalysis: Tight Conditional Bounds for Dense k-SUM and k-XOR, FOCS'21.
V. Dvorak & O. Klein. Probability Mass of Rademacher Sums Beyond One Standard Deviation, SIAM Journal on Discrete Mathematics, 2022.
N. Keller & O. Klein. Proof of Tomaszewski's Conjecture on Randomly Signed Sums, Advances in Mathematics, 2022. STOC'21.
E. Boyle, I. Dinur, N. Gilboa, Y. Ishai, N. Keller, O. Klein. Locality-Preserving Hashing for Shifts with Connections to Cryptography, ITCS'22.
N. Keller & O. Klein. A Structure Theorem for Almost Low-Degree Functions on the Slice, Israel Journal of Mathematics, 2020.
I. Dinur, N. Keller, O. Klein. An Optimal Distributed Discrete Log Protocol with Applications to Homomorphic Secret Sharing, Journal of Cryptology, 2020. Crypto'18.
N. Keller & O. Klein. Biased halfspaces, noise sensitivity, and local Chernoff inequalities, Discrete Analysis, 2019.