Noam Lifshitz

activity

20122026

most citedGlobal hypercontractivity and its applications

20 citations · 69 across the 36 of their papers we have counts for

collaborators

46 papers

math.GR2026

The Robust Thompson's Conjecture for Alternating Groups

Nathan Keller, Noam Lifshitz, Avichai Marmor +1

We show that there exists a constant $ε > 0$ such that if $C$ is a conjugacy class in $A_{n}$ of size at least $∣ A_{n} ∣^{1 - ε}$ , then $A_{n} ∖ {1} \subseteq C^{2}$ . This proves the…

math.CO2026

A Complete Intersection Theorem for Large Permutation Groups

Nathan Keller, Andrey Kupavskii, Noam Lifshitz +1

A family of permutations is called $t$ -intersecting if any two permutations in the family agree on at least $t$ elements. We prove that there exists $n_{0} \in N$ such that…

math.CO2025

The Forbidden Cross Intersection Problem for Permutations

Nathan Keller, Noam Lifshitz, Ohad Sheinfeld

We prove the following, for a universal constant $c > 0$ . Let $n \in N$ and $1 \leq t < c \frac{n}{l o g n}$ . Let $F, G \subset S_{n}$ be families of permutations such that no $σ\i…

math.CO2025

On Shapley Values and Threshold Intervals

Gil Kalai, Noam Lifshitz

Let $f : {0, 1}^{n} \to {0, 1}$ be a monotone Boolean functions, let $ψ_{k} (f)$ denote the Shapley value of the $k$ th variable and $b_{k} (f)$ denote the Banzhaf value (influence) of…

math.GR2024

Completing the proof of the Liebeck--Nikolov--Shalev conjecture

Noam Lifshitz

Liebeck, Nikolov, and Shalev conjectured the existence of an absolute constant $C > 0$ , such that for every subset $A$ of a finite simple group $G$ with $∣ A ∣ \geq 2$ , there exists $C\l…

math.GR2024

Initiating the proof of the Liebeck--Nikolov--Shalev conjecture

Nick Gill, Noam Lifshitz, László Pyber +1

Liebeck, Nikolov, and Shalev conjectured that for every subset A of a finite simple group S with |A|>1, there exist O( log|S| / log|A| ) conjugates of A whose product is S. This pa…

math.CO2024

Polynomial Bogolyubov for special linear groups via tensor rank

Shai Evra, Guy Kindler, Noam Lifshitz

We prove a polynomial Bogolyubov type lemma for the special linear group over finite fields. Specifically, we show that there exists an absolute constant $C > 0,$ such that if $A$ is…

math.CO2024

A Dense Model Theorem for the Boolean Slice

Gil Kalai, Noam Lifshitz, Dor Minzer +1

The (low soundness) linearity testing problem for the middle slice of the Boolean cube is as follows. Let $ε > 0$ and $f$ be a function on the middle slice on the Boolean c…

cs.CC2024★ 2 cited

Constant Degree Direct Product Testers with Small Soundness

Mitali Bafna, Noam Lifshitz, Dor Minzer

Let $X$ be a $d$ -dimensional simplicial complex. A function $F : X (k) \to {0, 1}^{k}$ is said to be a direct product function if there exists a function $f : X (1) \to {0, 1}$ …

math.CO2024

Product Mixing in Compact Lie Groups

David Ellis, Guy Kindler, Noam Lifshitz +1

If $G$ is a group, we say a subset $S$ of $G$ is product-free if the equation $x y = z$ has no solutions with $x, y, z \in S$ . For $D \in N$ , a group $G$ is said to be $D$ -quas…

math.CO2023★ 1 cited

On the maximum degree of induced subgraphs of the Kneser graph

Hou Tin Chau, David Ellis, Ehud Friedgut +1

For integers $n \geq k \geq 1$ , the {\em Kneser graph} $K (n, k)$ is the graph with vertex-set consisting of all the $k$ -element subsets of ${1, 2, \dots, n}$ , where two $k$ -element…

math.GR2023★ 1 cited

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 $S_{n}$ that exhibit closure under conjugation, known as \emph{normal} sets. We show that for any $ε > 0$ , there exists $n_0…

quant-ph2023

One Clean Qubit Suffices for Quantum Communication Advantage

Srinivasan Arunachalam, Uma Girish, Noam Lifshitz

We study the one-clean-qubit model of quantum communication where one qubit is in a pure state and all other qubits are maximally mixed. We demonstrate a partial function that has…

math.CO2023★ 1 cited

Bounds for Characters of the Symmetric Group: A Hypercontractive Approach

Noam Lifshitz, Avichai Marmor

Finding upper bounds for character ratios is a fundamental problem in asymptotic group theory. Previous bounds in the symmetric group have led to remarkable applications in unexpec…

math.GR2023★ 1 cited

Sharp hypercontractivity for symmetric groups and its applications

