Let G be a k-player game with value <1, whose query distribution is such that no marginal on k-1 players admits a non-trivial Abelian embedding. We show that for every n>=N, the value of the n-fold parallel repetition of G is val(G^n) <= 1/(log log ... log n), where the number of logarithms is C, and N=N(G) and 1 <= C <= k^(O(k)) are constants. As a consequence, we obtain a parallel repetition theorem for all 3-player games whose query distribution is pairwise-connected. Prior to our work, only inverse Ackermann decay bounds were known for such games.

In a constraint satisfaction problem (CSP) in the single-pass streaming model, an algorithm is given the constraints C1,…,Cm of an instance one after another (in some fixed order), and its goal is to approximate the value of the instance, i.e., the maximum fraction of constraints that can be satisfied simultaneously. In the p-pass streaming model the algorithm is given p passes over the input stream (in the same order), after which it is required to output an approximation of the value of the instance. We show a dichotomy result for p-pass streaming algorithms for all CSPs and for up to polynomially many passes. More precisely, we prove that for any arity parameter k, finite alphabet Σ, collection F of k-ary predicates over Σ and any c∈ (0,1), there exists 0

We construct $3$-query relaxed locally decodable codes (RLDCs) with constant alphabet size and length $\tilde{O}(k^2)$ for $k$-bit messages. Combined with the lower bound of $\tildeΩ(k^3)$ of [Alrabiah, Guruswami, Kothari, Manohar, STOC 2023] on the length of locally decodable codes (LDCs) with the same parameters, we obtain a separation between RLDCs and LDCs, resolving an open problem of [Ben-Sasson, Goldreich, Harsha, Sudan and Vadhan, SICOMP 2006]. Our RLDC construction relies on two components. First, we give a new construction of probabilistically checkable proofs of proximity (PCPPs) with $3$ queries, quasi-linear size, constant alphabet size, perfect completeness, and small soundness error. This improves upon all previous PCPP constructions, which either had a much higher query complexity or soundness close to $1$. Second, we give a query-preserving transformation from PCPPs to RLDCs. At the heart of our PCPP construction is a $2$-query decodable PCP (dPCP) with matching parameters, and our construction builds on the HDX-based PCP of [Bafna, Minzer, Vyas, Yun, STOC 2025] and on the efficient composition framework of [Moshkovitz, Raz, JACM 2010] and [Dinur, Harsha, SICOMP 2013]. More specifically, we first show how to use the HDX-based construction to get a dPCP with matching parameters but a large alphabet size, and then prove an appropriate composition theorem (and related transformations) to reduce the alphabet size in dPCPs.

We show that for every k∈ℕ and ε>0, for large enough alphabet R, given a k-CSP with alphabet size R, it is NP-hard to distinguish between the case that there is an assignment satisfying at least 1−ε fraction of the constraints, and the case no assignment satisfies more than 1/Rk−1−ε of the constraints. This result improves upon prior work of [Chan, Journal of the ACM 2016], who showed the same result with weaker soundness of O(k/Rk−2), and nearly matches the trivial approximation algorithm that finds an assignment satisfying at least 1/Rk−1 fraction of the constraints. Our proof follows the approach of a recent work [Minzer and Zheng, STOC 2024] of the authors, wherein the above result is proved for k=2. Our main new ingredient is a counting lemma for hyperedges between pseudo-random sets in the Grassmann graphs, which may be of independent interest.

Abstract. We show that the value of the [Formula: see text]-fold repeated GHZ game is at most [Formula: see text], improving upon the polynomial bound established by Holmgren and Raz. Our result is established via a reduction to approximate subgroup-type questions from additive combinatorics.

