17 citations · 54 across the 24 of their papers we have counts for
32 papers
A Complete Intersection Theorem for Large Permutation Groups
Nathan Keller, Andrey Kupavskii, Noam Lifshitz +1
A family of permutations is called -intersecting if any two permutations in the family agree on at least elements. We prove that there exists such that…
Sharp Hypercontractivity for Global Functions
Nathan Keller, Noam Lifshitz, Omri Marcus
For a function on the hypercube with Fourier expansion , the hypercontractive inequality allows bounding norms of $T_ρf=\sum_Sρ^…
On -Intersecting Families of Permutations
Nathan Keller, Noam Lifshitz, Dor Minzer +1
We prove that there exists a constant such that for any and any , if is a -intersecting family of permutations then$|A|\leq…
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…
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 -SUM conjecture asserts that finding numbers that sum to 0 in a list of random numbers, each of the order , cannot be done in much le…
Error Resilient Space Partitioning
Orr Dunkelman, Zeev Geyzel, Chaya Keller +4
A major research area in discrete geometry is to consider the best way to partition the -dimensional Euclidean space under various quality criteria. In this paper…