NLNoam Lifshitz

Noam Lifshitz

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Noam Lifshitz has a total of 19 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Top Cited Papers

    Sharp hypercontractivity for global functions

    by Nathan Keller, Noam Lifshitz, Omri Marcus

    For a function f \colon \{0,1\}^{n} \to \mathbb{R} with Fourier expansion f=\sum_{S \subset \{1,\ldots,n\}}\hat f(S)\chi_{S} , the hypercontractive inequality for the noise operator allows bounding norms of T_{\rho} f = \sum_{S} \rho^{|S|}\hat f(S)\chi_{S} in terms of norms of f . If f is Boolean-valued, the level- d inequality allows bounding the norm of f^{=d}=\sum_{|S|=d}\hat f(S)\chi_{S} in terms of \mathbb{E}[f] . These two inequalities play a central role in analysis of Boolean functions and its applications. While both inequalities hold in a sharp form when the hypercube \{0,1\}^{n} is endowed with the uniform measure, it is easy to show that they do not hold for more general discrete product spaces, and finding a ‘natural’ generalization was a long-standing open problem. Keevash, Lifshitz, Long, and Minzer [J. Amer. Math. Soc. 37, 245–279 (2024)] obtained a hypercontractive inequality for general discrete product spaces, that holds for functions which are ‘global’ – namely, are not significantly affected by a restriction of a small set of coordinates. This hypercontractive inequality is not sharp, which precludes applications to the symmetric group S_{n} and to other settings where sharpness of the bound is crucial. Also, no sharp level- d inequality for global functions over general discrete product spaces is known. We obtain sharp versions of the hypercontractive inequality and of the level- d inequality for global functions over discrete product spaces. Our inequalities open the way for diverse applications to extremal set theory, group theory, theoretical computer science, and number theory. We demonstrate this by proving quantitative bounds on the size of intersecting families of sets and vectors under weak symmetry conditions and by describing numerous applications that were obtained using our results. Those contain applications to the study of functions over the symmetric group S_{n} – including hypercontractivity and level- d inequalities, character bounds, variants of Roth’s theorem and of Bogolyubov’s lemma, and diameter bounds, as well as an application to the Furstenberg–Sárközy problem on the maximal size of a subset of \{1,\ldots,n\} which does not contain two elements that differ by a perfect square.


  • Open Access

    The Forbidden Cross Intersection Problem for Permutations

    by Nathan Keller, Noam Lifshitz, Ohad Sheinfeld

    We prove the following, for a universal constant $c>0$. Let $n \in \mathbb{N}$ and $1 \leq t0$, the statement fails for $t=(1+ε)\frac{n}{\log_2 n}$ and all $n>n_0(ε)$. This solves the cross-intersection variant of the Erdős-Sós forbidden intersection problem for permutations. The best previously known result, by Kupavskii and Zakharov (Adv.~Math., 2024), obtained the same assertion for $t \leq \tilde{O}(n^{1/3})$. We obtain our result by combining two recently introduced techniques: hypercontractivity of global functions and spreadness.

  • Open Access

    Turán Problems for Expanded Hypergraphs

    by Peter Keevash, Noam Lifshitz, Eoin Long, Dor Minzer

    We obtain new results on the Turán number of any bounded degree uniform hypergraph obtained as the expansion of a hypergraph of bounded uniformity. These are asymptotically sharp over an essentially optimal regime for both the uniformity and the number of edges and solve a number of open problems in Extremal Combinatorics. Firstly, we give general conditions under which the crosscut parameter asymptotically determines the Turán number, thus answering a question of Mubayi and Verstraëte. Secondly, we refine our asymptotic results to obtain several exact results, including proofs of the Huang–Loh–Sudakov conjecture on cross matchings and the Füredi–Jiang–Seiver conjecture on path expansions. We have introduced two major new tools for the proofs of these results. The first of these, Global Hypercontractivity, is used as a ‘black box’ (we present it in a separate paper with several other applications). The second tool, presented in this paper, is a far-reaching extension of the Junta Method, which we develop from a powerful and general technique for finding matchings in hypergraphs under certain pseudorandomness conditions.


  • Open Access

    Improved covering results for conjugacy classes of symmetric groups via hypercontractivity

    by 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 normal sets. We show that for any $\epsilon>0$ , there exists $n_0$ such that if $n>n_0$ and A is a normal subset of the symmetric group $S_n$ of density $\ge e^{-n^{2/5 - \epsilon }}$ , then $A^2 \supseteq A_n$ . This improves upon a seminal result of Larsen and Shalev (Inventiones Math., 2008), with our $2/5$ in the double exponent replacing their $1/4$ . Our proof strategy combines two types of techniques. The first is ‘traditional’ techniques rooted in character bounds and asymptotics for the Witten zeta function, drawing from the foundational works of Liebeck–Shalev, Larsen–Shalev, and more recently, Larsen–Tiep. The second is a sharp hypercontractivity theorem in the symmetric group, which was recently obtained by Keevash and Lifshitz. This synthesis of algebraic and analytic methodologies not only allows us to attain our improved bounds but also provides new insights into the behavior of general independent sets in normal Cayley graphs over symmetric groups.


  • Open Access

    Influences in Mixing Measures

    by Frederic Koehler, Noam Lifshitz, Dor Minzer, Elchanan Mossel

    The theory of influences in product measures has profound applications in theoretical computer science, combinatorics, and discrete probability. This deep theory is intimately connected to functional inequalities and to the Fourier analysis of discrete groups. Originally, influences of functions were motivated by the study of social choice theory, wherein a Boolean function represents a voting scheme, its inputs represent the votes, and its output represents the outcome of the elections. Thus, product measures represent a scenario in which the votes of the parties are randomly and independently distributed, which is often far from the truth in real-life scenarios. We begin to develop the theory of influences for more general measures under mixing or spectral independence conditions. More specifically, we prove analogues of the KKL and Talagrand influence theorems for Markov Random Fields on bounded degree graphs when the Glauber dynamics mix rapidly. We thus resolve a long standing challenge, stated for example by Kalai and Safra (2005). We show how some of the original applications of the theory of in terms of voting and coalitions extend to these general dependent measures. Our results thus shed light both on voting with correlated voters and on the behavior of general functions of Markov Random Fields (also called "spin-systems") where the Glauber dynamics mixes rapidly.


  • Open Access

    Product Mixing in Compact Lie Groups

    by David Ellis, Guy Kindler, Noam Lifshitz, Dor Minzer

    If G is a group, we say a subset S of G is product-free if the equation xy=z has no solutions with x,y,z ∈ S.In 1985, Babai and Sós [] asked, for a finite group G, how large a subset S⊆ G can be if it is product-free. The main tool (hitherto) for studying this problem has been the notion of a quasirandom group. For D ∈ ℕ, a group G is said to be D-quasirandom if the minimal dimension of a nontrivial complex irreducible representation of G is at least D. Gowers showed that in a D-quasirandom finite group G, the maximal size of a product-free set is at most |G|/D1/3. This disproved a longstanding conjecture of Babai and Sós from 1985. For the special unitary group, G=(n), Gowers observed that his argument yields an upper bound of n−1/3 on the measure of a measurable product-free subset. In this paper, we improve Gowers’ upper bound to exp(−cn1/3), where c>0 is an absolute constant. In fact, we establish something stronger, namely, product-mixing for measurable subsets of (n) with measure at least exp(−cn1/3); for this product-mixing result, the n1/3 in the exponent is sharp. Our approach involves introducing novel hypercontractive inequalities, which imply that the non-Abelian Fourier spectrum of the indicator function of a small set concentrates on high-dimensional irreducible representations. Our hypercontractive inequalities are obtained via methods from representation theory, harmonic analysis, random matrix theory and differential geometry. We generalize our hypercontractive inequalities from (n) to an arbitrary D-quasirandom compact connected Lie group for D at least an absolute constant, thereby extending our results on product-free sets to such groups. We also demonstrate various other applications of our inequalities to geometry (viz., non-Abelian Brunn-Minkowski type inequalities), mixing times, and the theory of growth in compact Lie groups. A subsequent work due to Arunachalam, Girish and Lifshitz uses our inequalities to establish new separation results between classical and quantum communication complexity.


  • Open Access

    Stability for the complete intersection theorem, and the forbidden intersection problem of Erdős and Sós

    by David Ellis, Nathan Keller, Noam Lifshitz

    A family \mathcal{F} of sets is said to be t-intersecting if |A \cap B| \geq t for any A,B \in \mathcal{F} . The seminal Complete Intersection Theorem of Ahlswede and Khachatrian (1997) gives the maximal size f(n,k,t) of a t -intersecting family of k -element subsets of [n]=\{1,\ldots,n\} , together with a characterisation of the extremal families, solving a longstanding problem of Frankl. The forbidden intersection problem , posed by Erdős and Sós in 1971, asks for a determination of the maximal size g(n,k,t) of a family \mathcal{F} of k -element subsets of [n] such that |A \cap B| \neq t-1 for any A,B \in \mathcal{F} . In this paper, we show that for any fixed t \in \mathbb{N} , if o(n) \leq k \leq n/2-o(n) , then g(n,k,t)=f(n,k,t) . In combination with prior results, this solves the problem of Erdős and Sós for any constant t , except for the ranges n/2-o(n) < k < n/2+t/2 and k < 2t . One key ingredient of the proof is the following sharp ‘stability’ result for the Complete Intersection Theorem: if k/n is bounded away from 0 and 1/2 , and \mathcal{F} is a t -intersecting family of k -element subsets of [n] such that |\mathcal{F}| \geq f(n,k,t) - O(\binom{n-d}{k}) , then there exists a family \mathcal{G} such that \mathcal{G} is extremal for the Complete Intersection Theorem, and |\mathcal{F} \setminus \mathcal{G}| = O(\binom{n-d}{k-d}) . This proves a conjecture of Friedgut (2008). We prove the result by combining classical ‘shifting’ arguments with a ‘bootstrapping’ method based upon an isoperimetric inequality. Another key ingredient is a ‘weak regularity lemma’ for families of k -element subsets of [n] , where k/n is bounded away from 0 and 1. This states that any such family \mathcal{F} is approximately contained within a ‘junta’ such that the restriction of \mathcal{F} to each subcube determined by the junta is ‘pseudorandom’ in a certain sense.


  • Open Access

    Hypercontractivity on the symmetric group

    by Yuval Filmus, Guy Kindler, Noam Lifshitz, Dor Minzer

    The hypercontractive inequality is a fundamental result in analysis, with many applications throughout discrete mathematics, theoretical computer science, combinatorics and more. So far, variants of this inequality have been proved mainly for product spaces, which raises the question of whether analogous results hold over non-product domains. We consider the symmetric group, $S_n$ , one of the most basic non-product domains, and establish hypercontractive inequalities on it. Our inequalities are most effective for the class of global functions on $S_n$ , which are functions whose $2$ -norm remains small when restricting $O(1)$ coordinates of the input, and assert that low-degree, global functions have small q-norms, for $q>2$ . As applications, we show the following: 1. An analog of the level-d inequality on the hypercube, asserting that the mass of a global function on low degrees is very small. We also show how to use this inequality to bound the size of global, product-free sets in the alternating group $A_n$ . 2. Isoperimetric inequalities on the transposition Cayley graph of $S_n$ for global functions that are analogous to the KKL theorem and to the small-set expansion property in the Boolean hypercube. 3. Hypercontractive inequalities on the multi-slice and stability versions of the Kruskal–Katona Theorem in some regimes of parameters.


  • Open Access

    Improved covering results for conjugacy classes of symmetric groups via hypercontractivity

    by 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$ such that if $n>n_0$ and $A$ is a normal subset of the symmetric group $S_n$ of density $\ge e^{-n^{2/5 - ε}}$, then $A^2 \supseteq A_n$. This improves upon a seminal result of Larsen and Shalev (Inventiones Math., 2008), with our $2/5$ in the double exponent replacing their $1/4$. Our proof strategy combines two types of techniques. The first is `traditional' techniques rooted in character bounds and asymptotics for the Witten zeta function, drawing from the foundational works of Liebeck--Shalev, Larsen--Shalev, and more recently, Larsen--Tiep. The second is a sharp hypercontractivity theorem in the symmetric group, which was recently obtained by Keevash and Lifshitz. This synthesis of algebraic and analytic methodologies not only allows us to attain our improved bounds but also provides new insights into the behavior of general independent sets in normal Cayley graphs over symmetric groups.

  • Open Access

    One Clean Qubit Suffices for Quantum Communication Advantage

    by 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 a quantum protocol of cost $O(\log N)$ in this model, however, every interactive randomized protocol has cost $Ω(\sqrt{N})$, settling a conjecture of Klauck and Lim. In contrast, all prior quantum versus classical communication separations required at least $Ω(\log N)$ clean qubits. The function demonstrating our separation also has an efficient protocol in the quantum-simultaneous-with-entanglement model of cost $O(\log N )$. We thus recover the state-of-the-art separations between quantum and classical communication complexity. Our proof is based on a recent hypercontractivity inequality introduced by Ellis, Kindler, Lifshitz, and Minzer, in conjunction with tools from the representation theory of compact Lie groups.