The problem of studying k-wise correlations in product spaces, i.e., correlations of the form ${\mathbb{E}_{\left( {{x_1}, \ldots ,{x_k}} \right)\sim \mu \otimes n}}\left[ {{f_1}\left( {{x_1}} \right) \cdots f\left( {{x_k}} \right)} \right]$ where ${\text{ }}{f_i}:\sum\nolimits_i^n \to \mathbb{C}$ are all 1-bounded functions and µ is a distribution over Σ1× … × Σk, appears in many different contexts throughout discrete mathematics. Examples include additive combinatorics, extremal combinatorics, hardness of approximation and probability. The goal in an inverse theorem is to characterize the type of functions f1,…,fkthat achieve non-trivial correlations, under minimal assumptions on the distribution µ.We give new inverse theorems for k-wise correlations for all k ⩾ 3. For k = 3, our inverse theorem works for any distribution µ which is pairwise-connected, which is essentially the minimal assumption required for a nontrivial inverse theorem to hold. For k > 3, our inverse theorem applies for distributions µ satisfying the stronger condition of not having any Abelian embeddings. This resolves a conjecture from [Bhangale-Khot-Minzer, STOC 2022].We give applications of our inverse theorems to additive combinatorics, hardness of approximation, and property testing. First, we show that there exists c > 0 such that any set A ⊆ {0,1,2}nwith density at least Ω((loglogloglogn)−c) must contain a combinatorial line, i.e., x,y,z ∈ {0,1,2}n, not all equal, such that xi= yi= zior (xi,yi,zi) = (0,1,2) for all i = 1,2,…,n. In other words, we give "reasonable bounds" for the density Hales-Jewett theorem of length 3. This involves combining our inverse theorems with several additional insights, motivated by Shkredov’s proof of the corners theorem and Polymath’s combinatorial proof of the density Hales-Jewett theorem. Second, we show how to construct a dictatorship vs quasi-random test that has perfect completeness and soundness s + ε from integrality gap instances with similar parameters, provided that its local distributions have no Abelian embeddings. Third, we analyze the direct-sum tester of [Dinur-Golubev, RANDOM 2019] in the low-soundness regime.

In the Max-Cut problem in the streaming model, an algorithm is given the edges of an unknown graph $G=(V, E)$ in some fixed order, and its goal is to approximate the size of the largest cut in G. Improving upon an earlier result of Kapralov, Khanna and Sudan, it was shown by Kapralov and Krachun that for all $\varepsilon\gt 0$, no $o(n)$ memory streaming algorithm can achieve a $(1 / 2+\varepsilon)$-approximation for Max-Cut. Their result holds for single-pass streams, i.e. the setting in which the algorithm only views the stream once, and it was open whether multi-pass access may help. The state-of-the-art result along these lines, due to Assadi and N, rules out arbitrarily good approximation algorithms with constantly many passes and $n^{1-\delta}$ space for any $\delta\gt 0$. We improve upon this state-of-the-art result, showing that any non-trivial approximation algorithm for Max-Cut requires either polynomially many passes or polynomially large space. More specifically, we show that for all $\varepsilon\gt 0$, a k-pass streaming $(1 / 2+\varepsilon)$-approximation algorithm for Max-Cut requires $\Omega_{\varepsilon}\left(n^{1 / 3} / k\right)$ space. This result leads to a similar lower bound for the Maximum Directed Cut problem, showing the near optimality of the algorithm of [Saxena, Singer, Sudan, Velusamy, SODA 2025]. Our lower bounds proceed by showing a communication complexity lower bound for the Distributional Implicit Hidden Partition (DIHP) Problem, introduced by Kapralov and Krachun. While a naive application of the discrepancy method fails, we identify a property of protocols called “globalness”, and show that (1) any protocol for DIHP can be turned into a global protocol, (2) the discrepancy of a global protocol must be small. The second step is the more technically involved step in the argument, and therein we use global hypercontractive inequalities, and more specifically strong quantitative versions of the level- d inequality for global functions.

