Noam Lifshitz

activity

20122026

most citedGlobal hypercontractivity and its applications

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

collaborators

Showing math.COShow all

30 papers · 1 filter

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.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…

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.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.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…

math.CO2021★ 20 cited

Global hypercontractivity and its applications

Peter Keevash, Noam Lifshitz, Eoin Long +1

The hypercontractive inequality on the discrete cube plays a crucial role in many fundamental results in the Analysis of Boolean functions, such as the KKL theorem, Friedgut's junt…

math.CO2021★ 13 cited

Forbidden intersections for codes

Peter Keevash, Noam Lifshitz, Eoin Long +1

Determining the maximum size of a $t$ -intersecting code in $[m]^{n}$ was a longstanding open problem of Frankl and Füredi, solved independently by Ahlswede and Khachatrian and by Fra…

math.CO2019

Approximation by juntas in the symmetric group, and forbidden intersection problems

David Ellis, Noam Lifshitz

A family of permutations $F \subset S_{n}$ is said to be $t$ -intersecting if any two permutations in $F$ agree on at least $t$ points. It is said to be $(t - 1)$ -…

math.CO2019

High dimensional Hoffman bound and applications in extremal combinatorics

Yuval Filmus, Konstantin Golubev, Noam Lifshitz

One powerful method for upper-bounding the largest independent set in a graph is the Hoffman bound, which gives an upper bound on the largest independent set of a graph in terms of…

math.CO2019★ 5 cited

Hypercontractivity for global functions and sharp thresholds

Peter Keevash, Noam Lifshitz, Eoin Long +1

The classical hypercontractive inequality for the noise operator on the discrete cube plays a crucial role in many of the fundamental results in the Analysis of Boolean functions,…

math.CO2018

On set systems without a simplex-cluster and the Junta method

Noam Lifshitz

A family ${A_{0}, \dots, A_{d}}$ of $k$ -element subsets of $[n] = {1, 2, \dots, n}$ is called a simplex-cluster if $A_{0} \cap \dots \cap A_{d} = \emptyset$ , $|A_{0}\cup\cdots\cup A_{…

math.CO2018★ 4 cited

Hypergraph Removal Lemmas via Robust Sharp Threshold Theorems

Noam Lifshitz

The classical sharp threshold theorem of Friedgut and Kalai (1996) asserts that any symmetric monotone function $f : {0, 1}^{n} \to {0, 1}$ exhibits a sharp threshold phenomenon. Thi…

math.CO2017★ 3 cited

The Junta Method for Hypergraphs and the Erdős-Chvátal Simplex Conjecture

Nathan Keller, Noam Lifshitz

Numerous problems in extremal hypergraph theory ask to determine the maximal size of a $k$ -uniform hypergraph on $n$ vertices that does not contain an `enlarged' copy $H^{+}$ of a fi…

math.CO2017★ 5 cited

Approximation of biased Boolean functions of small total influence by DNF's

Nathan Keller, Noam Lifshitz

The influence of the $k$ 'th coordinate on a Boolean function $f : {0, 1}^{n} \to {0, 1}$ is the probability that flipping $x_{k}$ changes the value $f (x)$ . The total influence…

math.CO2017

On a biased edge isoperimetric inequality for the discrete cube

David Ellis, Nathan Keller, Noam Lifshitz

The `full' edge isoperimetric inequality for the discrete cube (due to Harper, Bernstein, Lindsay and Hart) specifies the minimum size of the edge boundary $\partial A$ of a set $A…

A Complete Intersection Theorem for Large Permutation Groups

The Forbidden Cross Intersection Problem for Permutations

On Shapley Values and Threshold Intervals

Polynomial Bogolyubov for special linear groups via tensor rank

A Dense Model Theorem for the Boolean Slice

Product Mixing in Compact Lie Groups

On the maximum degree of induced subgraphs of the Kneser graph

Bounds for Characters of the Symmetric Group: A Hypercontractive Approach

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

Global hypercontractivity and its applications

Forbidden intersections for codes

Approximation by juntas in the symmetric group, and forbidden intersection problems

High dimensional Hoffman bound and applications in extremal combinatorics

Hypercontractivity for global functions and sharp thresholds

On set systems without a simplex-cluster and the Junta method

Hypergraph Removal Lemmas via Robust Sharp Threshold Theorems

The Junta Method for Hypergraphs and the Erdős-Chvátal Simplex Conjecture

Approximation of biased Boolean functions of small total influence by DNF's

On a biased edge isoperimetric inequality for the discrete cube

On $t$ -Intersecting Families of Permutations