Noam Lifshitz
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
Research Subjects
Research Interests
Noam Lifshitz has a total of 19 co-authors. Here are the top co-authors by number of shared publications:
- Dor Minzer
Massachusetts Institute of Technology, Cambridge, USA
8 shared publications - Nathan Keller
Department of Mathematics Bar Ilan University Ramat Gan Israel
8 shared publications - David Ellis
School of Mathematics University of Bristol Bristol UK
7 shared publications - Nathan Keller
Department of Mathematics, Bar Ilan University, Ramat Gan, Israel
6 shared publications - Ohad Sheinfeld
Department of Mathematics, Bar-Ilan University
4 shared publications - Boaz Tsaban
Department of Mathematics, Bar-Ilan University, Ramat Gan, Israel
2 shared publications
Latest Publications
- Top Cited Papers
- 9 January 2026
- Published by European Mathematical Society - EMS - Publishing House GmbH in Journal of the European Mathematical Society
Sharp hypercontractivity for global functions
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.
- 9 January 2026
- Published by European Mathematical Society - EMS - Publishing House GmbH in Journal of the European Mathematical Society
Top Cited PapersSharp hypercontractivity for global functions
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
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 AccessThe Forbidden Cross Intersection Problem for Permutations
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
- 23 April 2025
- Published by Springer Nature in Combinatorica
- Vol. 45 (3) , 1-36
Turán Problems for Expanded Hypergraphs
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.
- 23 April 2025
- Published by Springer Nature in Combinatorica
- Vol. 45 (3) , 1-36
Open AccessTurán Problems for Expanded Hypergraphs
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
- 21 October 2024
- Published by Cambridge University Press (CUP) in Forum of Mathematics, Sigma
- Vol. 12, e85
Improved covering results for conjugacy classes of symmetric groups via hypercontractivity
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.- 21 October 2024
- Published by Cambridge University Press (CUP) in Forum of Mathematics, Sigma
- Vol. 12, e85
Open AccessImproved covering results for conjugacy classes of symmetric groups via hypercontractivity
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
- 10 June 2024
- Published by Association for Computing Machinery (ACM)
- p. 527-536
Influences in Mixing Measures
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.
- 10 June 2024
- Published by Association for Computing Machinery (ACM)
- p. 527-536
Open AccessInfluences in Mixing Measures
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
- 10 June 2024
- Published by Association for Computing Machinery (ACM)
- p. 1415-1422
Product Mixing in Compact Lie Groups
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.
- 10 June 2024
- Published by Association for Computing Machinery (ACM)
- p. 1415-1422
Open AccessProduct Mixing in Compact Lie Groups
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
- 21 February 2024
- Published by European Mathematical Society - EMS - Publishing House GmbH in Journal of the European Mathematical Society
- Vol. 26 (5) , 1611-1654
Stability for the complete intersection theorem, and the forbidden intersection problem of Erdős and Sós
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.
- 21 February 2024
- Published by European Mathematical Society - EMS - Publishing House GmbH in Journal of the European Mathematical Society
- Vol. 26 (5) , 1611-1654
Open AccessStability for the complete intersection theorem, and the forbidden intersection problem of Erdős and Sós
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
- 8 January 2024
- Published by Cambridge University Press (CUP) in Forum of Mathematics, Sigma
- Vol. 12
Hypercontractivity on the symmetric group
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.- 8 January 2024
- Published by Cambridge University Press (CUP) in Forum of Mathematics, Sigma
- Vol. 12
Open AccessHypercontractivity on the symmetric group
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
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 AccessImproved covering results for conjugacy classes of symmetric groups via hypercontractivity
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
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.Open AccessOne Clean Qubit Suffices for Quantum Communication Advantage
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.