We give an IOPP (interactive oracle proof of proximity) for trivariate Reed-Muller codes that achieves the best known query complexity in some range of security parameters. Specifically, for degree d and security parameter $\lambda \leq \frac{\log ^{2} d}{\log \log d}$, our IOPP has $2^{-\lambda}$ round-byround soundness, $O(\lambda)$ queries, $O(\log \log d)$ rounds and $O(d)$ length. This improves upon the FRI [Ben-Sasson, Bentov, Horesh, Riabzev, ICALP 2018] and the STIR [Arnon, Chiesa, Fenzi, Yogev, Crypto 2024] IOPPs for Reed-Solomon codes, that have larger query and round complexity standing at $O(\lambda \log d)$ and $O(\log d+\lambda \log \log d)$ respectively. We use our IOPP to give an IOP for the NPcomplete language R1CS with the same parameters. Our construction is based on the line versus point test in the low-soundness regime. Compared to the axis parallel test (which is used in all prior works), the general affine lines test has improved soundness, which is the main source of our improved soundness. Using this test involves several complications, most significantly that projection to affine lines does not preserve individual degrees, and we show how to overcome these difficulties. En route, we extend some existing machinery to more general settings. Specifically, we give proximity generators for Reed-Muller codes, show a more systematic way of handling “side conditions” in IOP constructions, and generalize the compiling procedure of [Arnon, Chiesa, Fenzi, Yogev, Crypto 2024] to general codes.

Mitali Bafna, Karthik C. S., and Dor Minzer. 2025. Near Optimal Constant Inapproximability under ETH for Fundamental Problems in Parameterized Complexity. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC '25). Association for Computing Machinery, New York, NY, USA, 2118–2129.

STOC ’25, Prague, Czechia

