Let$X$be a d-dimensional simplicial complex. A function$F: X(k)\rightarrow\{0,1\}^{k}$is said to be a direct product function if there exists a function$f: x(1)\rightarrow\{0,1\}$such that$F(\sigma)=(f(\sigma_{1}),\ \ldots,\ f(\sigma_{k}))$for each k-face$\sigma$, In an effort to simplify components of the PCP theorem, Goldreich and Safra [1] introduced the problem of direct product testing, which asks whether one can test if$F: X(k)\rightarrow\{0,1\}^{k}$- is correlated with a direct product function by querying$F$on only 2 inputs. Dinur and Kaufman [2] conjectured that there exist bounded degree complexes with a direct product test in the small soundness regime. We resolve their conjecture by showing that for all$\delta > 0$, there exists a family of high-dimensional expanders with degree$O_{\delta}(1)$and a 2-query direct product tester with soundness$\delta$We use the characterization given by [3] and independently by [4], who showed that some form of non-Abelian coboundary expansion (which they called “Unique-Games coboundary expansion”) is a necessary and sufficient condition for a complex to admit such direct product testers. Our main technical contribution is a general technique for showing coboundary expansion of complexes with coefficients in a non-Abelian group. This allows us to prove that the high dimensional expanders constructed by [5] satisfy the conditions of [3], thus admitting a 2-query direct product tester with small soundness.

The (low soundness) linearity testing problem for the middle slice of the Boolean cube is as follows. Let$\varepsilon > 0$and$f$be a function on the middle slice on the Boolean cube, such that when choosing a uniformly random quadruple$(x,y,\ z,x\oplus y\oplus z)$of vectors of$2n$bits with exactly$n$ones, the probability that$f(x\oplus y\oplus z)=f(x)\oplus f(y)\oplus f(z)$is at least$1/2+\epsilon$. The linearity testing problem, posed by [6], asks whether there must be an actual linear function that agrees with$f$on$1/2+\epsilon^{\prime}$fraction of the inputs, where$\varepsilon^{\prime}=\in^{\prime}(\in) > 0$. We solve this problem, showing that$f$must indeed be correlated with a linear function. To do so, we prove a dense model theorem for the middle slice of the Boolean hypercube for Gowers uniformity norms. Specifically, we show that for every$k\in \mathbb{N}$, the normalized indicator function of the middle slice of the Boolean hypercube$\{0,1\}^{2n}$is close in Gowers norm to the normalized indicator function of the union of all slices with weight$t=n(\text{mod}\ 2^{k-1})$. Using our techniques we also give a more general ‘low degree test’ and a biased rank theorem for the slice.

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.

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.

We prove an analogue of Bonami’s (hypercontractive) lemma for complex-valued functions on L (𝑉 ,𝑊 ), where 𝑉 and 𝑊 are vector spaces over a finite field. This inequality is useful for functions on L (𝑉 ,𝑊 ) whose ‘generalised influences’ are small, in an appropriate sense. It leads to a significant shortening of the proof of a recent seminal result by Khot, Minzer and Safra that pseudorandom sets in Grassmann graphs have near-perfect expansion, which (in combination with the work of Dinur, Khot, Kindler, Minzer and Safra) implies the 2-2 Games conjecture (the variant, that is, with imperfect completeness)

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 are effective for global functions, which are functions that are not significantly affected by a restriction of a small set of coordinates. As applications, we obtain Fourier concentration, small-set expansion, and Kruskal–Katona theorems for high dimensional expanders. Our techniques rely on a new approximate Efron–Stein decomposition for high dimensional link expanders.

Given an alphabet size$m\in\mathbb{N}$thought of as a constant, and$\vec{k}=(k_{1}, \ldots, k_{m})$whose entries sum of up$n$, the$\vec{k}$-multi-slice is the set of vectors$x\in[m]^{n}$in which each symbol$i\in[m]$appears precisely$k_{i}$times. We show an invariance principle for low-degree functions over the multi-slice, to functions over the product space ($[m]^{n}, \mu^{n}$) in which$\mu(i)=k_{i}/n$. This answers a question raised by [21]. As applications of the invariance principle, we show: 1)An analogue of the “dictatorship test implies computational hardness” paradigm for problems with perfect completeness, for a certain class of dictatorship tests. Our computational hardness is proved assuming a recent strengthening of the Unique-Games Conjecture, called the Rich 2-to-1 Games Conjecture. Using this analogue, we show that assuming the Rich 2-to-1 Games Conjecture, (a) there is an$r$-ary CSP$\mathcal{P}_{r}$for which it is NP-hard to distinguish satisfiable instances of the CSP and instances that are at most$\frac{2r+1}{2^{r}}+o(1)$satisfiable, and (b) hardness of distinguishing 3-colorable graphs, and graphs that do not contain an independent set of size$o(1)$. 2)A reduction of the problem of studying expectations of products of functions on the multi-slice to studying expectations of products of functions on correlated, product spaces. In particular, we are able to deduce analogues of the Gaussian bounds from [38] for the multi-slice. 3)In a companion paper, we show further applications of our invariance principle in extremal combinatorics, and more specifically to proving removal lemmas of a wide family of hypergraphs$H$called$\zeta$-forests, which is a natural extension of the well-studied case of matchings.

