3 papers
math.CO2025
The Forbidden Cross Intersection Problem for Permutations
Nathan Keller, Noam Lifshitz, Ohad Sheinfeld
We prove the following, for a universal constant . Let and . Let be families of permutations such that no $σ\i…
cs.CR2025
Non-Adaptive Cryptanalytic Time-Space Lower Bounds via a Shearer-like Inequality for Permutations
Itai Dinur, Nathan Keller, Avichai Marmor
The power of adaptivity in algorithms has been intensively studied in diverse areas of theoretical computer science. In this paper, we obtain a number of sharp lower bound results…
math.GR2023
Improved covering results for conjugacy classes of symmetric groups via hypercontractivity
Nathan Keller, Noam Lifshitz, Ohad Sheinfeld
We study covering numbers of subsets of the symmetric group that exhibit closure under conjugation, known as \emph{normal} sets. We show that for any , there exists $n_0…