Abstract We consider the $$P$$ P -CSP problem for 3-ary predicates $$P$$ P on satisfiable instances. We show that under certain conditions on $$P$$ P and a $$(1,s)$$ ( 1 , s ) integrality gap instance of the $$P$$ P -CSP problem, it can be translated into a dictatorship vs. quasirandomness test with perfect completeness and soundness $$s+\epsilon$$ s + ϵ , for every constant $$\epsilon>0$$ ϵ > 0 . Compared to Ragahvendra (in: Proceedings of the fortieth annual ACM symposium on theory of computing (STOC), pp 245–254, 2008), we do not lose perfect completeness. This is particularly interesting as this test implies new hardness results on satisfiable constraint satisfaction problems, assuming the Rich 2-to-1 Games Conjecture by Braverman et al. (in: Lee JR (ed) Volume 185 of Leibniz international proceedings in informatics (LIPIcs), 27:1–27:20. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, 2021b. https://drops.dagstuhl.de/opus/volltexte/2021/13566 ).Our result can be seen as the first step of a potentially long-term challenging program of characterizing optimal inapproximability of every satisfiable $$k$$ k -ary CSP. At the heart of the reduction is our main analytical lemma for a class of 3-ary predicates, which is a generalization of a lemma by Mossel (Geom Funct Anal 19(6):1713–1756, 2010). The lemma and a further generalization of it that we conjecture may be of independent interest.

Abstract. The problem of testing low-degree polynomials has received significant attention over the years due to its importance in theoretical computer science. The problem is specified by three parameters, the field size [Formula: see text], the degree [Formula: see text], and the proximity parameter [Formula: see text], and the goal is to design a test that makes as few queries as possible to a given function and distinguishes between the case the function has degree at most [Formula: see text] and the case it is [Formula: see text]-far from any degree [Formula: see text] function. We say that a test is optimal if it makes [Formula: see text] queries and rejects any function which is [Formula: see text]-far from degree [Formula: see text] with probability [Formula: see text]. The most natural tester to consider is the [Formula: see text]-flat test, wherein one picks an affine subspace [Formula: see text] of dimension [Formula: see text] (chosen appropriately) uniformly at random, and checks that [Formula: see text]. The [Formula: see text]-flat test was shown to be optimal by Bhattacharyya et al. [ Proceedings of FOCS, 2010, pp. 488–497] for [Formula: see text], and later by Haramaty, Shpilka, and Sudan [ SIAM J. Comput., 42 (2013), pp. 536–562] for all prime powers [Formula: see text]. Their analyses, however, has a tower type dependency on the field size [Formula: see text] (i.e., in the hidden constant in the big [Formula: see text] notation). We improve the result of Haramaty, Shpilka, and Sudan, showing that the dependency on the field size is polynomial in [Formula: see text]. Our technique also applies in the more general setting of lifted affine invariant codes and gives the same polynomial dependency on the field size. This answers a problem raised by Haramaty, Ron-Zewi, and Sudan [ Theory Comput., 11 (2015), pp. 299–338]. Our approach significantly deviates from the strategy taken in earlier works and is based on studying the structure of the collection of erroneous subspaces, i.e., subspaces [Formula: see text] such that [Formula: see text] has degree greater than [Formula: see text]. Toward this end, we observe that these sets are poorly expanding in the affine Grassmann graph and use that to establish structural results on them via global hypercontractivity. We then use this structure to perform local correction on [Formula: see text].

We study the complexity of affine Unique-Games (UG) over globally hypercontractive graphs, which are graphs that are not small set expanders but admit a useful and succinct characterization of all small sets that violate the small-set expansion property. This class of graphs includes the Johnson and Grassmann graphs, which have played a pivotal role in recent PCP constructions for UG, and their generalizations via high-dimensional expanders. We show new rounding techniques for higher degree sum-of-squares (SoS) relaxations for worst-case optimization. In particular, our algorithm shows how to round "low-entropy" pseudodistributions, broadly extending the algorithmic framework of [Mitali Bafna et al., 2021]. At a high level, [Mitali Bafna et al., 2021] showed how to round pseudodistributions for problems where there is a "unique" good solution. We extend their framework by exhibiting a rounding for problems where there might be "few good solutions". Our result suggests that UG is easy on globally hypercontractive graphs, and therefore highlights the importance of graphs that lack such a characterization in the context of PCP reductions for UG.

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.

In the t-online-erasure model in property testing, an adversary is allowed to erase t values of a queried function for each query the tester makes. This model was recently formulated by Kalemaj, Raskhodnikova and Varma, who showed that the properties of linearity of functions as well as quadraticity can be tested in Ot (1) many queries: O(log(t)) for linearity and 22O(t) for quadraticity. They asked whether the more general property of low-degreeness can be tested in the online erasure model, whether better testers exist for quadraticity, and if similar results hold when “erasures” are replaced with “corruptions”.

A d-dimensional simplicial complex X is said to support a direct product tester if any locally consistent function defined on its k-faces (where k≪ d) necessarily come from a function over its vertices. More precisely, a direct product tester has a distribution µ over pairs of k-faces (A,A′), and given query access to F: X(k)→{0,1}k it samples (A,A′)∼ µ and checks that F[A]|A∩ A′ = F[A′]|A∩ A′. The tester should have (1) the ”completeness property”, meaning that any assignment F which is a direct product assignment passes the test with probability 1, and (2) the ”soundness property”, meaning that if F passes the test with probability s, then F must be correlated with a direct product function. Dinur and Kaufman showed that a sufficiently good spectral expanding complex X admits a direct product tester in the ”high soundness” regime where s is close to 1. They asked whether there are high dimensional expanders that support direct product tests in the ”low soundness”, when s is close to 0. We give a characterization of high-dimensional expanders that support a direct product tester in the low soundness regime. We show that spectral expansion is insufficient, and the complex must additionally satisfy a variant of coboundary expansion, which we refer to as ”Unique-Games coboundary expanders”. Conversely, we show that this property is also sufficient to get direct product testers. This property can be seen as a high-dimensional generalization of the standard notion of coboundary expansion over non-Abelian groups for 2-dimensional complexes. It asserts that any locally consistent Unique-Games instance obtained using the low-level faces of the complex, must admit a good global solution.

We prove a stability result for general 3-wise correlations over distributions satisfying mild connectivity properties. More concretely, we show that if Σ,Γ and Φ are alphabets of constant size, and µ is a distribution over Σ×Γ×Φ satisfying: (1) the probability of each atom is at least Ω(1), (2) µ is pairwise connected, and (3) µ has no Abelian embeddings into (ℤ,+), then the following holds. Any triplets of 1-bounded functions f∶ Σn→ℂ, g∶ Γn→ℂ, h∶ Φn→ℂ satisfying

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 show that for all є>0, for sufficiently large prime power q, for all δ>0, it is NP-hard to distinguish whether a 2-Prover-1-Round projection game with alphabet size q has value at least 1-δ, or value at most 1/q^(1-є). This establishes a nearly optimal alphabet-to-soundness tradeoff for 2-query PCPs with alphabet size q, improving upon a result of [Chan 2016]. Our result has the following implications:

We show that the value of the n-fold repeated GHZ game is at most $2^{-\Omega(n)}$, improving upon the polynomial bound established by Holmgren and Raz. Our result is established via a reduction to approximate subgroup type questions from additive combinatorics.

A local tester for an error correcting code $C\subseteq\Sigma^{n}$ is a tester that makes Q oracle queries to a given word $w\in\bar{\Sigma}^{n}$ and decides to accept or reject the word w. An optimal local tester is a local tester that has the additional properties of completeness and optimal soundness. By completeness, we mean that the tester must accept with probability 1 if $w\in C$. By optimal soundness, we mean that if the tester accepts with probability at least $ 1-\varepsilon$ (where $\varepsilon$ is small), then it must be the case that w is $O(\varepsilon/Q)$-close to some codeword $c\in C$ in Hamming distance. We show that Generalized Reed-Muller codes admit optimal testers with $Q=(C_{p}q)^{\lceil\frac{d+1}{q-1}\rceil+O(1)}$ queries for $C_{p}=(2p-1)^{\frac{1}{p-1}}$. Here, for a prime power $q=p^{k}$, the Generalized Reed-Muller code, $\operatorname{RM}[n, q, d]$, consists of the evaluations of all n-variate degree d polynomials over $\mathbb{F}_{q}$. As $p,q$, and d go to infinity, Q matches the known lower bound of $q^{\frac{d+1}{q-1}}$ up to a multiplicative factor of 1. Previously, no tester achieving this query complexity was known, and the best known testers due to Haramaty, Shpilka and Sudan [21] (which is optimal) and due to Ron-Zewi and Sudan [33](which was not known to be optimal) both required $q^{\lceil\frac{d+1}{q-q/p}\rceil}$ queries. Our tester achieves query complexity which is polynomially better than by a power of $p/(p-1)$, which is nearly the best query complexity possible for generalized Reed-Muller codes. The tester we analyze is constructed using the same framework of Ron-Zewi and Sudan, and in fact our analysis shows that their tester is optimal as well. More generally, our methods allow us to prove that a wide class of testers, which follow the form of the Ron-Zewi and Sudan tester, are optimal. This result applies to testers for all affine-invariant codes (which are not necessarily generalized Reed-Muller codes).

A regular graph G = (V,E) is an (ε,γ) small-set expander if for any set of vertices of fractional size at most ε, at least γ of the edges that are adjacent to it go outside. In this paper, we give a unified approach to several known complexity-theoretic results on small-set expanders. In particular, we show: 1) Max-Cut: we show that if a regular graph G = (V,E) is an (ε,γ) small-set expander that contains a cut of fractional size at least 1-δ, then one can find in G a cut of fractional size at least 1-O(δ/(εγ⁶)) in polynomial time. 2) Improved spectral partitioning, Cheeger’s inequality and the parallel repetition theorem over small-set expanders. The general form of each one of these results involves square-root loss that comes from certain rounding procedure, and we show how this can be avoided over small set expanders. Our main idea is to project a high dimensional vector solution into a low-dimensional space while roughly maintaining 𝓁₂² distances, and then perform a pre-processing step using low-dimensional geometry and the properties of 𝓁₂² distances over it. This pre-processing leverages the small-set expansion property of the graph to transform a vector valued solution to a different vector valued solution with additional structural properties, which give rise to more efficient integral-solution rounding schemes.