Peter Keevash, Noam Lifshitz

A recently fertile strand of research in Group Theory is developing non-abelian analogues of classical combinatorial results for arithmetic Cayley graphs, describing properties suc…

math.PR2023

Influences in Mixing Measures

Frederic Koehler, Noam Lifshitz, Dor Minzer +1

The theory of influences in product measures has profound applications in theoretical computer science, combinatorics, and discrete probability. This deep theory is intimately conn…

math.CO2023★ 1 cited

Sharp Hypercontractivity for Global Functions

Nathan Keller, Noam Lifshitz, Omri Marcus

For a function $f$ on the hypercube ${0, 1}^{n}$ with Fourier expansion $f = \sum_{S \subseteq [n]} f^(S) χ_{S}$ , the hypercontractive inequality allows bounding norms of $T_ρf=\sum_Sρ^…

math.CO2023

On $t$ -Intersecting Families of Permutations

Nathan Keller, Noam Lifshitz, Dor Minzer +1

We prove that there exists a constant $c_{0}$ such that for any $t \in N$ and any $n \geq c_{0} t$ , if $A \subset S_{n}$ is a $t$ -intersecting family of permutations then$|A|\leq…

math.CO2022

An analogue of Bonami's Lemma for functions on spaces of linear maps, and 2-2 Games

David Ellis, Guy Kindler, Noam Lifshitz

We prove an analogue of Bonami's (hypercontractive) lemma for complex-valued functions on $L (V, W)$ , where $V$ and $W$ are vector spaces over a finite field. This inequali…

math.CO2022★ 1 cited

Forbidden intersection problems for families of linear maps

David Ellis, Guy Kindler, Noam Lifshitz

We study an analogue of the Erdős-Sós forbidden intersection problem, for families of linear maps. If $V$ and $W$ are vector spaces over the same field, we say a family $\mathcal{F…

math.CO2022★ 2 cited

On the Largest Product-free Subsets of the Alternating Groups

Peter Keevash, Noam Lifshitz, Dor Minzer

A subset $A$ of a group $G$ is called product-free if there is no solution to $a = b c$ with $a, b, c$ all in $A$ . It is easy to see that the largest product-free subset of the symmetri…

math.CO2022

Isoperimetric Inequalities Made Simpler

Ronen Eldan, Guy Kindler, Noam Lifshitz +1

We give an alternative, simple method to prove isoperimetric inequalities over the hypercube. In particular, we show: 1. An elementary proof of classical isoperimetric inequalities…

cs.CC2021

Hypercontractivity on High Dimensional Expanders: Approximate Efron-Stein Decompositions for $ε$ -Product Spaces

Tom Gur, Noam Lifshitz, Siqi Liu

We prove hypercontractive inequalities on high dimensional expanders. As in the settings of the p-biased hypercube, the symmetric group, and the Grassmann scheme, our inequalities…

cs.CC2021

An Invariance Principle for the Multi-slice, with Applications

Mark Braverman, Subhash Khot, Noam Lifshitz +1

Given an alphabet size $m \in N$ thought of as a constant, and $k = (k_{1}, \dots, k_{m})$ whose entries sum of up $n$ , the $k$ -multi-slice is the set of vectors $x\i…

The Robust Thompson's Conjecture for Alternating Groups

A Complete Intersection Theorem for Large Permutation Groups

The Forbidden Cross Intersection Problem for Permutations

On Shapley Values and Threshold Intervals

Completing the proof of the Liebeck--Nikolov--Shalev conjecture

Initiating the proof of the Liebeck--Nikolov--Shalev conjecture

Polynomial Bogolyubov for special linear groups via tensor rank

A Dense Model Theorem for the Boolean Slice

Constant Degree Direct Product Testers with Small Soundness

Product Mixing in Compact Lie Groups

On the maximum degree of induced subgraphs of the Kneser graph

Improved covering results for conjugacy classes of symmetric groups via hypercontractivity

One Clean Qubit Suffices for Quantum Communication Advantage

Bounds for Characters of the Symmetric Group: A Hypercontractive Approach

Sharp hypercontractivity for symmetric groups and its applications

Influences in Mixing Measures

Sharp Hypercontractivity for Global Functions

On t-Intersecting Families of Permutations

An analogue of Bonami's Lemma for functions on spaces of linear maps, and 2-2 Games

Forbidden intersection problems for families of linear maps

On the Largest Product-free Subsets of the Alternating Groups

Isoperimetric Inequalities Made Simpler

Hypercontractivity on High Dimensional Expanders: Approximate Efron-Stein Decompositions for ε-Product Spaces

An Invariance Principle for the Multi-slice, with Applications

On $t$ -Intersecting Families of Permutations

Hypercontractivity on High Dimensional Expanders: Approximate Efron-Stein Decompositions for $ε$ -Product Spaces