We extend the definitions of complexity measures of functions to domains such as the symmetric group. The complexity measures we consider include degree, approximate degree, decision tree complexity, sensitivity, block sensitivity, and a few others. We show that these complexity measures are polynomially related for the symmetric group and for many other domains. To show that all measures but sensitivity are polynomially related, we generalize classical arguments of Nisan and others. To add sensitivity to the mix, we reduce to Huang’s sensitivity theorem using "pseudo-characters", which witness the degree of a function. Using similar ideas, we extend the characterization of Boolean degree 1 functions on the symmetric group due to Ellis, Friedgut and Pilpel to the perfect matching scheme. As another application of our ideas, we simplify the characterization of maximum-size t-intersecting families in the symmetric group and the perfect matching scheme.

A function f∶{0,1} n → {0,1} is called an approximate AND-homomorphism if choosing x,y∈n uniformly at random, we have that f(x∧ y) = f(x)∧ f(y) with probability at least 1−ε, where x∧ y = (x 1∧ y 1,…,x n ∧ y n ). We prove that if f∶ {0,1} n → {0,1} is an approximate AND-homomorphism, then f is δ-close to either a constant function or an AND function, where δ(ε) → 0 as ε→ 0. This improves on a result of Nehama, who proved a similar statement in which δ depends on n.

The noise sensitivity of a Boolean function measures how susceptible the value of f on a typical input x to a slight perturbation of the bits of x: it is the probability f(x) and f(y) are different when x is a uniformly chosen n-bit Boolean string, and y is formed by flipping each bit of x with small probability ε. The noise sensitivity of a function is a key concept with applications to combinatorics, complexity theory, learning theory, percolation theory and more. In this paper, we investigate noise sensitivity on the p-biased hypercube, extending the theory for polynomially small p. Specifically, we give sufficient conditions for monotone functions with large groups of symmetries to be noise sensitive (which in some cases are also necessary). As an application, we show that the 2-SAT function is noise sensitive around its critical probability. En route, we study biased versions of the invariance principle for monotone functions and give p-biased versions of Bourgain's tail theorem and the Majority is Stablest theorem, showing that in this case the correct analog of ``small low degree influences'' is lack of correlation with constant width DNF formulas.

A family ${\cal F}$ of graphs on a fixed set of $n$ vertices is called triangle-intersecting if for any $G_1,G_2 \in {\cal F}$, the intersection $G_1 \cap G_2$ contains a triangle. More generally, for a fixed graph $H$, a family ${\cal F}$ is $H$-intersecting if the intersection of any two graphs in ${\cal F}$ contains a subgraph isomorphic to $H$. In [D. Ellis, Y. Filmus, and E. Friedgut, J. Eur. Math. Soc., 14 (2012), pp. 841--885], a 36-year old conjecture of Simonovits and Sós was proved stating that the maximal size of a triangle-intersecting family is $(1/8)2^{n(n-1)/2}$. Furthermore, they proved a $p$-biased generalization, stating that for any $p \leq 1/2$, we have $\mu_{p}\left({\cal F}\right)\le p^{3}$, where $\mu_{p}\left({\cal F}\right)$ is the probability that the random graph $G\left(n,p\right)$ belongs to ${\cal F}$. In the same paper, the authors conjectured that the assertion of their biased theorem holds also for $1/2 < p \le 3/4$, and more generally, that for any non-$t$-colorable graph $H$ and any $H$-intersecting family ${\cal F}$, we have $\mu_{p}\left({\cal F}\right)\le p^{t(t+1)/2}$ for all $p \leq (2t-1)/(2t)$. In this note we construct, for any fixed $H$ and any $p>1/2$, an $H$-intersecting family ${\cal F}$ of graphs such that $\mu_{p}\left({\cal F}\right)\ge 1-e^{-n^{2}/C}$, where $C$ depends only on $H$ and $p$, thus disproving both conjectures.