The Cube versus Cube test is a variant of the well-known Plane versus Plane test of Raz and Safra [10], in which to each 3-dimensional affine subspace C of 𝔽 n q , a polynomial of degree at most d , T ( C ), is assigned in a somewhat locally consistent manner: taking two cubes C 1 , C 2 that intersect in a plane uniformly at random, the probability that T ( C 1 ) and T ( C 2 ) agree on C 1 ∩ C 2 is at least some ε. An element of interest is the soundness threshold of this test, i.e. the smallest value of ε, such that this amount of local consistency implies a global structure; namely, that there is a global degree d function g such that g| C = T (C) for at least Ω(ε) fraction of the cubes. We show that the cube versus cube low degree test has soundness poly( d )/ q . This result achieves the optimal dependence on q for soundness in low degree testing and improves upon previous soundness results of poly( d )/ q 1/2 due to Bhangale, Dinur and Navon [4].

Let Σ be an alphabet and µ be a distribution on Σk for some k ≥ 2. Let α > 0 be the minimum probability of a tuple in the support of µ (denoted supp(µ)). Here, the support of µ is the set of all tuples in Σk that have a positive probability mass under µ. We treat the parameters Σ, k, µ, α as fixed and constant.

In this paper we study functions on the Boolean hypercube that have the property that after applying certain random restrictions, the restricted function is correlated to a linear function with non-negligible probability. If the given function is correlated with a linear function then this property clearly holds. Furthermore, the property also holds for low-degree functions as low-degree functions become a constant function under a random restriction with a non-negligible probability. We show that this essentially is the only possible reason. More specifically, we show that the function must be correlated to a product of a linear function and a low-degree function. One of the main motivations of studying this question comes from the recent work of the authors towards understanding approximability of satisfiable Constraint Satisfaction Problems.

The problem of testing low-degree polynomials has received significant attention over the years due to its importance in theoretical computer science, and in particular in complexity theory. The problem is specified by three parameters: field size q, degree d and proximity parameter δ, and the goal is to design a tester making as few as possible queries to a given function, which is able to distinguish between the case the given function has degree at most d, and the case the given function is δ-far from any degree d function. With respect to these parameters, we say that a tester is optimal if it makes $O(q^{t}+1/\delta)$ queries, where $t=t(d,q)$ is the testing dimension of d, q (defined as the minimum integer so that for all $g:\mathbb{F}_{q}^{n}\rightarrow\mathbb{F}_{q}$ of degree more than d, there is a subspace of dimension t on which their restriction has degree exceeding d). For the field of size q, such tester was first given by Bhattacharyya et al. for q = 2, and later by Haramaty et al. [7] for all prime powers q. In fact, they showed that the natural t-flat tester is an optimal tester for the Reed-Muller code, for an appropriate t. Here, the t-flat tester is the tester that picks a uniformly random affine subspace A of dimension t, and checks that $\operatorname{deg}(f|_{A})\leqslant d$. Their analysis proves that the dependency of the t-flat tester on δ and d is optimal, however the dependency on the field size, i.e. the hidden constant in the O, is a tower-type function in q. We improve the result of Haramaty et al., showing that the dependency on the field size is polynomial. Our technique also applies in the more general setting of lifted affine invariant codes, and gives the same polynomial dependency on the field size. This answers a problem raised in [6]. Our approach significantly deviates from the strategy taken in earlier works [2], [7], [6], and is based on studying the structure of the collection of erroneous subspaces, i.e. subspaces A such that f|A has degree greater than d. Towards this end, we observe that these sets are poorly expanding in the affine version of the Grassmann graph and use that to establish structural results on them via global hypercontractivity. We then use this structure to perform local correction on f.

Cohen, Peri and Ta-Shma [Gil Cohen et al., 2021] considered the following question: Assume the vertices of an expander graph are labelled by ± 1. What "test" functions f : {±1}^t → {±1} can or cannot distinguish t independent samples from those obtained by a random walk? [Gil Cohen et al., 2021] considered only balanced labellings, and proved that for all symmetric functions the distinguishability goes down to zero with the spectral gap λ of the expander G. In addition, [Gil Cohen et al., 2021] show that functions computable by AC⁰ circuits are fooled by expanders with vanishing spectral expansion. We continue the study of this question. We generalize the result to all labelling, not merely balanced ones. We also improve the upper bound on the error of symmetric functions. More importantly, we give a matching lower bound and show a symmetric function with distinguishability going down to zero with λ but not with t. Moreover, we prove a lower bound on the error of functions in AC⁰ in particular, we prove that a random walk on expanders with constant spectral gap does not fool AC⁰.

We consider the P-CSP problem for 3-ary predicates P on satisfiable instances. We show that under certain conditions on P and a (1,s) integrality gap instance of the P-CSP problem, it can be translated into a dictatorship vs. quasirandomness test with perfect completeness and soundness s+ε, for every constant ε>0. Compared to Ragahvendra’s result [STOC, 2008], we do not lose perfect completeness. This is particularly interesting as this test implies new hardness results on satisfiable constraint satisfaction problems, assuming the Rich 2-to-1 Games Conjecture by Braverman, Khot, and Minzer [ITCS, 2021]. Our result can be seen as the first step of a potentially long-term challenging program of characterizing optimal inapproximability of every satisfiable k-ary CSP.

For a function g∶{0,1}m→{0,1}, a function f∶ {0,1}n→{0,1} is called a g-polymorphism if their actions commute: f(g(row1(Z)),…,g(rown(Z))) = g(f(col1(Z)),…,f(colm(Z))) for all Z∈{0,1}n× m. The function f is called an approximate g-polymorphism if this equality holds with probability close to 1, when Z is sampled uniformly. A pair of functions f0,f1∶ {0,1}n → {0,1} are called a skew g-polymorphism if f0(g(row1(Z)),…,g(rown(Z))) = g(f1(col1(Z)),…,f1(colm(Z))) for all Z∈{0,1}n× m.

What is the least surface area of a symmetric body $B$ whose $\mathbb{Z}^n$ translations tile $\mathbb{R}^n$? Since any such body must have volume $1$, the isoperimetric inequality implies that its surface area must be at least $Ω(\sqrt{n})$. Remarkably, Kindler et al.\ showed that for general bodies $B$ this is tight, i.e.\ that there is a tiling body of $\mathbb{R}^n$ whose surface area is $O(\sqrt{n})$. In theoretical computer science, the tiling problem is intimately to the study of parallel repetition theorems (which are an important component in PCPs), and more specifically in the question of whether a "strong version" of the parallel repetition theorem holds. Raz showed, using the odd cycle game, that strong parallel repetition fails in general, and subsequently these ideas were used in order to construct non-trivial tilings of $\mathbb{R}^n$. In this paper, motivated by the study of a symmetric parallel repetition, we consider the symmetric variant of the tiling problem in $\mathbb{R}^n$. We show that any symmetric body that tiles $\mathbb{R}^n$ must have surface area at least $Ω(n/\sqrt{\log n})$, and that this bound is tight, i.e.\ that there is a symmetric tiling body of $\mathbb{R}^n$ with surface area $O(n/\sqrt{\log n})$. We also give matching bounds for the value of the symmetric parallel repetition of Raz's odd cycle game. Our result suggests that while strong parallel repetition fails in general, there may be important special cases where it still applies.

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 propose a variant of the 2-to-1 Games Conjecture that we call the Rich 2-to-1 Games Conjecture and show that it is equivalent to the Unique Games Conjecture. We are motivated by two considerations. Firstly, in light of the recent proof of the 2-to-1 Games Conjecture [Subhash Khot et al., 2017; Irit Dinur et al., 2018; Irit Dinur et al., 2018; Subhash Khot et al., 2018], we hope to understand how one might make further progress towards a proof of the Unique Games Conjecture. Secondly, the new variant along with perfect completeness in addition, might imply hardness of approximation results that necessarily require perfect completeness and (hence) are not implied by the Unique Games Conjecture.

We give alternate proofs for three related results in analysis of Boolean functions, namely the KKL Theorem, Friedgut’s Junta Theorem, and Talagrand’s strengthening of the KKL Theorem. We follow a new approach: looking at the first Fourier level of the function after a suitable random restriction and applying the Log-Sobolev inequality appropriately. In particular, we avoid using the hypercontractive inequality that is common to the original proofs. Our proofs might serve as an alternate, uniform exposition to these theorems and the techniques might benefit further research.

We obtain new separation results for the two-party external information complexity of Boolean functions. The external information complexity of a function f(x,y) is the minimum amount of information a two-party protocol computing f must reveal to an outside observer about the input. We prove an exponential separation between external and internal information complexity, which is the best possible; previously no separation was known. We use this result in order to then prove a near-quadratic separation between amortized zero-error communication complexity and external information complexity for total functions, disproving a conjecture of the first author. Finally, we prove a matching upper bound showing that our separation result is tight.

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.

In the distributed uniformity testing problem, k servers draw samples from some unknown distribution, and the goal is to determine whether the unknown distribution is uniform or whether it is ε-far from uniform, where ε is a proximity parameter. Each server decides whether to accept or reject, and these decisions are sent to a referee, who makes a final decision based on the servers' local decisions. Uniformity testing is a particularly useful building-block, because it is complete for the problem of testing identity to any fixed distribution.

We prove that pseudorandom sets in the Grassmann graph have near-perfect expansion. This completes the last missing piece of the proof of the 2-to-2-Games Conjecture (albeit with imperfect completeness). The Grassmann graph has induced subgraphs that are themselves isomorphic to Grassmann graphs of lower orders. A set of vertices is called pseudorandom if its density within all such subgraphs (of constant order) is at most slightly higher than its density in the entire graph. We prove that pseudorandom sets have almost no edges within them. Namely, their edge-expansion is very close to 1.

We present a polynomial time reduction from gap-3LIN to label cover with 2-to-1 constraints. In the “yes” case the fraction of satisfied constraints is at least 1 −ε, and in the “no” case we show that this fraction is at most ε, assuming a certain (new) combinatorial hypothesis on the Grassmann graph. In other words, we describe a combinatorial hypothesis that implies the 2-to-1 conjecture with imperfect completeness. The companion submitted paper [Dinur, Khot, Kindler, Minzer and Safra, STOC 2018] makes some progress towards proving this hypothesis.

We show a directed and robust analogue of a boolean isoperimetric-type theorem of Talagrand [ Geom. Funct. Anal., 3 (1993), pp. 295--314]. As an application, we give a monotonicity testing algorithm that makes $\tilde{O}(\sqrt{n}/\varepsilon^2)$ nonadaptive queries to a function $f:\{0,1\}^n \mapsto \{0,1\}$, always accepts a monotone function, and rejects a function that is $\varepsilon$-far from being monotone with constant probability.

We present a candidate reduction from the 3-Lin problem to the 2-to-2 Games problem and present a combinatorial hypothesis about Grassmann graphs which, if correct, is sufficient to show the soundness of the reduction in a certain non-standard sense. A reduction that is sound in this non-standard sense implies that it is NP-hard to distinguish whether an n-vertex graph has an independent set of size ( 1- 1/√2 ) n - o(n) or whether every independent set has size o(n), and consequently, that it is NP-hard to approximate the Vertex Cover problem within a factor √2-o(1).

We show a directed and robust analogue of a boolean isoperimetric type theorem of Talagrand [13]. As an application, we give a monotonicity testing algorithm that makes O̅(√n/ε2) non-adaptive queries to a function f : {0, 1}n→ {0, 1}, always accepts a monotone function and rejects a function that is ε-far from being monotone with constant probability.