Authors Irit Dinur, Inbal Livni Navon,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 19 (3), 2023, pp. 1โ56
www.theoryofcomputing.org
Exponentially Small Soundness for the
Direct Product Z-test
Irit Dinurโ Inbal Livni Navonโ
Received July 4, 2019; Revised October 12, 2022; Published October 2, 2023
Abstract. Given a function ๐ : [๐] ๐ โ [๐] ๐ , the Z-test is a three-query test for
checking if the function ๐ is a direct product, i. e., if there are functions ๐1 , . . . , ๐ ๐ :
[๐] โ [๐] such that ๐ (๐ฅ 1 , . . . , ๐ฅ ๐ ) = (๐1 (๐ฅ 1 ), . . . , ๐ ๐ (๐ฅ ๐ )) for every input ๐ฅ โ [๐] ๐ .
This test was introduced by Impagliazzo โ et. al. (SICOMP 2012), who showed that
if the test passes with probability ๐ > exp(โ ๐) then ๐ is ฮฉ(๐)-correlated to a direct
product function in some precise sense. It remained an open question whether the
soundness of this test can be pushed all the way down to exp(โ๐) (which would
be optimal). This is our main result: we show that whenever ๐ passes the Z-test
with probability ๐ > exp(โ๐) , there must be a global reason for this, namely, ๐ is
ฮฉ(๐)-correlated to a direct product function, in the same sense of closeness.
Towards proving our result we analyze the related (two-query) V-test, and prove
a โrestricted global structureโ theorem for it. Such theorems were also proven
in previous work on direct product testing in the small soundness regime. The
most recent paper, by Dinur and Steurer (CCC 2014), analyzed the V-test in the
exponentially small soundness regime. We strengthen their conclusion by moving
A preliminary version of this paper appeared in the Proceedings of the 32nd Computational Complexity
Conference, 2017 [7].
โ Research supported in part by an ISF-UGC grant number 1399/14, and by BSF grant number 2014371.
โ Research supported in part by an ISF-UGC grant number 1399/14, and by BSF grant number 2014371.
ACM Classification: F.2.2
AMS Classification: 68Q25
Key words and phrases: direct product testing, property testing, agreement
ยฉ 2023 Irit Dinur and Inbal Livni Navon
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2023.v019a003
I RIT D INUR AND I NBAL L IVNI NAVON
from an โin expectationโ statement to a stronger โconcentration of measureโ type of
statement, which we prove using reverse hypercontractivity. This stronger statement
allows us to proceed to analyze the Z-test.
1 Introduction
A function ๐ : [๐] ๐ โ [๐] ๐ for ๐ , ๐, ๐ โ โ is a direct product function if ๐ = (๐1 , . . . , ๐ ๐ ) , for
๐ ๐ : [๐] โ [๐], i. e., the output of ๐ on each coordinate depends on the input to this coordinate
alone. Direct products appear in a variety of contexts in complexity theory, usually for hardness
amplification. In PCP constructions it underlies the Parallel Repetition Theorem [18] and
implicitly appears in other forms of gap amplification, see e. g., [4]. The specific task of testing
direct products as an abstraction of a certain element of PCP constructions was introduced by
[9].
The combinatorial question that underlies these constructions is the direct product testing
question: given a function ๐ : [๐] ๐ โ [๐] ๐ , is it a direct product function? The setting of
interest here is where we query ๐ on as few inputs as possible, and decide if is it a direct product
function. Direct product testing is a type of property testing question, yet it is not in the standard
property testing parameter regime. In property testing, we are generally interested in showing
that functions that pass the test with high probability, for example 99%, are close to having the
property.
In our case, we are interested in understanding the structure of functions that pass the test
with smallโbut non-trivialโprobability, e. g., 1%. The 1% regime is often more challenging
than the 99% regime. It plays an important role in PCPs where one needs to prove a large gap.
In such arguments, one needs to be able to deduce non-trivial structure even from a proof that
passes a verification test with small probability, e. g., 1%.
There are very few families of tests for which 1% theorems are known. These include
algebraic low-degree tests and direct product tests. For low-degree tests there has been a
considerable amount of work in various regimes and in particular towards understanding the
extent of the 1% theorems, see, e. g., [19, 1, 3] and [2]. It is intriguing to understand more broadly
for which tests such theorems can hold. Indeed, as far as we know, there are no other tests that
exhibit such strong โstructure vs. randomnessโ behavior, and direct product tests are natural
candidates in which to study this question.
We remark that finding new settings where 1% theorems hold (including in particular
derandomized direct products) can potentially be useful for constructing locally testable codes
and stronger PCPs, see, e. g., the recent papers [14, 6]. Towards this goal, gaining a more
comprehensive understanding of direct product tests, as well as developing tools for proving
them, are natural objectives.
โ Our results improve the minimal soundness of the 2-query PCP
from [13] from exp( ๐) to exp(๐).
T HEORY OF C OMPUTING, Volume 19 (3), 2023, pp. 1โ56 2
E XPONENTIALLY S MALL S OUNDNESS FOR THE D IRECT P RODUCT Z- TEST
Test 1: Z-test with parameter ๐ก (3-query test)
1. Choose ๐ด, ๐ต, ๐ถ to be a random partition of [๐], ๐ด ๐ถ ๐ต
such that |๐ด| = |๐ต| = ๐ก. ๐ฅ
2. Choose uniformly at random ๐ฅ, ๐ฆ, ๐ง โ [๐] ๐ such ๐ฆ
that ๐ฅ ๐ด = ๐ฆ๐ด and ๐ฆ๐ต = ๐ง ๐ต .
๐ง
3. Accept if ๐ (๐ฅ)๐ด = ๐ (๐ฆ)๐ด and ๐ (๐ง)๐ต = ๐ (๐ฆ)๐ต .
Denote by agr๐ก๐ ( ๐ ) the success probability of ๐ on this test.
1.1 Our main result
The main question we study is: if ๐ : [๐] ๐ โ [๐] ๐ passes a certain natural test (Test 1) with
non-negligible probability, what does ๐ look like?
Theorem 1.1 (Main Theorem โ Global Structure). For every ๐ , ๐ > 1, there exists ๐ > 0 such that
for every ๐ > 0 and large enough ๐, if ๐ : [๐] ๐ โ [๐] ๐ is a function that passes Test 1 with probability
agr๐๐/10 ( ๐ ) = ๐ โฅ eโ๐๐ ๐ , then there exist functions (๐1 , . . . , ๐ ๐ ) , ๐ ๐ : [๐] โ [๐] such that
2
๐
๐๐
Pr ๐ (๐ฅ) โ (๐1 (๐ฅ 1 ) . . . , ๐ ๐ (๐ฅ ๐ )) โฅ ,
๐ฅโ[๐] ๐ 10
๐๐
where โ means that the strings are equal on all but at most ๐๐ coordinates.
The theorem is qualitatively tight with respect to several parameters: (i) soundness (i. e., the
parameter ๐), (ii) approximate equality vs. exact equality (i. e., the parameter ๐), (iii) number of
queries in the test. We discuss these next.
(i) Soundness The soundness of the theorem is the smallest success probability for which the
theorem holds. In our case it is 2โ๐ ๐ for some constant ๐ > 0. This is tight up to the constant ๐,
as can be seen from the example below.
Example 1.2 (Random function). Let ๐ : [๐] ๐ โ {0, 1} ๐ be a random function, i. e., for each
๐ฅ โ [๐] ๐ choose ๐ (๐ฅ) โ {0, 1} ๐ uniformly and independently. Two random strings in {0, 1} ๐ก are
equal with probability 2โ๐ก , therefore agr๐ก๐ ( ๐ ) โฅ 2โ2๐ก , since the test performs two such checks.
On the other hand, since ๐ is random, it is not close to any direct product function (see Section 6
for more information).
We remark that every function ๐ : [๐] ๐ โ {0, 1} ๐ is at least 2โ๐ close to a direct product
function 1, so this amount of correlation is meaningless. We conclude that in order to have direct
product theorem that is not trivial, the minimal soundness has to be larger than 2โ๐ .
1Consider the direct product function constructed incrementally by taking the most common value out of {0, 1}
on each step.
T HEORY OF C OMPUTING, Volume 19 (3), 2023, pp. 1โ56 3
I RIT D INUR AND I NBAL L IVNI NAVON
Test 2: V-test with parameter ๐ก (2-query test)
1. Choose ๐ด โ [๐] of size ๐ก, uniformly at random.
๐ด
2. Choose uniformly at random ๐ฅ, ๐ฆ โ [๐] ๐ such ๐ฅ
that ๐ฅ ๐ด = ๐ฆ๐ด .
๐ฆ
3. Accept if ๐ (๐ฅ)๐ด = ๐ (๐ฆ)๐ด .
Denote by agrโจ๐ก ( ๐ ) the success probability of ๐ on this test.
(ii) Approximate equality vs. exact equality In the theorem, we prove that for for an ฮฉ(๐)
๐๐
fraction of the inputs ๐ฅ we have ๐ (๐ฅ) โ (๐1 (๐ฅ), . . . , ๐ ๐ (๐ฅ)) . A priori, one could hope for a stronger
conclusion in which ๐ (๐ฅ) = (๐1 (๐ฅ), . . . , ๐ ๐ (๐ฅ)) for an ฮฉ(๐) fraction of the inputs ๐ฅ. However,
Example 1.3 shows that for ๐ก = ๐/10 , approximate equality is necessary.
Example 1.3 (Noisy direct product function). This example is from [5]. Let ๐ be a direct product
function, except that on each input ๐ฅ we โcorrupt" ๐ (๐ฅ) on ๐๐ random coordinates by changing
๐ (๐ฅ) on these coordinates into random values. For ๐ > 1/10 , the probability that Test 1 on ๐
misses all the corrupted coordinates is 2โฮฉ(๐๐) , in which case the test succeeds. Since we have
changed ๐ (๐ฅ) on ๐๐ coordinates into random values, no direct product function can approximate
๐ on more than a (1 โ ๐) fraction of the coordinates.
From this example, we conclude that it is not possible to approximate ๐ that passes Test 1
(with parameter ๐ก = ๐/10) with probability eโ๐๐๐ on more than a (1โ๐) fraction of the coordinates.
In Section 6 we prove similar bounds for different intersection sizes, and also discuss different
test variants.
(iii) Number of queries in the test The absolute minimum number of queries for any direct
product test is two. Indeed, there is a very natural 2-query test, Test 2. Dinur and Goldenberg
showed that it is not possible to have a direct product theorem with soundness lower than
1/poly(๐) using the 2-query test [5].
Example 1.4 (Localized direct product functions). In this example we assume that ๐ = ๐(๐ 2 ) .
For every ๐ โ [๐] we choose a random function ๐๐ : [๐] โ [๐] independently. For every input
๐ฅ โ [๐] ๐ , we choose a random ๐ ๐ฅ โ ๐, set ๐ = ๐ฅ ๐ and set ๐ (๐ฅ) = (๐๐ (๐ฅ 1 ), . . . , ๐๐ (๐ฅ ๐ )) .
The function ๐ satisfies agrโจ๐ก ( ๐ ) โฅ ๐ก/๐ 2 ; indeed, for ๐ฅ, ๐ฆ and ๐ด chosen in the test, if ๐ ๐ฅ = ๐ ๐ฆ
and ๐ ๐ฅ โ ๐ด, then the test will pass. The probability that ๐ ๐ฅ = ๐ ๐ฆ is 1/๐ , and the probability that
๐ ๐ฅ โ ๐ด is ๐ก/๐ .
For ๐ = ๐(๐ 2 ) , the function ๐ is far from direct product, since it is made up from ๐ different
direct product functions, each piece consisting of roughly a 1/๐ fraction of the domain [๐] ๐ .
For every ๐ก, the function described in the example satisfies agrโจ๐ก ( ๐ ) โฅ 1/๐ 2 , yet there is
no direct product function that approximates ๐ on ฮฉ(1/๐ 2 ) fraction of the domain. In [5] the
T HEORY OF C OMPUTING, Volume 19 (3), 2023, pp. 1โ56 4
E XPONENTIALLY S MALL S OUNDNESS FOR THE D IRECT P RODUCT Z- TEST
Test 3: Z-test for functions over sets, with parameter ๐ก (3-queries)
1. Choose random ๐ , ๐ , ๐ , ๐ โ [๐], such that |๐ | =
|๐ | = ๐ก, |๐ | = |๐| = ๐ โ ๐ก and ๐ โฉ ๐ = ๐ โฉ ๐ = ๐ ๐
๐ โฉ ๐ = โ
.
2. Accept if ๐ (๐ โช ๐)๐ = ๐ (๐ โช ๐)๐ and ๐ ๐
๐ (๐ โช ๐)๐ = ๐ (๐ โช ๐)๐ .
Denote by agr๐ก๐ ๐ ๐๐ก ( ๐ ) the success probability of ๐ on this test.
conclusion from Example 1.4 was that 1/poly(๐) is the limit for small soundness for direct
product tests. However, [13] showed that by adding just one more query, this limitation goes
away. They introduced a 3-query test, similar to Test 1, and proved a direct product theorem for
๐ฝ
all ๐ > 2โ๐ for some constant ๐ฝ โค 1/2 .
Direct product test for functions over sets Some of the previous results on direct products, such
as [13], were proven in a slightly different setting where the function tested is ๐ : [๐] โ [๐] ๐ .
๐
The input to ๐ is an unordered set ๐ โ [๐] of ๐ elements, and we view ๐ (๐) a matching that
matches each element ๐ โ ๐ to an element ๐ (๐)๐ โ [๐]. The first bit of ๐ (๐) corresponds to
๐ (๐)๐ for the smallest elements ๐ โ ๐, and so on. In this setting, a direct product function is
๐ก
๐ : [๐] โ [๐], and we say that ๐ (๐) โ ๐(๐) if for all but ๐ก of the elements ๐ โ ๐, ๐ (๐)๐ = ๐(๐).
In this article, we prove a direct product testing theorem also for this setting. Test 3 is the
analog of Test 1 for functions over sets. In Test 3 (see figure), we pick four sets ๐ , ๐ , ๐, ๐ โ [๐],
such that ๐ โฉ ๐ = ๐ โฉ ๐ = ๐ โฉ ๐ = โ
(other intersections can be non-empty). The sets are
picked such that |๐ โช ๐ | = |๐ โช ๐ | = |๐ โช ๐ | = ๐ , so that they can be inputs for ๐ .
Theorem 1.5 (Global Structure for Sets). There exists a constant ๐ > 0, such that for every ๐ > 0, large
enough ๐ โ โ and ๐ > e๐๐๐ , ๐ โ โ , if the function ๐ : [๐] โ [๐] ๐ passes Test 3 with probability
๐
agr๐๐/10
๐ ๐๐ก
( ๐ ) = ๐ > eโ๐๐๐ , then there exists a function ๐ : [๐] โ [๐] such that
๐๐
Pr ๐ (๐) โ ๐(๐) โฅ ๐ โ 4๐ 2 .
๐
Notice that the bound ๐ โ 4๐ 2 is better than the bound in Theorem 1.1, and it is tight, as
demonstrated by the function ๐ which is a hybrid of 1/๐ different direct product functions on
equal parts of the inputs. Such function ๐ passes Test 3 with probability ๐, and every direct
product function is close to ๐ only on an ๐ fraction of the inputs.
We remark that the two theorems are not the same. In Theorem 1.1, there are ๐ different
functions ๐1 , . . . , ๐ ๐ : [๐] โ [๐] whereas in Theorem 1.5 there is a single one. Furthermore,
Theorem 1.1 holds for any ๐ , ๐ โ โ and large enough ๐, and Theorem 1.5 (and other such
direct product theorems) only hold for ๐ ๐. The proofs of the theorems are also different, as
discussed later in the Introduction.
T HEORY OF C OMPUTING, Volume 19 (3), 2023, pp. 1โ56 5
I RIT D INUR AND I NBAL L IVNI NAVON
The proof of the global structure for sets uses the fact that the first query, ๐ โช ๐, and the last
query, ๐ โช ๐, are nearly independent. These queries are not completely independent, because
๐, ๐ are picked such that ๐ โฉ ๐ = โ
. The difference between the distribution of ๐ โช ๐ and
๐ โช ๐ and the distribution of two independent subsets of size ๐ is bounded by ๐ 2 /๐ . This
means that the theorem holds when ๐ 2 /๐ ๐ . For an exponentially small ๐, this implies that
๐ = exp(๐). We have not analyzed the case where ๐ is smaller with respect to ๐ in this setting
(in the main theorem, when ๐ : [๐] ๐ โ [๐] ๐ , there is no requirement that ๐ should be large
with respect to ๐).
1.2 Restricted global structure
Our proof has two main parts, similar to the structure of the proof of [5, 13]. In the first part, we
analyze only Test 2 and prove a restricted global structure theorem for it, Theorem 1.6 below,
(this was called local structure in [13, 8]). The term โrestricted global structureโ refers to the
case when we restrict the domain to small (but not trivial) pieces, and show that ๐ is close to a
product function on each piece separately. This is the structure of the function in Example 1.4.
More explicitly, for every ๐ด โ [๐] of size ๐/10 , ๐ โ [๐]๐ด and ๐พ โ [๐]๐ด , a restriction is a triple
๐ = (๐ด, ๐, ๐พ). The choice of ๐ก = ๐/10 in Theorem 1.1 is somewhat arbitrary, the theorem can be
proven with ๐ก = ๐ ๐ for any constant ๐ < 1/2 . The restriction corresponds to the set of inputs
๐ฑ๐ = {๐ค โ [๐][๐]\๐ด | ๐ (๐, ๐ค)๐ด = ๐พ}.
Our restricted global structure theorem is that for many restrictions ๐, there exists a direct
product function that is close to ๐ on ๐ฑ๐ .
Theorem 1.6 (Restricted Global Structure โ informal). There exists a constant ๐ > 0, such that for
every ๐ผ > 0 and large enough ๐ โ โ the following holds. Let ๐ : [๐] ๐ โ [๐] ๐ be a function that passes
Test 2 with probability agrโจ๐/10 ( ๐ ) = ๐ > eโ๐๐ผ๐ . Let ๐ be the test distribution over ๐, namely choosing
๐ด โ [๐], ๐ฅ โ [๐] ๐ uniformly and setting ๐ = (๐ด, ๐ฅ ๐ด , ๐ (๐ฅ)๐ด ) . Then with probability ฮฉ(๐), there exists
a direct product function ๐ = (๐1 , . . . , ๐9๐/10 ), ๐ ๐ : [๐] โ [๐] such that,
๐ผ๐
Pr ๐ (๐, ๐ค)[๐]\๐ด โ ๐(๐ค[๐]\๐ด ) ๐ค โ ๐ฑ๐ โฅ 1 โ ๐ 2 (1.1)
๐คโ[๐][๐]\๐ด
A similar theorem was proven in [13] but only for soundness (i. e., ๐) at least exp(โ๐ ๐ฝ ) for
a constant ๐ฝ โค 1/2 . This was strengthened to soundness exp(โฮฉ(๐)) in [8]. Our Theorem 1.6
improves on the conclusion of [8]. In [8] the probability in (1.1) was shown to be at least 1 โ ๐(๐ผ)
(recall that ๐ผ is a constant), whereas we show it is exponentially close to 1 (when ๐ is that
small). This difference may seem minor but in fact it is what prevented [8] from deriving global
structure via a three-query test (i. e., moving from the V-test to the Z-test). When we try to move
from restricted global structure to global structure, the consistency inside each restriction needs
to be very high for the probabilistic arguments to work, as we explain below.
The restricted global structure gives us a direct product function that approximates ๐ only
on a restricted subset of the inputs. In the proof of the global structure, we use the third query
T HEORY OF C OMPUTING, Volume 19 (3), 2023, pp. 1โ56 6
E XPONENTIALLY S MALL S OUNDNESS FOR THE D IRECT P RODUCT Z- TEST
to show that there exists a global function. A key step in the proof of the global structure is
to show that for many restrictions ๐, the function ๐๐ is close to ๐ on a much larger subsets of
inputs. This is done, intuitively, by claiming that if ๐ (๐ฅ)๐ด = ๐ (๐ฆ)๐ด , then with high probability
๐ (๐ฆ) โ ๐๐ (๐ฆ) for ๐ = (๐ด, ๐ฅ ๐ด , ๐ (๐ฅ)๐ด ) . Since ๐ต is a random set and ๐ (๐ง)๐ต = ๐ (๐ฆ)๐ต , then ๐ (๐ง), ๐๐ (๐ง)
are also close. This claim only holds if the success probability on (1.1) is more than 1 โ ๐, else it
is possible that all the success probability of the test comes from ๐ such that ๐ (๐ฅ)๐ด = ๐ (๐ฆ)๐ด , but
๐ (๐ฆ), ๐๐ (๐ฆ) are far from each other.
1.3 Technical contribution
In terms of technical contributions our proof consists of two new components.
Domain extension Our first contribution is a new domain extension step that facilitates the proof
of the restricted global structure. The restricted global structure shows that with probability
ฮฉ(๐), the function ๐ is close to a direct product function on the restricted domain ๐ฑ๐ . A natural
way to show that a function is close to a direct product function is to define a direct product
function by majority value. However, this method fails when the agreement guaranteed for ๐ is
small, as in our case.
This is usually resolved by moving to a restricted domain in which the agreement is much
higher, and by defining majority there. The first part of our proof is to show that with probability
ฮฉ(๐) over the restrictions ๐ = (๐ด, ๐, ๐พ), the set ๐ฑ๐ satisfies the two properties:
1. Its density is at least ๐/2 .
2. ๐ has very high agreement in ๐ฑ๐ . Informally it means that taking a random pair ๐ค, ๐ฃ โ ๐ฑ๐
which agree on a random subset of coordinates ๐ฝ, then ๐ (๐, ๐ค)๐ฝ โ ๐ (๐, ๐ฃ)๐ฝ with probability
greater than 1 โ ๐.
We call such restrictions excellent, following [13].
We show that for every excellent restriction ๐ฑ๐ , ๐ is close to a direct product function on
๐ฑ๐ . Let ๐๐ : ๐ฑ๐ โ [๐] ๐\๐ด be the restriction of ๐ to ๐ฑ๐ , i. e., โ๐ค โ ๐ฑ๐ , ๐๐ (๐ค) = ๐ (๐, ๐ค)[๐]\๐ด . The
function ๐๐ has high agreement, which is good for defining majority, but unfortunately ๐ฑ๐ is
very sparse in [๐] ๐\๐ด . The density of ๐ฑ๐ can be as low as ๐/2 , which is exponentially small,
and this is where the techniques used in [13] break down. In order to prove that ๐ is close to a
direct product function on ๐ฑ๐ , we use a local averaging operator to extend the domain from ๐ฑ๐
to [๐][๐]\๐ด .
The local averaging operator ๐ซ 3 is the majority of a 3/4-correlated neighborhood of ๐ฑ๐ ,
4
โ๐ค โ [๐][๐]\๐ด , ๐ โ [๐] \ ๐ด ๐ซ 3 ๐๐ (๐ค)๐ = Plurality { ๐๐ (๐ฃ)๐ },
๐ฃ โผ ๐ค,๐ฃโ๐ฑ๐ ,๐ฃ ๐ =๐ค ๐
4
3/4
where ๐ฃ โผ ๐ค means that for every ๐ โ ๐ independently, we take ๐ฃ ๐ = ๐ค ๐ with probability 1/4 ,
3/4
and a random value in [๐] else.
T HEORY OF C OMPUTING, Volume 19 (3), 2023, pp. 1โ56 7
I RIT D INUR AND I NBAL L IVNI NAVON
The domain of the new function is all of [๐][๐]\๐ด , ๐ซ 3 ๐๐ : [๐][๐]\๐ด โ [๐][๐]\๐ด , and it satisfies
4
the following properties:
1. ๐ซ 3 ๐๐ approximates ๐๐ on ๐ฑ๐ .
4
2. ๐ซ 3 ๐๐ has high agreement, taking a random pair ๐ค, ๐ฃ โ [๐][๐]\๐ด such that ๐ค ๐ฝ = ๐ฃ ๐ฝ , results
4
in agreeing answers, ๐ซ 3 ๐๐ (๐ค)๐ฝ โ ๐ซ 3 ๐๐ (๐ฃ)๐ฝ with probability greater than 1 โ ๐.
4 4
The main technical tool we use to prove these properties is a reverse hypercontractivity argument
from [16]. For every two sets ๐ , ๐ โ [๐] ๐ , Mossel et al. proved a lower bound on the probability
of a random ๐ค โ [๐] ๐ and ๐ฃ โผ3/4 ๐ค to be in ๐ and in ๐, respectively. We use their result to
prove that for almost all of ๐ค โ [๐][๐]\๐ด , taking ๐ฃ โผ ๐ค ends inside ๐ฑ๐ with probability at least
3/4
poly(๐). This allows us to prove that for almost all of ๐ค โ [๐][๐]\๐ด , ๐ โ [๐] \ ๐ด , the plurality
๐ซ 3 ๐๐ (๐ค)๐ relays on many values of ๐๐ (๐ฃ)๐ , which in turn lets us to prove the two properties above.
4
Lastly, we define a direct product function ๐๐ by taking the plurality over ๐ซ 3 ๐๐ , and show
4
that it is close to ๐๐ .
Direct product testing in a dense regime A second new element comes when stitching the
many localized functions into one global direct product function, by using the third query.
We prove two global structure theorems, Theorem 1.1 for functions on tuples (ordered lists)
๐ : [๐] ๐ โ [๐] ๐ and Theorem 1.5 for functions on sets ๐ : [๐] โ [๐] ๐ .
๐
When we work with ๐ that is defined over sets, we can directly follow the approach of [13] to
complete the proof. However, when working with ๐ defined on tuples we reach a combinatorial
question that itself resembles a direct product testing question, but in a different (dense) regime.
Luckily, the fact that this question is in a dense regime makes it easier to solve, and this leads to
our global structure theorem for tuples.
1.4 Agreement tests and direct product tests
The question of direct product testing fits into a more general family of tests called agreement
tests. We digress slightly to describe this setting formally and explain how direct product tests
fit into this framework.
Agreement tests In all efficient PCPs we break a proof into small overlapping pieces, use
relatively inefficient PCPs (i. e., PCPs that incur a large blowup) to encode each small piece,
and then through an agreement test put the pieces back together. The agreement test is needed
because given the set of pieces (their values and locations), there is no guarantee that the
different pieces come from the same underlying global proof, i. e., that the proofs of each piece
can be โput back together againโ. The PCP system needs to ensure this through agreement testing:
we take two (or more) pieces that have some overlap, and check that they agree.
T HEORY OF C OMPUTING, Volume 19 (3), 2023, pp. 1โ56 8
E XPONENTIALLY S MALL S OUNDNESS FOR THE D IRECT P RODUCT Z- TEST
Figure 1: complete ๐-uniform ๐-partite graph
โโ๐ป
๐
vertices
๐1 ๐2 ๐๐
This situation can be formulated as an agreement testing question as follows. Let ๐ be a
ground set, |๐ | = ๐, and let ๐ป be a collection of subsets of ๐, i. e., a set of hyperedges. Let [๐]
be a finite set of colors, where it is sufficient to think of ๐ = 2.
A local assignment is a set ๐ = {๐ ๐ } of local colorings ๐ ๐ : ๐ โ [๐], one per subset ๐ โ ๐ป. A
local assignment is called global if there is a global coloring ๐ : ๐ โ [๐] such that
โ๐ โ ๐ป, ๐ ๐ โก ๐| ๐ .
An agreement check for a tuple of subsets ๐ 1 , . . . , ๐ ๐ checks whether their local functions agree
on any point in the intersection, denoted agree(๐ ๐ 1 , . . . , ๐ ๐ ๐ ) . Formally,
agree(๐ ๐ 1 , . . . , ๐ ๐ ๐ ) โ โ๐, ๐ โ [๐], ๐ฅ โ ๐ ๐ โฉ ๐ ๐ , ๐ ๐ ๐ (๐ฅ) = ๐ ๐ ๐ (๐ฅ) .
A local assignment that is global passes all agreement checks. The converse is also true: a local
assignment that passes all agreement checks must be global.
An agreement test is specified by giving a distribution ๐ over tuples of subsets ๐ 1 , . . . , ๐ ๐ . We
define the agreement of a local assignment to be the probability of agreement,
agree(๐ ๐ 1 , . . . , ๐ ๐ ๐ ) .
agr(๐) = Pr
๐ (๐ 1 ,...,๐ ๐ )โผ๐
An agreement theorem shows that if ๐ is a local assignment with agr๐ (๐) > ๐ then ๐ is somewhat
close to a global assignment. Agreement theorems can be studied for any hypergraph and
in this article we prove such theorems for two specific hypergraphs: the ๐-uniform complete
hypergraph, and the ๐-uniform ๐-partite complete hypergraph.
Relation to direct product testing Theorem 1.5 is readily interpretted as an agreement test
theorem. As for Theorem 1.1, we next describe a hypergraph on which it can also be interpreted
โgeometricallyโ as an agreement test theorem. Consider complete ๐-uniform ๐-partite hypergraph
(see Figure 1). Let ๐บ = (๐ = ๐1 , . . . , ๐๐ , ๐ป) be the complete ๐-partite hypergraph with |๐๐ | = ๐
for ๐ โ [๐], and
๐ป = {(๐ฃ 1 , . . . , ๐ฃ ๐ ) | โ๐ โ [๐], ๐ฃ ๐ โ ๐๐ } .
T HEORY OF C OMPUTING, Volume 19 (3), 2023, pp. 1โ56 9
I RIT D INUR AND I NBAL L IVNI NAVON
There is a bฤณection between ๐ป and [๐] ๐ . We shall interpret ๐ (๐ฅ1 , . . . , ๐ฅ ๐ ) as a local coloring of
the vertices ๐ฅ 1 , . . . , ๐ฅ ๐ . In this way, we have the following equivalence
๐ : [๐] ๐ โ [๐] ๐ โโ ๐ = {๐ ๐ฅ } ๐ฅโ๐ป .
Moreover, local assignments which are global, i. e., ๐ such that ๐ ๐ฅ = ๐| ๐ฅ for some global
coloring ๐ : ๐1 โช ยท ยท ยท โช ๐๐ โ [๐], correspond exactly to functions ๐ which are direct products,
๐ = (๐1 , . . . , ๐ ๐ ) where ๐ ๐ = ๐|๐๐ ,
๐ = (๐1 , . . . , ๐ ๐ ) โโ ๐ is global.
Finally, Test 2 can be described as taking 2 hyperedges that intersect on ๐ก vertices, and check
if their local functions agree on the intersection. Similarly, Test 1 can be described as picking
three hyperedges, โ 1 , โ2 , โ3 โ ๐ป such that โ 1 , โ2 intersect on ๐ก vertices, and โ2 , โ3 intersect on a
disjoint set of ๐ก vertices, and checking agreement.
Our main theorem, Theorem 1.1, is equivalent to an agreement theorem showing that if a
local assignment ๐ passes a certain 3-query agreement test with non-negligible probability, then
there exists a global assignment ๐ : ๐ โ [๐] with which it agrees non-negligibly.
The ๐-uniform complete hypergraph (it is non-partite, in contrast to the above), is related to
Theorem 1.5. In this hypergraph the vertex set is [๐] and there is a hyperedge for every possible
๐-element subset of [๐]. Now we have a similar equivalence between local assignments and
functions over sets, i. e., functions where the input is a set ๐ โ [๐] of size ๐,
[๐]
๐ : โ [๐] ๐ โโ ๐ = {๐ ๐ } ๐ โ([๐]) .
๐ ๐
An agreement theorem for this hypergraph is equivalent to Theorem 1.5, in which ๐ is defined
not on the set of tuples [๐] ๐ but on the set of subsets [๐] . A global assignment ๐ on this graph
๐
is equivalent to a direct product function over sets, i. e., ๐ = ๐ : [๐] โ [๐] .
1.5 Organization of the paper
Section 2 contains preliminary notation and definitions. In Section 3 we prove the restricted
global structure, Theorem 1.6. Section 4 is dedicated to the global structure for functions on
sets. We show how to deduce a variant of Theorem 1.6 for sets rather than tuples and then
prove the global structure theorem for sets, Theorem 1.5. In Section 5 we prove the global
structure theorem for tuples, Theorem 1.1. Lastly, in Section 6 we discuss lower bounds for
various 3-query direct product tests that were not presented in the introduction.
The conference version of this paper had a small gap in the proof that has been thankfully
caught by the careful reviewers and editor, and this has been corrected in Appendix A by
referencing to [12].
2 Preliminaries
For a set ๐ด โ [๐] we denote by ๐ดยฏ the set [๐] \ ๐ด.
T HEORY OF C OMPUTING, Volume 19 (3), 2023, pp. 1โ56 10
E XPONENTIALLY S MALL S OUNDNESS FOR THE D IRECT P RODUCT Z- TEST
Definition 2.1. For every 2 strings ๐ฅ, ๐ฆ โ [๐] ๐ we say that
๐ก
1. ๐ฅ โ ๐ฆ if ๐ฅ, ๐ฆ differ in at most ๐ก coordinates.
๐ก
2. ๐ฅ 0 ๐ฆ if ๐ฅ, ๐ฆ differ in more than ๐ก coordinates.
Notice that the distance in the above definition is not relative, but it is the number of
coordinates in which the two strings differ.
For a set ๐ด โ [๐], we denote by ๐ โ [๐]๐ด a matching from every ๐ โ ๐ด to an element in [๐].
ยฏ
For ๐ โ [๐]๐ด and ๐ค โ [๐]๐ด , the string (๐, ๐ค) โ [๐] ๐ is the string created by taking for each ๐ โ ๐ด
the element matched to ๐ in ๐, and for each ๐ โ ๐ด the element matched to ๐ in ๐ค.
Let ๐ฅ โ [๐] ๐ , we denote by ๐ฅ ๐ด โ [๐]๐ด the matching which matches each ๐ โ ๐ด the element
๐ฅ ๐ โ [๐].
๐ก
For ๐ฅ, ๐ฆ โ [๐]๐ด , we say that ๐ฅ โ ๐ฆ if for all except at most ๐ก coordinates ๐ โ ๐ด, ๐ฅ, ๐ฆ match the
same value to ๐.
Definition 2.2 (Plurality). The plurality of a function ๐ on a distribution ๐ is its most frequent
value
Plurality( ๐ (๐ฅ)) = arg max Pr [ ๐ (๐ฅ) = ๐ฝ] .
๐ฅโผ๐ ๐ฝ ๐ฅโ๐
We use a few different Bernstein-Chernoff-type concentration bounds, stated below.
ร๐
Fact 2.3 (Chernoff bound). Let ๐1 , . . . , ๐ ๐ be independent random variables in {0, 1}, let ๐ = ๐=1 ๐๐
and denote ๐ = ๐ผ[๐]. Then for every ๐ฟ โ (0, 1),
๐ฟ2 ๐
Pr [๐ โ ๐ โฅ ๐ฟ๐] โค eโ 3 (2.1)
๐1 ,...,๐ ๐
๐ฟ2 ๐
Pr [๐ โ ๐ โค โ๐ฟ๐] โค eโ 2 . (2.2)
๐1 ,...,๐ ๐
Inequality (2.1) appears as [10, Eq. (6)] and [15, Thm. 4.4.2]. Inequality (2.2) appears as [10,
Eq. (7)] and [15, Thm. 4.5.2].
We use two variants of this bound for sampling without replacement. The next variant
follows from combining Fact 2.3, Eq. (2.2) with Hoeffdingโs generic reduction from sampling
without replacement to a sum of independent variables, [11, Theorem 4].
Fact 2.4 (Hoeffding bound for random subset.). Let ๐ถ be a set, and let ๐ต โ ๐ถ be subset. Suppose we
pick a random subset ๐ โ ๐ถ of size ๐ < |๐ถ|, then for every ๐ฟ โ (0, 1)
|๐ต|๐ โ
|๐ต|๐๐ฟ 2
Pr |๐ต โฉ ๐| โค (1 โ ๐ฟ) โค e 2|๐ถ| .
๐ |๐ถ|
We also use the following result by Hoeffding.
T HEORY OF C OMPUTING, Volume 19 (3), 2023, pp. 1โ56 11
I RIT D INUR AND I NBAL L IVNI NAVON
Fact 2.5 (Hoeffdingโs inequality for random sampling without replacement, [11, Theorems 1 and
4] ). Let ๐ถ = {๐1 , . . . ๐ ๐ } be a multiset of ๐ values, ๐ ๐ โ [0, 1], and let ๐1 , . . . , ๐๐ be ๐ random samples
ร๐
without replacement from ๐ถ. Let ๐ = ๐=1 ๐๐ and denote ๐ = ๐ผ[๐], then
2๐ก 2
Pr [๐ โ ๐ > ๐ก] โค eโ ๐ .
๐1 ,...,๐ ๐
The random variables in Hoeffdingโs bounds for random variables without replacement
are not independent, but they are not independent in a very specific way, of being without
replacement. In addition to these bounds we also have the following bound for random variables
that are not independent. This bound appears as Theorem 1.1 in [12].
Fact 2.6 (Generalized Chernoff bound [12, 17]). Let ๐1 , . . . , ๐ ๐ be random variables in {0, 1}, let
ร๐
๐ = ๐=1 ๐๐ . If there exists ๐ โ (0, 1) such that for every ๐ โ [๐], Pr[โง๐โ๐ ๐๐ = 1] โค ๐ |๐| , then for every
๐พ โ (๐, 1),
[๐ โฅ ๐พ๐] โค eโ2๐(๐พโ๐) .
2
Pr
๐1 ,...,๐ ๐
2.1 Reverse hypercontractivity
Definition 2.7 (๐-correlated distribution). For every string ๐ฅ โ [๐] ๐ and constant ๐ โ (0, 1), the
๐-correlated distribution from ๐ฅ, denoted by ๐ฆ โผ ๐ฅ, is defined as follows. Each ๐ โ [๐] is inserted
๐,๐ฝ
into ๐ฝ with probability ๐, independently. The string ๐ฆ is chosen such that ๐ฅ ๐ฝ = ๐ฆ ๐ฝ , and the rest is
uniform. In some cases, we omit the subscript ๐ฝ.
We quote Proposition 9.2 from [16]:
๐2 ๐2
Proposition 2.8. Let ๐ด, ๐ต โ [๐] ๐ of sizes Pr๐คโ[๐]๐ [๐ค โ ๐ด] = eโ 2 and Pr๐คโ[๐]๐ [๐ค โ ๐ต] = eโ 2 .
Then
(2โ๐)(๐ 2 +๐ 2 ) ๐๐๐
โ โ 2(1โ๐)
Pr [๐ฅ โ ๐ด, ๐ฆ โ ๐ต] โฅ e 4(1โ๐) .
๐ฅโ[๐] ๐ ,๐ฆโผ๐ฅ
๐
By changing notation and simplifying, we get the following corollary.
Corollary 2.9. For ๐ด, ๐ต โ [๐] ๐ , |๐ด| โฅ |๐ต|,
๐ 3๐
[๐ฅ โ ๐ด, ๐ฆ โ ๐ต] โฅ Pr [๐ฅ โ ๐ด] Pr [๐ฅ โ ๐ต] .
1+ 2(1โ๐) 1+ 2(1โ๐)
Pr
๐ฅโ[๐] ๐ ,๐ฆโผ๐ฅ ๐ฅโ[๐] ๐ ๐ฅโ[๐] ๐
๐
Proof. |๐ด| โฅ |๐ต| implies ๐ โค ๐, we know that
๐๐๐ ๐๐ 2 ๐
โ 2(1โ๐) โ 2(1โ๐)
e โฅe = Pr [๐ฅ โ ๐ต] 1โ๐ .
๐ฅโ[๐] ๐
T HEORY OF C OMPUTING, Volume 19 (3), 2023, pp. 1โ56 12
E XPONENTIALLY S MALL S OUNDNESS FOR THE D IRECT P RODUCT Z- TEST
Similarly
๐
(2โ๐)(๐ 2 +๐ 2 )
ยท โ ๐2 โ ๐2 1+ 2(1โ๐) ยท โ ๐2 โ ๐2
2โ๐ 2 2 2 2
โ
e 4(1โ๐) =e 2(1โ๐)
=e =
๐ ๐
Pr [๐ฅ โ ๐ต] Pr [๐ฅ โ ๐ด] .
1+ 2(1โ๐) 1+ 2(1โ๐)
๐ฅโ[๐] ๐ ๐ฅโ[๐] ๐
Together we get
๐ 3๐
Pr [๐ฅ โ ๐ด, ๐ฆ โ ๐ต] โฅ Pr [๐ฅ โ ๐ด] Pr [๐ฅ โ ๐ต] .
1+ 2(1โ๐) 1+ 2(1โ๐)
๐ฅ,๐ฆ ๐ฅโ[๐] ๐ ๐ฅโ[๐] ๐
3 Restricted global structure
In this section we prove the restricted global structure theorem, Theorem 1.6, which we restate
formally below as Theorem 3.9. Let ๐ : [๐] ๐ โ [๐] ๐ be a function that passes Test 2 with
probability ๐, i. e.,
agrโจ๐/10 ( ๐ ) = ๐ โฅ eโ๐๐ผ๐ .
We show that such ๐ already has some direct product structure, namely that there are restrictions
of the domain [๐] ๐ such that ๐ is close to a direct product function on each of the restricted
parts.
Definition 3.1 (Restriction). A restriction is a triple ๐ = (๐ด, ๐, ๐พ), for ๐ด โ [๐], |๐ด| = ๐/10 , ๐ โ [๐]๐ด
and ๐พ โ [๐]๐ด .
ยฏ
Definition 3.2 (Consistent strings). For every restriction ๐ = (๐ด, ๐, ๐พ), a string ๐ค โ [๐]๐ด is
consistent with ๐ if ๐ (๐, ๐ค)๐ด = ๐พ. For every ๐, let ๐ฑ๐ be the set of consistent strings,
n o
ยฏ
๐ฑ๐ = ๐ค โ [๐]๐ด ๐ (๐, ๐ค)๐ด = ๐พ .
ยฏ
Definition 3.3 (Restricted function). For each restriction ๐ = (๐ด, ๐, ๐พ), let ๐๐ : ๐ฑ๐ โ [๐]๐ด be the
function
๐๐ (๐ค) = ๐ (๐, ๐ค)๐ดยฏ .
Definition 3.4 (Distribution over restrictions). Let ๐ be the following distribution over re-
strictions ๐. Pick a uniform set ๐ด โ [๐] of size ๐/10 , pick a uniform ๐ฅ โ [๐] ๐ and output
๐ = (๐ด, ๐ฅ ๐ด , ๐ (๐ฅ)๐ด ) .
Note that the distribution ๐ depends on the function ๐ .
We define good restriction in an analogous way to the definitions of [13].
Definition 3.5 (Good restriction). A restriction ๐ = (๐ด, ๐, ๐พ) is good, if Pr๐คโ[๐]๐ดยฏ [๐ค โ ๐ฑ๐ ] โฅ ๐/2 .
T HEORY OF C OMPUTING, Volume 19 (3), 2023, pp. 1โ56 13
I RIT D INUR AND I NBAL L IVNI NAVON
Definition 3.6 (๐ผ-DP restriction). A restriction ๐ = (๐ด, ๐, ๐พ) is an ๐ผ-DP restriction if it is good,
and there exist functions ๐ ๐ : [๐] โ [๐] for each ๐ โ ๐ดยฏ such that, denoting ๐ = (๐ ๐ )๐โ๐ดยฏ ,
๐ผ๐
Pr ๐๐ (๐ค) 0 ๐(๐ค) ๐ค โ ๐ฑ๐ โค ๐ 2 .
๐คโ[๐]๐ดยฏ
Remark 3.7. The parameter ๐ผ can be viewed as slack. It is the amount of disagreement we are
willing to tolerate between two tuples, while still considering them in agreement.
We define a local averaging operator. Notice that the operator is not linear.
Definition 3.8 (Local averaging operator). For every ๐ โ [0, 1], let ๐ซ๐ be the following (non-linear)
ยฏ ยฏ
operator. For every subset ๐ฑ๐ โ [๐]๐ด and function โ : ๐ฑ๐ โ [๐]๐ด , the operator takes โ to the
ยฏ ยฏ ยฏ ๐ค โ [๐]๐ดยฏ ,
function ๐ซ๐ โ : [๐]๐ด โ [๐]๐ด satisfies โ๐ โ ๐ด,
๐ซ๐ โ(๐ค)๐ = Plurality (โ(๐ฃ)๐ ) .
๐ฃ โผ ๐ค s.t. ๐โ๐ฝ
๐,๐ฝ
We define plurality over an empty set to be an arbitrary value.
In the proof of the restricted global structure we use the operator ๐ซ๐ with ๐ = 3/4 , which
we denote by ๐ซ to simplify notation. Clearly 3/4 is an arbitrary constant, our proof works for
any constant ๐ > 1/2 .
Our main theorem of this section asserts that (a) a non-negligible fraction of restrictions are
good, and that (b) almost all good restrictions are DP restrictions.
Theorem 3.9 (Restricted Global Structure, formal). There exists a small constant ๐ > 0, such that for
every constant ๐ผ > 0 and large enough ๐ โ โ the following holds. For every function ๐ : [๐] ๐ โ [๐] ๐ ,
if agrโจ๐/10 ( ๐ ) = ๐ > eโ๐๐ผ๐ , then
๐
Pr [๐ is good] โฅ
๐โผ๐ 2
and
Pr [๐ is an ๐ผ-DP restriction | ๐ is good] โฅ 1 โ ๐ 2 .
๐โผ๐
A similar theorem was proven in [8] under the name โlocal structureโ. Under the same
assumptions [8] showed that ๐ must be close to a product function for many pieces ๐ฑ๐ of
the domain. However, the closeness was considerably weaker: unlike in our definition of
a DP restriction, in [8] even in the restricted part of the domain, ๐ฑ๐ โ [๐] ๐ , there could be
a (small) constant fraction of the inputs on which ๐ differs from the product function ๐. In
contrast, we only allow an ๐2 fraction of disagreeing inputs, which is necessary for the ensuing
global-structure argument.
Parameters. In the proof of the theorem we use several values for the slack parameter ๐ผ, that
are constant multiples of each other, which we denote by ๐ผ0 , ๐ผ 1 etc. These constant factors are
not important, and the reader can treat all ๐ผ ๐ as โsimilar to ๐ผโ.
We prove the theorem in Section 3.1, using lemmas that are proven on Section 3.2, Section 3.3
and Section 3.4.
T HEORY OF C OMPUTING, Volume 19 (3), 2023, pp. 1โ56 14
E XPONENTIALLY S MALL S OUNDNESS FOR THE D IRECT P RODUCT Z- TEST
3.1 Proof of Theorem 3.9
Let ๐ : [๐] ๐ โ [๐] ๐ be a function that passes Test 2 with probability ๐. The test can also be
ยฏ
written as: choose ๐ = (๐ด, ๐, ๐พ) โผ ๐ and a uniform ๐ค โ [๐]๐ด , and accept if ๐ (๐, ๐ค)๐ด = ๐พ.
๐
๐ = Pr test passes ๐ is chosen โค Pr ๐ is good ยท 1 + ,
๐โผ๐ ๐โผ๐ 2
because the success probability of the test on a restriction ๐ which is not good is at most ๐/2 .
Therefore,
๐
Pr ๐ is good โฅ .
(3.1)
๐โผ๐ 2
Fix ๐ผ0 = 1600
1
๐ผ.
Definition 3.10 (Excellent restriction). A good restriction ๐ = (๐ด, ๐, ๐พ) is excellent if for ๐ = 3/4
ยฏ
and for ๐ = 9/32 the following holds. Choose ๐ค โ [๐]๐ด uniformly and ๐ฃ โผ ๐ค then,
๐,๐ฝ
๐ผ0 ๐
๐ผ0 ๐ ฮ
Pr ๐ค, ๐ฃ โ ๐ฑ๐ and ๐๐ (๐ค)๐ฝ 0 ๐๐ (๐ฃ)๐ฝ โค eโ 40 = ๐ . (3.2)
๐ค,๐ฃ,๐ฝ
Lemma 3.11. A good ๐ โผ ๐ is excellent with probability at least 1 โ ๐ 2 .
The proof of the lemma appears on Section 3.2.
To prove Theorem 3.9 it is enough to show that every excellent restriction is an ๐ผ-DP
restriction. A natural idea is to define a direct product function by taking the plurality of ๐๐ on
๐ฑ๐ , because the agreement of ๐๐ inside ๐ฑ๐ is almost 1. However, it is difficult to prove that this
function is close to ๐๐ because the set ๐ฑ๐ is very sparse. Instead, we prove that ๐ซ ๐๐ is close to ๐๐ ,
and that ๐ซ ๐๐ is close to a direct product function. Fix ๐ผ1 = 10๐ผ 0 .
Lemma 3.12. For every excellent ๐,
๐ผ1 ๐
Pr ๐๐ (๐ค) 0 ๐ซ ๐๐ (๐ค) ๐ค โ ๐ฑ๐ โค ๐ 3 .
๐คโ[๐]๐ดยฏ
The proof appears in Section 3.3 and relies on reverse hypercontractivity.
Fix ๐ผ2 = 1500๐ผ 0 .
Lemma 3.13. For every excellent restriction ๐ there exists a direct product function ๐ = (๐1 , . . . , ๐ ๐ดยฏ ) ,
๐ ๐ : [๐] โ [๐] such that
๐ผ2 ๐
Pr ๐ซ ๐๐ (๐ค) 0 ๐(๐ค) โค 3๐ 4 .
๐คโ[๐]๐ดยฏ
The proof is in Section 3.4.
The two lemmas above, Lemma 3.12 and Lemma 3.13, imply the following claim.
T HEORY OF C OMPUTING, Volume 19 (3), 2023, pp. 1โ56 15
I RIT D INUR AND I NBAL L IVNI NAVON
Claim 3.14. Every excellent restriction ๐ is an ๐ผ-DP restriction.
Proof. Fix an excellent restriction ๐. Let ๐ = (๐1 , . . . , ๐ ๐ดยฏ ) , ๐ ๐ : [๐] โ [๐] be the direct product
function promised from Lemma 3.13. For an excellent ๐, Pr๐ค [๐ค โ ๐ฑ๐ ] โฅ 2๐ . Therefore, the
๐ผ2 ๐
probability of ๐ซ ๐๐ (๐ค) 0 ๐(๐ค) is small even when conditioning on ๐ค โ ๐ฑ๐ . By Lemma 3.13
๐ผ2 ๐
3๐ โฅ
4
Pr ๐ซ ๐๐ (๐ค) 0 ๐(๐ค)
๐คโ[๐]๐ดยฏ
๐ผ2 ๐
โฅ Pr [๐ค โ ๐ฑ๐ ] Pr ๐ซ ๐๐ (๐ค) 0 ๐(๐ค) ๐ค โ ๐ฑ๐
๐คโ[๐]๐ดยฏ ๐คโ[๐]๐ดยฏ
๐
๐ผ2 ๐
โฅ Pr ๐ซ ๐๐ (๐ค) 0 ๐(๐ค) ๐ค โ ๐ฑ๐ . (3.3)
2 ๐คโ[๐]๐ดยฏ
By the triangle inequality,
(๐ผ 1 +๐ผ2 )๐ ๐ผ1 ๐
Pr ๐๐ (๐ค) 0 ๐(๐ค) ๐ค โ ๐ฑ๐ โค Pr ๐๐ (๐ค) 0 ๐ซ ๐๐ (๐ค) ๐ค โ ๐ฑ๐
๐ค ๐ค
๐ผ2 ๐
+ Pr ๐ซ ๐๐ (๐ค) 0 ๐(๐ค) ๐ค โ ๐ฑ๐
๐ค
โค๐ + 6๐ 3 < ๐2 .
3
(by (3.3) and Lemma 3.12)
By definition, ๐๐ (๐ค) = ๐ (๐ฅ ๐ด , ๐ค)๐ดยฏ , so from the above equation
(๐ผ 1 +๐ผ 2 )๐ (๐ผ1 +๐ผ2 )๐
Pr ๐ (๐ฅ ๐ด , ๐ค)๐ดยฏ 0 ๐(๐ค) ๐ค โ ๐ฑ๐ = Pr ๐๐ (๐ค) 0 ๐(๐ค) ๐ค โ ๐ฑ๐ < ๐2 .
๐ค ๐ค
Since ๐ผ1 + ๐ผ2 < ๐ผ we are done.
In the proof we see that a random restriction ๐ โผ ๐ is good with probability ๐/2, and
that a good restriction is excellent with probability 1 โ ๐ 2 . From the claim above, an excellent
restriction ๐ is an ๐ผ-DP restriction, which finishes the proof.
3.2 Good restrictions are excellent with high probability
In this section we prove Lemma 3.11, which states that a good restriction is excellent with high
probability. We start by showing that when averaging over ๐, ๐๐ is consistent in ๐ฑ๐ .
ยฏ
Claim 3.15. For every ๐ โ (0, 1), let ๐ โผ ๐ , ๐ค โ [๐]๐ด and ๐ฃ โผ ๐ค, then
๐,๐ฝ
๐ผ0 ๐
๐ผ0 ๐
Pr ๐ค, ๐ฃ โ ๐ฑ๐ , ๐๐ (๐ค)๐ฝ 0 ๐๐ (๐ฃ)๐ฝ โค eโ 20 .
๐,๐ค,๐ฃ,๐ฝ
T HEORY OF C OMPUTING, Volume 19 (3), 2023, pp. 1โ56 16
E XPONENTIALLY S MALL S OUNDNESS FOR THE D IRECT P RODUCT Z- TEST
Proof. Denote ๐ = (๐, ๐ด, ๐พ). Let ๐ธ1 (๐, ๐ด, ๐ค, ๐ฃ, ๐ฝ, ๐พ) be the event that we are interested in bounding
its probability, namely, the event
๐ผ0 ๐
๐ (๐, ๐ค)๐ด = ๐ (๐, ๐ฃ)๐ด = ๐พ and ๐ (๐, ๐ค)๐ฝ 0 ๐ (๐, ๐ฃ)๐ฝ .
When ๐, ๐ค, ๐ฃ, ๐ด, ๐ฝ are all random, the probability of a uniform ๐ด, ๐ฝ to be such that ๐ (๐, ๐ค), ๐ (๐, ๐ฃ)
are equal on ๐ด but are far on ๐ฝ is very small.
๐ผ0 ๐
Let ๐ธ2 (๐ด, ๐, ๐ฃ, ๐ค, ๐ฝ) โ ๐ธ1 (๐ด, ๐, ๐ฃ, ๐ค, ๐ฝ, ๐พ) be the event that ๐ (๐, ๐ค)๐ด = ๐ (๐, ๐ฃ)๐ด and ๐ (๐, ๐ค)๐ฝ 0
๐ (๐, ๐ฃ)๐ฝ .
Fix ๐ โ (0, 1). We start by bounding the probability of ๐ธ2 under the distribution ๐ โผ ๐ ,
ยฏ
๐ค โ [๐]๐ด uniformly and ๐ฃ โผ ๐ค. Writing the distribution explicitly:
๐,๐ฝ
1. Pick ๐ด โ [๐] of size ๐/10 .
2. Pick ๐ฅ โ [๐] ๐ , set ๐ = ๐ฅ ๐ด and ๐พ = ๐ (๐ฅ)๐ด .
3. Pick ๐ฝ โ ๐ดยฏ of size โฌ(9๐/10, ๐) (binomial random variable).
ยฏ
4. Pick uniform ๐ค, ๐ฃ โ [๐]๐ด such that ๐ค ๐ฝ = ๐ฃ ๐ฝ .
Notice that ๐ธ2 is independent of ๐พ, so it does not matter how ๐พ is chosen. We can define an
equivalent process for producing the same distribution (without ๐พ):
1. Pick a set ๐ด0 โ [๐] of size ๐/10 + โฌ(9๐/10, ๐).
2. Pick ๐ฆ, ๐ง โ [๐] ๐ such that ๐ฆ๐ด0 = ๐ง ๐ด0 .
3. Pick ๐ด โ ๐ด0 of size ๐/10 .
4. Set ๐ = ๐ฆ๐ด , ๐ค = ๐ฆ๐ดยฏ and ๐ฃ = ๐ง ๐ดยฏ .
Let
๐ท = {๐ โ ๐ด0 | ๐ (๐ฆ)๐ โ ๐ (๐ง)๐ } .
๐ธ2 occurs only if ๐ด โฉ ๐ท = โ
yet |๐ท| โฅ ๐ผ0 ๐.
As the second random process allows us to see, ๐ด is a uniform subset of ๐ด0. Let ๐1 , . . . ๐ |๐ด| be
an arbitrary order over the elements of ๐ด. We can think of ๐ด as being chosen incrementally,
each ๐ ๐ is chosen randomly from ๐ด0 \ {๐1 , . . . , ๐ ๐โ1 } .
Pr [๐ด โฉ ๐ท = โ
] = Pr ๐1 , . . . , ๐ |๐ด| โ ๐ท
(3.4)
๐ด
= Pr [๐1 โ ๐ท] ยท Pr [๐2 โ ๐ท | ๐1 โ ๐ท] ยท ยท ยท Pr ๐ |๐ด| โ ๐ท ๐1 , . . . , ๐ |๐ด|โ1 โ ๐ท
โค(1 โ ๐ผ 0 )|๐ด| โค eโ๐ผ0 |๐ด|
where we use the fact that for every ๐ ๐ , Pr ๐ ๐ โ ๐ท ๐1 . . . ๐ ๐โ1 โ ๐ท โค 1 โ ๐ผ0 , since |๐ท| โฅ ๐ผ0 ๐.
T HEORY OF C OMPUTING, Volume 19 (3), 2023, pp. 1โ56 17
I RIT D INUR AND I NBAL L IVNI NAVON
๐ผ0 ๐
The bound in (3.4) holds for each ๐ด0 such that ๐ (๐ฆ)๐ด0 0 ๐ (๐ง)๐ด0 , therefore also on average,
๐ผ0 ๐
Pr [๐ธ2 ] = Pr ๐ (๐ฆ)๐ด0 0 ๐ (๐ง)๐ด0 and ๐ (๐ฆ)๐ด = ๐ (๐ง)๐ด โค eโ๐ผ0 |๐ด| .
๐ฆ,๐ง,๐ด0 ,๐ด
๐ผ0 ๐
We conclude that Pr[๐ธ1 ] โค Pr[๐ธ2 ] โค eโ๐ผ0 |๐ด| โค eโ 20 .
ยฏ
Proof of Lemma 3.11. For every restriction ๐ and ๐ค, ๐ฃ โ [๐]๐ด let ๐ธ(๐, ๐ค, ๐ฃ, ๐ฝ) be the event that
๐ผ0 ๐
๐ค, ๐ฃ โ ๐ฑ๐ and ๐๐ (๐ค)๐ฝ 0 ๐๐ (๐ฃ)๐ฝ .
For every ๐ that is good but not excellent, there is ๐ โ {3/4, 9/32} such that
Pr [๐ธ(๐, ๐ค, ๐ฃ, ๐ฝ)] > ๐ .
๐ค,๐ฃ โผ ๐ค
๐,๐ฝ
In this case we say that ๐ is bad for ๐.
Assume for a contradiction that Pr๐โผ๐ ๐ is good but not excellent > ๐3 /2 . These fail to be
excellent because of at least one of the choices of ๐, so either for ๐ = 3/4 or for ๐ = 9/32 ,
๐3
Pr [๐ is bad for ๐] โฅ .
๐โผ๐ 4
For this ๐,
๐3
Pr [๐ธ(๐, ๐ค, ๐ฃ, ๐ฝ)] โฅ Pr [๐ is bad for ๐] Pr [๐ธ(๐, ๐ค, ๐ฃ, ๐ฝ) | ๐ is bad for ๐] โฅ ๐.
๐โผ๐,๐ค,๐ฃ โผ ๐ค ๐โผ๐ ๐ค,๐ฃ โผ ๐ค 4
๐,๐ฝ ๐,๐ฝ
๐ผ๐
This contradicts Claim 3.15, because ๐3 /4 ยท ๐ โฅ eโ 20 , as ๐ผ0 = 1600๐ผ. Therefore, we conclude
that Pr๐โผ๐ ๐ is good but not excellent โค ๐ 3 /2 .
Finally, since ๐ โผ ๐ is good with probability at least ๐/2 , by averaging a good ๐ โผ ๐ is
excellent with probability at least 1 โ ๐ 2 .
3.3 Local averaging operator
In this section we prove Lemma 3.12, which states that for every excellent ๐, ๐ซ ๐๐ approximates
๐๐ .
ยฏ ยฏ
Fix an excellent ๐, and let ๐ฟ โ [๐]๐ด be the set of โlonelyโ strings in [๐]๐ด , those that have a
sparse neighborhood in ๐ฑ๐ . We fix te sparsity parameter ๐ = ๐ 50 , and define
( )
๐ดยฏ
๐ฟ = ๐ค โ [๐] Pr [๐ฃ โ ๐ฑ๐ ] โค ๐ .
๐ฃ โผ ๐ค
3/4,๐ฝ
There is a trade off between the โsparsityโ parameter ๐ and the bound on the size of ๐ฟ. The
sparsity parameter is chosen to make sure that Pr๐คโ[๐]๐ดยฏ [๐ค โ ๐ฟ] < ๐ 10 . These powers of ๐
T HEORY OF C OMPUTING, Volume 19 (3), 2023, pp. 1โ56 18
E XPONENTIALLY S MALL S OUNDNESS FOR THE D IRECT P RODUCT Z- TEST
are derived from our arbitrary choice of defining ๐ซ ๐๐ as the plurality of a 3/4-correlated
neighborhood.
In addition, the success probability of the test ๐ should be large enough to promise that ๐/๐2
is small.
Claim 3.16. Pr๐คโ[๐]๐ดยฏ [๐ค โ ๐ฟ] < ๐10
Proof. We prove the claim by using Corollary 2.9 on the sets ๐ฟ,๐ฑ๐ . Denote by ๐ ๐ฟ = Pr๐คโ[๐]๐ดยฏ [๐ค โ
๐ฟ] and ๐ = Pr๐คโ[๐]๐ดยฏ [๐ค โ ๐ฑ๐ ] . Since ๐ is excellent, ๐ โฅ ๐/2 .
Assume for a contradiction that |๐ฟ| > |๐ฑ๐ | , i. e., ๐ ๐ฟ โฅ ๐. By Corollary 2.9
5 ๐ 52 ๐ 112
[๐ค โ ๐ฟ, ๐ฃ โ ๐ฑ๐ ] โฅ ๐ ๐ฟ2 ๐ 2 โฅ .
11
Pr
๐คโ[๐]๐ดยฏ ,๐ฃ โผ ๐ค 2 2
3/4
By the definition of ๐ฟ
Pr [๐ค โ ๐ฟ, ๐ฃ โ ๐ฑ๐ ] โค ๐ ๐ฟ ๐ 50 , (3.5)
๐คโ[๐]๐ดยฏ ,๐ฃ โผ ๐ค
3/4
and we reach a contraction.
Therefore, ๐ ๐ฟ < ๐. By Corollary 2.9,
11 ๐ 52 11
[๐ค โ ๐ฟ, ๐ฃ โ ๐ฑ๐ ] โฅ ๐ ๐ฟ2 ๐ 2 โฅ ๐ ๐ฟ2 .
5
Pr
๐คโ[๐]๐ดยฏ ,๐ฃ โผ ๐ค 2
3/4
Equation (3.5) still holds, so combining the two bounds on Pr๐คโ[๐]๐ดยฏ ,๐ฃ โผ ๐ค [๐ค โ ๐ฟ, ๐ฃ โ ๐ฑ๐ ] ,
3/4
๐ 52 11
๐ ๐ฟ2 โค ๐ ๐ฟ ๐ 50 ,
2
That is ๐ ๐ฟ โค 2๐ 2 (50โ 2 ) < ๐10 .
9 5
The local averaging operator ๐ซ ๐๐ takes the plurality vote over ๐ฃ โผ ๐ค, conditioning on
3/4,๐ฝ
๐ฃ โ ๐ฑ๐ . If we pick ๐ฃ โผ ๐ค without conditioning on ๐ฃ โ ๐ฑ๐ , then each ๐ is in ๐ฝ with probability
3/4,๐ฝ
3/4 . For ๐ค โ ๐ฟ, taking ๐ฃ โผ ๐ค conditioning on ๐ฃ โ ๐ฑ๐ , we get that for most ๐, ๐ โ ๐ฝ with
3/4,๐ฝ
probability that is close to 3/4 .
ยฏ
Claim 3.17. For every ๐ค โ ๐ฟ and all except ๐ผ0 ๐ of the coordinates ๐ โ ๐ด,
3 1
Pr [๐ฝ 3 ๐|๐ฃ โ ๐ฑ๐ ] โฅ โ .
๐ฃ โผ ๐ค 4 10
3/4,๐ฝ
T HEORY OF C OMPUTING, Volume 19 (3), 2023, pp. 1โ56 19
I RIT D INUR AND I NBAL L IVNI NAVON
Proof. Fix ๐ค โ ๐ฟ. Let ๐ท be
( )
3 1
๐ท = ๐ โ [๐] Pr [๐ฝ 3 ๐|๐ฃ โ ๐ฑ๐ ] < โ .
๐ฃ โผ ๐ค 4 10
3/4,๐ฝ
Assume for a contradiction that the claim does not hold, i. e., |๐ท| > ๐ผ0 ๐.
๐ผ0 ๐
By the Chernoff bound (Fact 2.3), Pr๐ฃ โผ ๐ค |๐ท โฉ ๐ฝ | โค โค eโ 900 . For ๐ค โ ๐ฟ,
4 โ 20 |๐ท|
3 1
3/4,๐ฝ
conditioning on ๐ฃ โ ๐ฑ๐ increases the above probability by a factor of at most 1/๐ . That is,
3 1 1 ๐ผ0 ๐
Pr |๐ท โฉ ๐ฝ | โค โ |๐ท| ๐ฃ โ ๐ฑ๐ โค eโ 900 .
๐ฃ โผ ๐ค 4 20 ๐
3/4,๐ฝ
๐ผ0 ๐ ๐ผ0 ๐
The constant ๐ in is chosen to be small enough to promise that ๐1 eโ 900 = ๐ โ50 ยท eโ 900 โค ๐. That is,
|๐ฝ โฉ ๐ท| โฅ 34 โ 20
1
|๐ท| almost always.
If ๐ฝ is such that |๐ฝ โฉ ๐ท| โฅ 34 โ 20 |๐ท| , then a random ๐ โ ๐ท has probability of at least
4 โ 20
1 3 1
to be in ๐ฝ. Therefore,
3 1 3 1
Pr [๐ โ ๐ฝ | ๐ฃ โ ๐ฑ] โฅ Pr |๐ท โฉ ๐ฝ | โค โ |๐ท| ๐ฃ โ ๐ฑ๐ โ
๐ฃ โผ ๐ค,๐โ๐ท ๐ฃ โผ ๐ค 4 20 4 20
3/4,๐ฝ 3/4,๐ฝ
3 1 3 1
โฅ(1 โ ๐) โ > โ ,
4 20 4 10
which is a contradiction to the definition of ๐ท.
Proof of Lemma 3.12. Fix an excellent restriction ๐. Recall that for an excellent restriction ๐,
Pr๐คโ[๐]๐ดยฏ [๐ค โ ๐ฑ๐ ] โฅ ๐/2 and
๐ผ0 ๐
Pr ๐ค, ๐ฃ โ ๐ฑ๐ and โ(๐ค)๐ฝ 0 โ(๐ฃ)๐ฝ โค ๐ . (3.6)
๐ค,๐ฃ โผ ๐ค
3/4,๐ฝ
Let ๐ต be the set of โbadโ inputs,
( )
๐
๐ผ๐
๐ต = ๐ค โ ๐ฑ๐ Pr ๐ฃ โ ๐ฑ๐ and ๐๐ (๐ฃ)๐ฝ 0 ๐๐ (๐ค)๐ฝ โฅ .
๐ฃ โผ ๐ค 10
3/4,๐ฝ
By averaging on equation (3.6), Pr๐คโ๐ฑ๐ [๐ค โ ๐ต] โค ๐ โค 2๐ .
10๐ 1 3
Recall ๐ฟ is the set of lonely inputs. By Claim 3.16, Pr๐คโ[๐]๐ [๐ค โ ๐ฟ] โค ๐10 . Since ๐ is excellent,
๐ 10 ๐3
Pr [๐ค โ ๐ฟ] โค ๐ < .
๐คโ๐ฑ๐ 2 2
T HEORY OF C OMPUTING, Volume 19 (3), 2023, pp. 1โ56 20
E XPONENTIALLY S MALL S OUNDNESS FOR THE D IRECT P RODUCT Z- TEST
Together, the probability that a random ๐ค โ ๐ฑ๐ is in ๐ต or in ๐ฟ is smaller than ๐ 3 . Therefore,
๐ผ1 ๐
to prove the lemma it is enough to prove that for every ๐ค โ ๐ฑ๐ \ {๐ต โช ๐ฟ} , ๐๐ (๐ค) โ ๐ซ ๐๐ (๐ค).
Fix ๐ค โ ๐ฑ๐ \ (๐ต โช ๐ฟ). Denote by ๐ท the set of coordinates on which ๐๐ (๐ค), ๐ซ ๐๐ (๐ค) differ,
๐ท = ๐ โ ๐ดยฏ ๐๐ (๐ค)๐ โ ๐ซ ๐๐ (๐ค)๐ .
ยฏ
Assume for a contradiction that |๐ท| > ๐ผ1 ๐ . For ๐ฃ โ [๐]๐ด , ๐ฝ โ ๐ดยฏ and ๐ โ ๐ด,
ยฏ let ๐ธ(๐ฃ, ๐ฝ, ๐) be
the event
๐ โ ๐ฝ and ๐๐ (๐ค)๐ โ ๐๐ (๐ฃ)๐ .
We reach a contradiction by upper bounding and lower bounding the probability of ๐ธ under the
distribution ๐ โ ๐ท and ๐ฃ โผ ๐ค, given that ๐ฃ โ ๐ฑ๐ .
3/4,๐ฝ
Lower bound. The function ๐ซ ๐๐ takes the most common value ๐๐ (๐ฃ)๐ for ๐ฃ โผ ๐ค. By definition,
3/4,๐ฝ
the set ๐ท contains all of the coordinates ๐ such that ๐๐ (๐ค)๐ is not the most probable value ๐๐ (๐ฃ)๐ ,
when ๐ฃ โผ ๐ค. Therefore for every ๐ โ ๐ท,
3/4,๐ฝ
1
Pr [ ๐๐ (๐ค)๐ โ ๐๐ (๐ฃ)๐ | ๐ โ ๐ฝ, ๐ฃ โ ๐ฑ๐ ] โฅ . (3.7)
๐ฃ โผ ๐ค 2
3/4,๐ฝ
To lower bound the probability of ๐ธ we need to lower bound the probability of ๐ โ ๐ฝ. When
picking ๐ฃ โผ ๐ค, each ๐ is in ๐ฝ with probability 3/4 . From Claim 3.17, for all except ๐ผ0 ๐ coordinates,
3/4,๐ฝ
the probability of ๐ to be in ๐ฝ is not much different, it is at least 3/4 โ 1/10 . Let ๐ท 0 โ [๐] be the set
of coordinates in which Pr[๐ โ ๐ฝ] is lower than 3/4 โ 10 1
, then |๐ท 0 | โค ๐ผ0 ๐ < 1/10|๐ท| . Together
we get that
0 3 1 1
Pr [๐ โ ๐ฝ | ๐ฃ โ ๐ฑ๐ ] โฅ Pr [๐ โ ๐ท ] โ > .
๐โ๐ท,๐ฃ โผ ๐ค ๐โ๐ท 4 10 2
3/4,๐ฝ
From the two equations above,
Pr [๐ธ(๐ฃ, ๐ฝ, ๐) | ๐ฃ โ ๐ฑ๐ ] = Pr [๐ โ ๐ฝ and ๐๐ (๐ค)๐ โ ๐๐ (๐ฃ)๐ | ๐ฃ โ ๐ฑ๐ ]
๐ฃ โผ ๐ค,๐โ๐ท ๐ฃ โผ ๐ค,๐โ๐ท
3/4,๐ฝ 3/4,๐ฝ
= Pr [๐ โ ๐ฝ | ๐ฃ โ ๐ฑ๐ ] Pr [ ๐๐ (๐ค)๐ โ ๐๐ (๐ฃ)๐ | ๐ โ ๐ฝ, ๐ฃ โ ๐ฑ๐ ]
๐ฃ โผ ๐ค,๐โ๐ท ๐ฃ โผ ๐ค
3/4,๐ฝ 3/4,๐ฝ
1 1 1
> ยท = .
2 2 4
Upper Bound. For ๐ค โ ๐ฑ๐ \ (๐ต โช ๐ฟ) , the following two equations hold: Pr๐ฃ โผ ๐ค [๐ฃ โ ๐ฑ๐ ] โฅ ๐
3/4,๐ฝ
๐ผ0 ๐
๐
and Pr๐ฃ โผ ๐ค ๐ฃ โ ๐ฑ๐ and ๐๐ (๐ฃ)๐ฝ 0 ๐๐ (๐ค)๐ฝ โค 10 . Combining the two equations,
3/4,๐ฝ
๐ผ0 ๐
1
Pr ๐๐ (๐ฃ)๐ฝ 0 ๐๐ (๐ค)๐ฝ ๐ฃ โ ๐ฑ๐ โค . (3.8)
๐ฃ โผ ๐ค 10
3/4,๐ฝ
T HEORY OF C OMPUTING, Volume 19 (3), 2023, pp. 1โ56 21
I RIT D INUR AND I NBAL L IVNI NAVON
๐ผ0 ๐
Suppose ๐๐ (๐ฃ)๐ฝ โ ๐๐ (๐ค)๐ฝ , our assumption is that |๐ท| > ๐ผ1 ๐ = 10๐ผ0 ๐ , so a uniform ๐ โ ๐ท is
in the ๐ผ0 ๐ coordinates in which ๐๐ (๐ฃ)๐ฝ , ๐๐ (๐ค)๐ฝ differ with probability at most 10
1
. This lets us
bound the probability of ๐ธ:
๐ผ0 ๐
Pr [๐ธ(๐ฃ, ๐ฝ, ๐) | ๐ฃ โ ๐ฑ๐ ] โค Pr ๐๐ (๐ฃ)๐ฝ 0 ๐๐ (๐ค)๐ฝ ๐ฃ โ ๐ฑ๐
๐ฃ โผ ๐ค,๐โ๐ท ๐ฃ โผ ๐ค
3/4,๐ฝ 3/4,๐ฝ
๐ผ0 ๐
+ Pr ๐๐ (๐ฃ)๐ฝ โ ๐๐ (๐ค)๐ฝ and ๐ โ ๐ฝ and ๐๐ (๐ค)๐ โ ๐๐ (๐ฃ)๐ ๐ฃ โ ๐ฑ๐
๐ฃ โผ ๐ค,๐โ๐ท
3/4,๐ฝ
1 1 1
โค + < .
10 10 4
The upper and lower bounds contradict each other so for all ๐ค โ ๐ฑ๐ \ (๐ต โช ๐ฟ), |๐ท| โค ๐ผ1 ๐ and
๐ผ1 ๐
๐๐ (๐ค) โ ๐ซ ๐๐ (๐ค) . Since Pr๐ค [๐ค โ ๐ต โช ๐ฟ] โค ๐ 3 we finish the proof.
3.4 Direct product function
In this section we prove that ๐ซ ๐๐ is close to a direct product function, proving Lemma 3.13.
We start by defining the candidate direct product function, which is the plurality vote of
๐ซ ๐๐ .
ยฏ ยฏ
Definition 3.18. For every excellent ๐ = (๐ด, ๐, ๐พ), let ๐๐ : [๐]๐ด โ [๐]๐ด be the following function:
for every ๐ โ ๐ด and ๐ โ [๐],
๐๐,๐ (๐) = Plurality {๐ซ ๐๐ (๐ค)๐ } ,
๐คโ[๐]๐ดยฏ s.t. ๐ค ๐ =๐
ties are broken arbitrarily.
Set ๐ผ3 = 20๐ผ0 .
Claim 3.19. For every excellent ๐,
๐ผ3 ๐
Pr ๐ซ ๐๐ (๐ค)๐ฝ โ ๐ซ ๐๐ (๐ฃ)๐ฝ โฅ 1 โ 3๐10 .
๐คโ[๐]๐ดยฏ ,๐ฃ โผ ๐ค
1/2,๐ฝ
Proof. The proof is similar to the proof of Lemma 3.12. Its main idea is that if ๐ซ ๐๐ (๐ค) and ๐ซ ๐๐ (๐ฃ)
disagree on a lot of coordinates, then a large fraction of their 3/4-correlated neighborhoods also
disagree on a lot of coordinates. This can only happen for very few inputs ๐ค, ๐ฃ, otherwise we
contradict the fact that ๐ is excellent.
Fix an excellent ๐. Let ๐ถ be a set of โbadโ triplets,
๐ผ0 ๐ ๐2
0 0 0 0
๐ถ = (๐ค, ๐ฃ, ๐ฝ) ๐ค ๐ฝ = ๐ฃ ๐ฝ and Pr ๐ค , ๐ฃ โ ๐ฑ๐ and ๐๐ (๐ค )๐ฝห 0 ๐๐ (๐ฃ )๐ฝห โฅ ,
๐ค 0 ,๐ฝ 0 ,๐ฃ 0 ,๐ฝ 00 10
T HEORY OF C OMPUTING, Volume 19 (3), 2023, pp. 1โ56 22
E XPONENTIALLY S MALL S OUNDNESS FOR THE D IRECT P RODUCT Z- TEST
where ๐ค 0 โผ 0 ๐ค, ๐ฃ 0 โผ 00 ๐ฃ and ๐ฝห = ๐ฝ โฉ ๐ฝ 0 โฉ ๐ฝ 00.
3/4,๐ฝ 3/4,๐ฝ
ยฏ
If (๐ค, ๐ฃ, ๐ฝ) are distributed such that ๐ค is uniform in [๐]๐ด and ๐ฃ โผ ๐ค, then the marginal
1/2,๐ฝ
distribution over ๐ค 0 is uniform, and ๐ฃ 0 โผ ๐ค 0 . This is because for every ๐ independently, the
9/32, ๐ฝห
probability of ๐ to be in ๐ฝห = ๐ฝ โฉ ๐ฝ 0 โฉ ๐ฝ 00 is (3/4) 2 ยท (1/2) = 9/32 .
๐ผ0 ๐
Since ๐ is excellent, Pr๐ค0 โ[๐]๐ดยฏ ,๐ฃ0 โผ ๐ค0 ๐ค 0 , ๐ฃ 0 โ ๐ฑ๐ , ๐๐ (๐ค 0)๐ฝห 0 ๐๐ (๐ฃ 0)๐ฝห โค ๐. Therefore by
9/32, ๐ฝห
averaging, Pr๐คโ[๐]๐ดยฏ ,๐ฃ โผ ๐ค [(๐ค, ๐ฃ, ๐ฝ) โ ๐ถ] โค ๐2 < ๐10 .
10๐
1/2,๐ฝ
Recall that ๐ฟ is the set of โlonelyโ inputs, those with sparse neighborhood. From Claim 3.16,
Pr๐คโ[๐]๐ดยฏ [๐ค โ ๐ฟ] < ๐10 .
๐ผ3 ๐
We prove next that for every ๐ค, ๐ฃ, ๐ฝ such that (๐ค, ๐ฃ, ๐ฝ) โ ๐ถ and ๐ค, ๐ฃ โ ๐ฟ, ๐ซ ๐๐ (๐ค)๐ฝ โ ๐ซ ๐๐ (๐ฃ)๐ฝ .
This proves the claim since by a union bound argument,
Pr [(๐ค, ๐ฃ, ๐ฝ) โ ๐ถ or ๐ค โ ๐ฟ or ๐ฃ โ ๐ฟ]
๐คโ[๐]๐ดยฏ ,๐ฃ โผ ๐ค
1/2,๐ฝ
โค 2 Pr [๐ค โ ๐ฟ] + Pr [(๐ค, ๐ฃ, ๐ฝ) โ ๐ถ] โค 3๐ 10 .
๐คโ[๐]๐ดยฏ ๐คโ[๐]๐ดยฏ ,๐ฃ โผ ๐ฃ
1/2,๐ฝ
Fix ๐ค, ๐ฃ, ๐ฝ such that ๐ค ๐ฝ = ๐ฃ ๐ฝ , ๐ค, ๐ฃ โ ๐ฟ and (๐ค, ๐ฃ, ๐ฝ) โ ๐ถ. Let ๐ท โ ๐ฝ be the set
๐ท = {๐ โ ๐ฝ | ๐ซ ๐๐ (๐ค)๐ โ ๐ซ ๐๐ (๐ฃ)๐ } .
Assume for a contradiction that |๐ท| โฅ ๐ผ3 ๐.
ยฏ ๐ค 0 , ๐ฃ 0 โ ๐ฑ and ๐ โ ๐ด,
For every ๐ฝ 0 , ๐ฝ 00 โ ๐ด, ยฏ let ๐ธ(๐ฝ 0 , ๐ฝ 00 , ๐ค 0 , ๐ฃ 0 , ๐) be the following event:
๐๐ (๐ค 0)๐ โ ๐๐ (๐ฃ 0)๐ and ๐ โ ๐ฝ 0 โฉ ๐ฝ 00 .
We reach a contradiction by giving an upper bound and a lower bound of this event, under the
distribution ๐ โ ๐ท, ๐ค 0 โผ 0 ๐ค and ๐ฃ 0 โผ 00 ๐ฃ, given that ๐ค 0 , ๐ฃ 0 โ ๐ฑ๐ .
3/4,๐ฝ 3/4,๐ฝ
Lower Bound. For every ๐ โ ๐ท, ๐ซ ๐๐ (๐ค)๐ โ ๐ซ ๐๐ (๐ฃ)๐ , i. e., the most frequent value ๐๐ (๐ค 0)๐ for
๐ค 0 โผ ๐ค is different from the most frequent value ๐๐ (๐ฃ 0)๐ for ๐ฃ 0 โผ ๐ฃ . Therefore, for every ๐ โ ๐ท,
3/4 3/4
1
Pr [ ๐๐ (๐ค 0)๐ โ ๐๐ (๐ฃ 0)๐ | ๐ โ ๐ฝ 0 โฉ ๐ฝ 00 , ๐ค 0 , ๐ฃ 0 โ ๐ฑ๐ ] โฅ , (3.9)
๐ค 0 ,๐ฝ 0 ,๐ฃ 0 ,๐ฝ 00 2
where ๐ค 0 โผ 0 ๐ค and ๐ฃ 0 โผ 00 ๐ฃ .
3/4,๐ฝ 3/4,๐ฝ
To finish the lower bound, we need to lower bound the probability of ๐ โ ๐ฝ 0 โฉ ๐ฝ 00 , for ๐ค 0 โผ 0 ๐ค
3/4,๐ฝ
and ๐ฃ 0 โผ 00 ๐ฃ given that ๐ค 0 , ๐ฃ 0 โ ๐ฑ๐ . Without conditioning on ๐ค 0 , ๐ฃ 0 โ ๐ฑ๐ , each ๐ is in ๐ฝ 0 โฉ ๐ฝ 00
3/4,๐ฝ
with probability (3/4)2 . We show that the probability is not much lower even when conditioning
T HEORY OF C OMPUTING, Volume 19 (3), 2023, pp. 1โ56 23
I RIT D INUR AND I NBAL L IVNI NAVON
on ๐ค 0 , ๐ฃ 0 โ ๐ฑ๐ . From Claim 3.17, for all except ๐ผ0 ๐ of the coordinates ๐ โ ๐ด, ยฏ the probability of ๐
to be in ๐ฝ is at least 3/4 โ 1/10 . Let ๐ท๐ฝ 0 be the set of coordinates such that Pr[๐ โ ๐ฝ 0] โค 34 โ 10
0 1
and let ๐ท๐ฝ 00 be the equivalent set for ๐ฝ . Then |๐ท \ (๐ท๐ฝ 0 โช ๐ท๐ฝ 00 )| โฅ 20๐ผ 0 ๐ โ ๐ผ0 ๐ โ ๐ผ0 ๐ .
00
2
0 00
3 1 1
[๐ โ ๐ฝ โฉ ๐ฝ ] โฅ Pr ๐ โ ๐ท โฉ ๐ท > .
Pr ๐ฝ0 ๐ฝ 00 โ
๐โ๐ท,๐ค 0 โผ ๐ค,๐ฃ 0 โผ ๐ฃ ๐โ๐ท 4 10 3
3/4,๐ฝ 0 3/4,๐ฝ 00
Combining the two equations, we lower bound the probability of ๐ธ, under the distribution
๐ โ ๐ท, ๐ค 0 โผ 0 ๐ค and ๐ฃ 0 โผ 00 ๐ฃ,
3/4,๐ฝ 3/4,๐ฝ
Pr [๐ธ(๐ฝ 0 , ๐ฝ 00 , ๐ค 0 , ๐ฃ 0 , ๐) | ๐ค 0 , ๐ฃ 0 โ ๐ฑ๐ ] = Pr [๐ โ ๐ฝ 0 โฉ ๐ฝ 00 | ๐ค 0 , ๐ฃ 0 โ ๐ฑ๐ ]
๐,๐ค 0 ,๐ฝ 0 ,๐ฃ 0 ,๐ฝ 00 ๐,๐ค 0 ,๐ฝ 0 ,๐ฃ 0 ,๐ฝ 00
ยท Pr [ ๐๐ (๐ค 0)๐ โ ๐๐ (๐ฃ 0)๐ | ๐ค 0 , ๐ฃ 0 โ ๐ฑ๐ , ๐ โ ๐ฝ 0 โฉ ๐ฝ 00]
๐,๐ค 0 ,๐ฝ 0 ,๐ฃ 0 ,๐ฝ 00
1 1 1
โฅ ยท โฅ .
3 2 6
Upper Bound. The fixed ๐ค, ๐ฃ, ๐ฝ satisfy Pr๐ฃ0 โผ ๐ฃ [๐ฃ 0 โ ๐ฑ๐ ] โฅ ๐ and
3/4,๐ฝ 00
๐ผ0 ๐ ๐2
0 0 0 0
Pr 0 ๐ค , ๐ฃ โ ๐ฑ๐ and ๐๐ (๐ค )๐ฝห 0 ๐๐ (๐ฃ )๐ฝห โค ,
๐ค 0 โผ ๐ค,๐ฃ โผ ๐ฃ 10
3/4,๐ฝ 0 3/4,๐ฝ 00
where ๐ฝห = ๐ฝ โฉ ๐ฝ 0 โฉ ๐ฝ 00 .
Therefore,
๐ผ0 ๐
0 0 0 0 1
Pr ๐๐ (๐ค )๐ฝห 0 ๐๐ (๐ฃ )๐ฝห ๐ค , ๐ฃ โ ๐ฑ๐ โค .
๐ค 0 โผ ๐ค,๐ฃ 0 โผ ๐ฃ 10
3/4,๐ฝ 0 3/4,๐ฝ 00
๐ผ0 ๐
If ๐๐ (๐ค 0)๐ฝห โ ๐๐ (๐ฃ 0)๐ฝห , then a uniform ๐ โ ๐ท has probability of at most ๐ผ|๐ท|
0๐ ๐ผ0 ๐
โค 20๐ผ 0๐
โค 1/20 to
be in a coordinate in which ๐๐ (๐ค ), ๐๐ (๐ฃ ) differ. Therefore,
0 0
1 1 1
Pr [๐ธ(๐ฝ 0 , ๐ฝ 00 , ๐ค 0 , ๐ฃ 0 , ๐) | ๐ค 0 , ๐ฃ 0 โ ๐ฑ๐ ] โค + < ,
๐โ๐ท,๐ค 0 โผ ๐ค,๐ฃ 0 โผ ๐ฃ 10 20 6
3/4,๐ฝ 0 3/4,๐ฝ 00
which contradicts the lower bound. This completes the proof of Claim 3.19.
Claim 3.20. For every excellent ๐,
Pr [๐ซ ๐๐ (๐ค)๐ = ๐ซ ๐๐ (๐ฃ)๐ | ๐ค ๐ = ๐ฃ ๐ ] โฅ 1 โ 10๐ผ 3 .
๐ด ยฏ
ยฏ
๐โ ๐ด,๐ค,๐ฃโ[๐]
Proof. Fix an excellent ๐. Claim 3.19 proves the agreement of ๐ซ ๐๐ on correlated inputs. In this
claim, we prove its agreement on uncorrelated inputs.
ยฏ
Let ๐ 0 be the distribution of picking ๐ข, ๐ฃ, ๐ค โ [๐]๐ด and ๐ โ ๐ดยฏ defined as follows.
T HEORY OF C OMPUTING, Volume 19 (3), 2023, pp. 1โ56 24
E XPONENTIALLY S MALL S OUNDNESS FOR THE D IRECT P RODUCT Z- TEST
1. Pick a uniform ๐ โ ๐ดยฏ .
ยฏ
2. Pick uniform ๐ค, ๐ฃ โ [๐]๐ด such that ๐ค ๐ = ๐ฃ ๐ .
3. For every ๐ โ ๐, insert ๐ into ๐ฝ with probability 12 independently.
(
๐ค๐ ๐โ๐ฝ
4. For every ๐ โ ๐ดยฏ set ๐ข ๐ = .
๐ฃ๐ else
The distribution ๐ 0 produces ๐ค, ๐ฃ that are uncorrelated except that ๐ค ๐ = ๐ฃ ๐ . The pair ๐ค, ๐ข are
nearly 1/2-correlated (the only difference is the coordinate ๐ in which ๐ข๐ = ๐ค ๐ with probability 1).
We prove the claim by applying Claim 3.19 on the correlated pairs ๐ข, ๐ค and ๐ข, ๐ฃ, and get that with
high probability ๐ซ ๐๐ (๐ข)๐ = ๐ซ ๐๐ (๐ค)๐ and ๐ซ ๐๐ (๐ข)๐ = ๐ซ ๐๐ (๐ฃ)๐ , deducing that ๐ซ ๐๐ (๐ค)๐ = ๐ซ ๐๐ (๐ฃ)๐ .
The marginal distribution on ๐ค, ๐ข in ๐ 0 is very close to 1/2-correlated. The only difference
between the marginal distribution of ๐ค, ๐ข, ๐ฝ, ๐ โผ ๐ 0 and ๐ข โผ ๐ค is that in ๐ 0 , ๐ค ๐ = ๐ข๐ with
1/2
probability 1 and not 1/2 . In Claim 3.23 we prove that the probability of any event on ๐ข โผ ๐ค
1/2,๐ฝ
can increase by at most a factor of 2, for ๐ข, ๐ค, ๐ฝ โช {๐} produced by ๐ 0 .
Therefore, we can use Claim 3.19 on ๐ค, ๐ข, ๐ฝ, ๐ โผ ๐ 0 and pay a factor of 2,
๐ผ3 ๐
Pr ๐ซ ๐๐ (๐ค)๐ฝโช{๐} 0 ๐ซ ๐๐ (๐ข)๐ฝโช{๐} โค2 ยท 3๐ 10 . (3.10)
๐ค,๐ข,๐ฝ,๐โผ๐ 0
The same holds also for ๐ฃ, ๐ข, ๐ดยฏ \ ๐ฝ, ๐ โผ ๐ 0 .
For ๐ค, ๐ข, ๐ฝ, ๐ โผ ๐ 0 ,the coordinate ๐ is a random coordinate in ๐ฝ โช {๐}. Therefore, if
๐ผ3 ๐
๐ซ ๐๐ (๐ค)๐ฝโช{๐} โ ๐ซ ๐๐ (๐ข)๐ฝโช{๐} , then the probability of ๐ be be such that ๐ซ ๐๐ (๐ค)๐ โ ๐ซ ๐๐ (๐ข)๐ is
๐ผ3 ๐
at most |๐ฝโช{๐}| . Each ๐ โ ๐ is in ๐ฝ with probability 1/2 independently, which lets us bound the
1 1 ยฏ
| ๐ด|
size of ๐ฝ by the Chernoff bound, Pr๐ฝ [|๐ฝ | < ๐/4] โค e 3ยท52 2 < ๐ . If |๐ฝ | > ๐/4 , then the probability
of a random ๐ โ ๐ฝ to fall into the ๐ผ 3 ๐ disagreeing coordinates is at most 4๐ผ3 ๐ . Therefore,
๐ ๐ผ3 ๐
Pr [๐ซ ๐๐ (๐ค)๐ โ ๐ซ ๐๐ (๐ข)๐ ] โค Pr |๐ฝ | < or ๐ซ ๐๐ (๐ค)๐ฝโช{๐} 0 ๐ซ ๐๐ (๐ข)โช{๐}
๐ค,๐ข,๐ฝ,๐โผ๐ 0 ๐ค,๐ข,๐ฝ,๐โผ๐ 0 4
+ 4๐ผ3 ๐ โค 6๐10 + ๐ + 4๐ผ3 ๐ < 5๐ผ3 ๐. (3.11)
The same holds also for ๐ฃ, ๐ข, ๐ดยฏ \ ๐ฝ, ๐ .
Therefore, from equation (3.11) on ๐ค, ๐ข, ๐ฝ, ๐ and ๐ฃ, ๐ข, ๐ดยฏ \ ๐ฝ, ๐,
Pr [๐ซ ๐๐ (๐ค)๐ = ๐ซ ๐๐ (๐ฃ)๐ | ๐ค ๐ = ๐ฃ ๐ ] โฅ Pr [๐ซ ๐๐ (๐ค)๐ = ๐ซ ๐๐ (๐ฃ)๐ = ๐ซ ๐๐ (๐ข)๐ ]
๐โ ๐ดยฏ ๐,๐ค,๐ฃ,๐ขโผ๐ 0
ยฏ
๐ค,๐ฃโ[๐]๐ด
โฅ1 โ 5๐ผ3 โ 5๐ผ3 .
T HEORY OF C OMPUTING, Volume 19 (3), 2023, pp. 1โ56 25
I RIT D INUR AND I NBAL L IVNI NAVON
Claim 3.21. For every excellent ๐,
Pr [๐ซ ๐๐ (๐ค)๐ = ๐๐ (๐ค)๐ ] โฅ 1 โ 20๐ผ3 .
๐คโ[๐]๐ดยฏ ,๐โ ๐ดยฏ
Proof. Fix an excellent ๐. The function ๐๐ is defined as the plurality of ๐ซ ๐๐ . This means that
ยฏ
for every ๐ค โ [๐]๐ด and ๐ โ ๐ด,ยฏ if ๐ซ ๐๐ (๐ค)๐ โ ๐๐ (๐ค)๐ , then ๐ซ ๐๐ (๐ค)๐ is not the most frequent value
๐ซ ๐๐ (๐ฃ)๐ among all ๐ฃ such that ๐ฃ ๐ = ๐ค ๐ , i. e., Pr๐ฃโ[๐]๐ดยฏ [๐ซ ๐๐ (๐ค)๐ = ๐ซ ๐๐ (๐ฃ)๐ |๐ค ๐ = ๐ฃ ๐ ] โค 1/2 .
This implies that
1
Pr [๐ซ ๐๐ (๐ค)๐ โ ๐ซ ๐๐ (๐ฃ)๐ | ๐ค ๐ = ๐ฃ ๐ ] โฅ Pr [๐ซ ๐๐ (๐ค)๐ โ ๐๐ (๐ค)๐ ] .
๐ค,๐ฃโ[๐]๐ดยฏ ,๐โ ๐ดยฏ 2 ๐คโ[๐]๐ด ,๐โ๐ดยฏ
Therefore, by Claim 3.20,
Pr [๐ซ ๐๐ (๐ค)๐ โ ๐๐ (๐ค)๐ ] โค 20๐ผ3 ๐ .
๐คโ[๐]๐ด ,๐โ ๐ดยฏ
ยฏ
Proof of Lemma 3.13. Fix an excellent ๐. For every ๐ค โ [๐]๐ด , let ๐ท๐ค โ ๐ดยฏ be the set of coordinates
๐ท๐ค = ๐ โ ๐ดยฏ ๐๐ (๐ค)๐ โ ๐ซ ๐๐ (๐ค)๐ .
ยฏ
Let ๐ถ โ [๐]๐ด be the set of inputs in which ๐๐ is close to ๐ซ ๐๐ ,
n o
ยฏ
๐ถ = ๐ค โ [๐]๐ด |๐ท๐ค | โค 25๐ผ3 ๐ .
By Claim 3.21 and averaging, Pr๐ค [๐ค โ ๐ถ] โฅ 1/5 .
ยฏ
Let ๐ต โ [๐]๐ด be the set of inputs in which ๐๐ , ๐ซ ๐๐ are far from each other,
๐ต = ๐ค โ [๐] ๐
0
|๐ท๐ค | โฅ ๐ผ2 ๐ .
Notice that ๐ต โฉ ๐ถ = ๐ but there can be inputs that are neither in ๐ต nor in ๐ถ (because ๐ผ 2 = 1500๐ผ 0
and ๐ผ3 = 20๐ผ0 ).
By Corollary 2.9,
1
[๐ค โ ๐ต, ๐ฃ โ ๐ถ] โฅ Pr [๐ฃ โ ๐ถ] 2 Pr [๐ค โ ๐ต] 2 โฅ Pr [๐ค โ ๐ต] 2 .
3 5 5
Pr
๐ค,๐ฃ โผ ๐ค ๐ฃโ[๐]๐ดยฏ ๐คโ[๐]๐ดยฏ ยฏ
12 ๐คโ[๐]๐ด
1/2,๐ฝ
We will show that ๐ซ ๐๐ has large disagreement on almost every 12 -correlated pair ๐ค, ๐ฃ such that
๐ค โ ๐ต, ๐ฃ โ ๐ถ, which lets us bound the size of ๐ต.
Typically, for ๐ฃ โผ ๐ค, we get that |๐ฝ โฉ ๐ท๐ค | โ |๐ท๐ค |/2 . The probability of |๐ฝ โฉ ๐ท๐ค | โฅ
1/2,๐ฝ
(1/2 โ 1/10) |๐ท๐ค | is nearly 1, by the Chernoff bound, Pr๐ฃ โผ ๐ค [|๐ฝ โฉ ๐ท๐ค | < (1/2 โ 1/10) |๐ท๐ค |] โค
1/2,๐ฝ
1 1
|๐ท๐ค |
e 3ยท52 2 .
T HEORY OF C OMPUTING, Volume 19 (3), 2023, pp. 1โ56 26
E XPONENTIALLY S MALL S OUNDNESS FOR THE D IRECT P RODUCT Z- TEST
๐ผ3 ๐
If ๐ค โ ๐ต and ๐ฃ โ ๐ถ and |๐ฝ โฉ๐ท๐ค | โฅ (1/2 โ 1/10) |๐ท๐ค | , it must be that ๐ซ ๐๐ (๐ค)๐ฝ 0 ๐ซ ๐๐ (๐ฃ)๐ฝ . This
25๐ผ 3 ๐
is because for ๐ฃ โ ๐ถ, ๐ซ ๐๐ (๐ฃ)๐ฝ โ ๐๐ (๐ค)๐ฝ . For ๐ค โ ๐ต, |๐ท๐ค | โฅ ๐ผ2 ๐, if |๐ฝ โฉ ๐ท๐ค | โฅ (1/2 โ 1/10) ๐ผ2 ๐,
30๐ผ 3 ๐
then |๐ฝ โฉ ๐ท๐ค | โฅ 30๐ผ3 ๐, i. e., ๐ซ ๐๐ (๐ค)๐ฝ 0 ๐๐ (๐ค)๐ฝ . The function ๐๐ is a product function,
30๐ผ3 ๐ 25๐ผ3 ๐
so ๐๐ (๐ค)๐ฝ = ๐๐ (๐ฃ)๐ฝ . So if ๐ซ ๐๐ (๐ค)๐ฝ 0 ๐๐ (๐ค)๐ฝ and ๐ซ ๐๐ (๐ฃ)๐ฝ โ ๐๐ (๐ค)๐ฝ , it must be that
๐ผ3 ๐
๐ซ ๐๐ (๐ค)๐ฝ 0 ๐ซ ๐๐ (๐ฃ)๐ฝ .
From the two equations above,
1 1 1
๐ค โ ๐ต, ๐ฃ โ ๐ถ and |๐ฝ โฉ ๐ท๐ค | โฅ Pr [๐ค โ ๐ต] 2 โ eโ๐ผ0 ๐ . (3.12)
5
Pr โ |๐ท๐ค | โฅ
๐คโ[๐]๐ดยฏ ,๐ฃ โผ ๐ค 2 10 ยฏ
12 ๐คโ[๐]๐ด
1/2,๐ฝ
๐ผ3 ๐
That is, Pr๐คโ[๐]๐ดยฏ ,๐ฃ โผ ๐ค ๐ซ ๐๐ (๐ค)๐ฝ 0 ๐ซ ๐๐ (๐ฃ)๐ฝ โฅ 12 Pr๐คโ[๐]๐ดยฏ [๐ค โ ๐ต] 2 โ eโ๐ผ๐ .
1 5
1/2,๐ฝ
๐ผ3 ๐
From Claim 3.19, Pr๐คโ[๐]๐ดยฏ ,๐ฃ โผ ๐ค ๐ซ ๐๐ (๐ค)๐ฝ 0 ๐ซ ๐๐ (๐ฃ)๐ฝ โค 3๐ 10 . Therefore,
1/2,๐ฝ
1
Pr [๐ค โ ๐ต] 2 โ eโ๐ผ๐ โค 3๐ 10 .
5
(3.13)
12 ๐คโ[๐]๐ดยฏ
This means that Pr๐คโ[๐]๐ดยฏ [๐ค โ ๐ต] โค 3๐ 4 , and completes the proof of Lemma 3.13.
Finally, we are left with proving the following claim, relating the standard 1/2-correlated
distribution to an almost correlated version in which one extra random coordinate is identical.
ยฏ
Definition 3.22. For every ๐ฅ โ [๐]๐ด , we say that ๐ฆ is almost 1/2-correlated with ๐ฅ, denoted by
๐ฆ โผ ๐ฅ i it is chosen by the following process:
1/2,๐ฝ ๐ด
โข Choose a uniform ๐ โ ๐ดยฏ and set ๐ฝ = {๐}.
โข Insert any ๐ โ ๐ into ๐ฝ with probability 1/2 independently.
โข Set ๐ฆ ๐ฝ = ๐ฅ ๐ฝ , set the rest of ๐ฆ to be uniform.
ยฏ
Claim 3.23. For any event ๐ธ(๐ฆ, ๐ฅ, ๐ฝ) over ๐ฅ, ๐ฆ โ [๐]๐ด and ๐ฝ โ ๐ด,
ยฏ
Pr [๐ธ(๐ฆ, ๐ฅ, ๐ฝ)] โค 2 Pr [๐ธ(๐ฆ, ๐ฅ, ๐ฝ)] .
๐ฆ โผ ๐ฅ ๐ฆโ[๐] ๐ ,๐ฅ โผ ๐ฆ
1/2,๐ฝ ๐ด 1/2,๐ฝ
Proof. Fix ๐ธ(๐ฅ, ๐ฆ, ๐ฝ) to be any event. For every ๐ฅ โ [๐] ๐ , let ๐ต ๐ฅ contain the tuples (๐ฅ, ๐ฝ) such that
๐ธ(๐ฅ, ๐ฆ, ๐ฝ) happens.
Fix ๐ฅ โ [๐] ๐ . For each (๐ฆ, ๐ฝ) โ ๐ต ๐ฆ , by the definition of 12 -correlation,
|๐ฝ | ๐โ|๐ฝ | ๐โ|๐ฝ |
0 1 1 1
Pr [(๐ง, ๐ฝ ) = (๐ฆ, ๐ฝ)] = .
๐ง โผ ๐ฅ
0
2 2 ๐
1/2,๐ฝ
T HEORY OF C OMPUTING, Volume 19 (3), 2023, pp. 1โ56 27
I RIT D INUR AND I NBAL L IVNI NAVON
For ๐ง, ๐ฝ 0 that are almost 12 -correlated to ๐ฆ:
|๐ฝ |โ1 ๐โ|๐ฝ | ๐โ|๐ฝ |
0 |๐ฝ | 1 1 1
Pr [(๐ง, ๐ฝ ) = (๐ฅ, ๐ฝ)] = .
๐ง โผ ๐ฅ
0๐ด
๐ 2 2 ๐
1/2,๐ฝ
Therefore,
Pr [(๐ง, ๐ฝ 0) = (๐ฅ, ๐ฝ)] โค 2 Pr [(๐ง, ๐ฝ 0) = (๐ฅ, ๐ฝ)] .
๐ง โผ ๐ฆ ๐ง โผ ๐ฆ
1/2,๐ฝ 0๐ด 1/2,๐ฝ 0
This implies that
[๐ธ(๐ฆ, ๐ฅ, ๐ฝ)] = (๐ฅ, ๐ฝ) โ ๐ต ๐ฆ โค 2 (๐ฅ, ๐ฝ) โ ๐ต ๐ฆ ,
Pr Pr Pr
๐ฆโ[๐] ๐ ,๐ฅ โผ ๐ฆ ๐ฆโ[๐] ๐ ,๐ฅ โผ ๐ฆ ๐ฆโ[๐] ๐ ,๐ฅ โผ ๐ฆ
1/2,๐ฝ ๐ด 1/2,๐ฝ ๐ด 1/2,๐ฝ
which finishes the proof.
4 Global structure for sets
Up until now we have considered functions ๐ : [๐] ๐ โ [๐] ๐ whose inputs are ordered tuples
(๐ฅ 1 . . . , ๐ฅ ๐ ) โ [๐] ๐ . We now move to consider functions ๐ : [๐] โ [๐] ๐ whose inputs are
๐
unordered sets {๐ฅ 1 , . . . , ๐ฅ ๐ } โ [๐] . In this setting assume that ๐ ๐ (for tuples no such
๐
assumption is made).
To each subset ๐ = {๐ 1 , . . . , ๐ ๐ } the function ๐ assigns ๐ (๐) โ [๐] ๐ . We view ๐ (๐) as a โlocal
functionโ on ๐, assigning a value in [๐] to every ๐ โ ๐. We denote by ๐ (๐)๐ the value that ๐ (๐)
assigns to ๐. For a subset ๐ โ ๐, we denote by ๐ (๐)๐ the outputs of ๐ corresponding to the
elements in ๐.
There are straightforward analogs to Theorem 1.1 and Theorem 3.9 which we present and
prove in this section. Interestingly, in the case of sets deducing global structure from restricted
global structure is quite easier than it is for tuples.
First, let us present the Z-test for sets from [13] when ๐ก = ๐/10 . Let agr๐๐/10 ๐ ๐๐ก
( ๐ ) be the success
probability of this test. This is the same test as Test 3 from the introduction with ๐ก = ๐/10 .
For convenience, we write again Theorem 1.5 from the introduction.
Theorem 4.1 (Global Structure for Sets, restated). There exist a small constant ๐ > 0, such that for
every constant ๐ > 0, large enough ๐ โ โ and ๐ > e๐๐๐ , ๐ โ โ , if the function ๐ : [๐] โ [๐] ๐
๐
passes Test 3 with probability agr๐๐/10
๐ ๐๐ก
( ๐ ) = ๐ > eโ๐๐๐ , then there exists a function ๐ : [๐] โ [๐] such
that
๐๐
Pr ๐ (๐) โ ๐(๐) โฅ ๐ โ 4๐ 2 .
๐
To prove the theorem, we first โtranslateโ the restricted global structure theorem for tuples
to a theorem on sets, and then use it to prove the global structure.
T HEORY OF C OMPUTING, Volume 19 (3), 2023, pp. 1โ56 28
E XPONENTIALLY S MALL S OUNDNESS FOR THE D IRECT P RODUCT Z- TEST
Test 4: Z-test for functions over sets, with ๐ก = ๐/10 (3-query test)
1. Choose a random set ๐ โ [๐] of size ๐/10 .
๐ ๐
2. Choose random ๐ , ๐ , ๐ , ๐ โ [๐], such that
|๐ | = |๐ | = ๐/10 , |๐ | = |๐| = 9๐/10 and
๐ โฉ๐ = ๐ โฉ๐ = ๐ โฉ๐ = โ
.
๐ ๐
3. Accept if ๐ (๐ โช ๐)๐ = ๐ (๐ โช ๐)๐ and
๐ (๐ โช ๐)๐ = ๐ (๐ โช ๐)๐ .
Denote by agr๐๐/10
๐ ๐๐ก
( ๐ ) the success probability of ๐ on this test.
4.1 Restricted global structure for sets
We define analogous definitions for good restrictions and DP
restrictions
for functions on sets.
To make the reduction proof simpler, we use a constant ๐ โ 1 โ ๐ /๐ , 1 (i. e., almost 1). Fix a
2
function ๐ : [๐] โ [๐] ๐ such that agr๐๐/10
๐ ๐๐ก
( ๐ ) = ๐ > eโ๐๐๐ .
๐
Definition 4.2 (Good pair). A pair ๐ , ๐ โ [๐], |๐ | = 9๐/10, |๐ | = ๐/10, ๐ โฉ ๐ = โ
is good if
๐
Pr [ ๐ (๐ โช ๐)๐ = ๐ (๐ โช ๐)๐ | ๐ โฉ ๐ = โ
] > ๐.
๐ 2
Definition 4.3 (๐ผ-DP pair). A pair ๐ , ๐ โ [๐], |๐ | = 9๐/10, |๐ | = ๐/10, ๐ โฉ ๐ = โ
is an ๐ผ-DP
pair if it is good, and if there exists a function ๐ ๐ ,๐ : [๐] โ [๐] such that
3๐ผ๐
Pr ๐ (๐ โช ๐)๐ 0 ๐ ๐ ,๐ (๐) ๐ โฉ ๐ = โ
, ๐ (๐ โช ๐)๐ = ๐ (๐ โช ๐)๐ โค 2๐ 2 .
๐
Notice that in the case of a function on sets, there is a single function ๐ ๐ ,๐ : [๐] โ [๐],
instead of 9๐/10 different functions in the case of tuples.
Lemma 4.4 (Restricted global structure for sets). There exists a small constants ๐ > 0, such that for
every constant ๐ผ > 0, large enough ๐ โ โ and ๐ > e๐๐๐ , ๐ โ โ , the following holds.
For every function ๐ : [๐] โ [๐] ๐ , if agr๐๐/10
๐ ๐๐ก
( ๐ ) = ๐ > eโ๐๐ผ๐ , then at least (1 โ ๐ 2 โ ๐ 2 /๐) of
๐
the good pairs ๐ , ๐ are ๐ผ-DP pairs.
This lemma is an analog to Theorem 3.9, and we prove it by a reduction from it. For every
๐ : [๐] โ [๐] ๐ we define a function ๐ 0 : [๐] ๐ โ [๐] ๐ โช โฅ that equals โฅ if the input has two
๐
identical coordinates, and identifies with ๐ everywhere else. For ๐ ๐, almost all inputs donโt
have two identical coordinates, and ๐ 0 , ๐ are equal on these inputs.
Using Theorem 3.9, we derive a restricted global structure on ๐ 0 . Since ๐ equals ๐ 0 almost
always, we find an equivalence between an ๐ผ-DP pair ๐ , ๐ to an ๐ผ-DP restriction ๐. For every
๐ผ-DP restriction ๐ we have the direct product function ๐๐ = (๐ ๐ )๐โ๐ดยฏ , ๐ ๐ : [๐] โ [๐]. We build
T HEORY OF C OMPUTING, Volume 19 (3), 2023, pp. 1โ56 29
I RIT D INUR AND I NBAL L IVNI NAVON
a restricted global function ๐ ๐ ,๐ : [๐] โ [๐] by taking the most frequent value among the
functions (๐ ๐ )๐โ๐ดยฏ . Note that even though ๐ 0 is permutation invariant, the functions (๐ ๐ )๐โ๐ดยฏ are
not necessarily identical.
Since the proof is technical, and its main points are described in the paragraph above, we
defer it to Appendix A.
4.2 Global structure for sets
The proof is very similar to the proof of lemma 3.16 in [13].
Proof of Theorem 1.5. Fix a function ๐ : [๐] โ [๐] ๐ that passes Test 4 with probability ๐, denote
๐
๐ผ = ๐/5 . Let ๐ , ๐ โ [๐] be the subsets chosen on Test 4.
If Pr๐ [ ๐ (๐ โช ๐)๐ = ๐ (๐ โช ๐)๐ | ๐ โฉ ๐ = โ
] < 2๐ ๐ , then the test rejects with probability at
least 1 โ 2๐ ๐ . The function ๐ passes the test with probability ๐, so the test must succeed with
probability at least ๐ on ๐ , ๐ such that Pr๐ [ ๐ (๐ โช ๐)๐ = ๐ (๐ โช ๐)๐ | ๐ โฉ ๐ = โ
] > 2๐ ๐ , i. e.,
on good pairs.
Using Lemma 4.4, at least (1 โ 2๐ 2 โ ๐ 2 /๐) of the good pairs are ๐ผ-DP pairs. Fix an ๐ผ-DP
pair ๐ , ๐, and let ๐ = ๐ ๐ ,๐ : [๐] โ [๐] be the direct product function associated with ๐ , ๐.
Let ๐ฑ be all the sets ๐ that are consistent with ๐ , ๐,
[๐]
๐ฑ= ๐โ ๐ โฉ ๐ = โ
, ๐ (๐ โช ๐)๐ = ๐ (๐ โช ๐)๐ .
9๐/10
We use the third query to show that this ๐ is in fact a global direct product function which is
close to ๐ , i.e that ๐ (๐) โ ๐(๐) for about an ๐-fraction of the sets ๐ โ [๐]
๐
.
Let ๐ถ be the set of inputs for which ๐ , ๐ are close,
[๐] ๐๐
๐ถ= ๐โ ๐ (๐) โ ๐(๐) .
๐
Suppose that instead of running Test 4 as is, we choose ๐, ๐ by the following process:
[๐]
1. Choose a uniform ๐ โ ๐
.
2. Choose ๐ to be a uniform 9๐/10 subset of ๐.
3. Set ๐ = ๐ \ ๐ and return (๐, ๐).
If the process outputs ๐ such that ๐ โฉ ๐ โ โ
, we assume that the test rejects. The probability of
this event is less than ๐ 2 /๐ , and if it does not happen, the process generates the test distribution.
Therefore, ๐ passes the test where ๐, ๐ are chosen using the above process with probability
at least ๐ โ ๐ 2 /๐ . We prove the claim by proving that conditioning on ๐ โ ๐ถ, the success
probability of the test is much lower than ๐. We deduce that the probability of ๐ โ ๐ถ must be
close to ๐.
The test passes if ๐ โ ๐ฑ and ๐ (๐ โช ๐)๐ = ๐ (๐ โช ๐)๐ . We prove that for ๐ โ ๐ถ, with high
3๐ผ๐ 3๐ผ๐
probability both ๐ (๐ โช ๐)๐ 0 ๐(๐) and ๐ (๐ โช ๐)๐ โ ๐(๐), and the test fails.
T HEORY OF C OMPUTING, Volume 19 (3), 2023, pp. 1โ56 30
E XPONENTIALLY S MALL S OUNDNESS FOR THE D IRECT P RODUCT Z- TEST
3๐ผ๐
1. If ๐ โ ๐ฑ, the test fails. For every ๐ โ ๐ฑ, Lemma 4.4 states that ๐ (๐ โช ๐)๐ โ ๐(๐) with
probability 1 โ 2๐ 2 . Conditioning on ๐ โ ๐ถ does not increase the probability by much
(where we assume that ๐ถ is small, else there is nothing to prove),
3๐ผ๐ 1
Pr ๐ (๐ โช ๐)๐ 0 ๐(๐) ๐ โ ๐ฑ, ๐ โ ๐ถ โค 2๐ 2 โค 3๐ 2 . (4.1)
๐ Pr[๐ โ ๐ถ]
2. For every set ๐ let ๐ท๐ = {๐ โ [๐] | ๐ (๐)๐ โ ๐ (๐)๐ } . For ๐ โ ๐ถ, |๐ท๐ | > 5๐ผ๐. The set ๐ is
a random subset of ๐ of size 9๐/10 . Therefore, for ๐ โ ๐ถ, by the tail bound (Fact 2.4),
๐ผ๐ 3๐ผ๐
Pr๐โ๐ [|๐ โฉ ๐ท๐ | โค 3๐ผ๐ | ] โค eโ 4 . By definition,
if |๐ โฉ ๐ท๐ | โฅ 3๐ผ๐, then ๐ (๐)๐ 0 ๐(๐) .
3๐ผ๐ ๐ผ๐
That is, for ๐ โ ๐ถ, Pr๐โ๐ ๐ (๐)๐ โ ๐(๐) โค eโ 4 .
From the two items above,
Pr[Test passes|๐ โ ๐ถ] = Pr [๐ โ ๐ฑ and ๐ (๐ โช ๐)๐ = ๐ (๐ โช ๐)๐ | ๐ โ ๐ถ]
3๐ผ๐
โค Pr ๐ (๐ โช ๐)๐ 0 ๐(๐) and ๐ โ ๐ฑ ๐ โ ๐ถ
๐
3๐ผ๐
+ Pr ๐ (๐)๐ โ ๐(๐) ๐ โ ๐ถ
๐โ๐
๐ผ๐
โค 3๐ 2 + eโ 4 .
We assume that ๐ passes the test with probability ๐ โ ๐ 2 /๐ ,
Pr[Test passes] = Pr[Test passes and ๐ โ ๐ถ] + Pr[Test passes and ๐ โ ๐ถ] .
Therefore,
๐2
Pr[๐ โ ๐ถ] โฅ ๐ โ โ 3๐ 2 โ eโ 4 ๐ผ๐ โฅ ๐ โ 4๐2 ,
1
๐
which finishes the proof.
In the introduction, we stressed that in order to extend the restricted global structure into a
global structure, the restricted global structure theorem has to be โstrong,โ i. e., the probability
3๐ผ๐
of ๐ (๐ โช ๐)๐ 0 ๐ ๐ ,๐ (๐) should be strictly smaller than ๐, it is 2๐ 2 in our case. If the local
structure was not strong and the bound in (4.1) would have been larger than ๐, then all the
5๐ผ๐
success probability of the test could come from sets such that ๐ (๐) 0 ๐(๐). In this case, we
could not have deduced that ๐ถ is large and ๐ is close to a direct product function. This is the
situation in the local structure theorem of [8].
T HEORY OF C OMPUTING, Volume 19 (3), 2023, pp. 1โ56 31
I RIT D INUR AND I NBAL L IVNI NAVON
5 Global structure for tuples
In this section, we prove our main theorem โ global structure for tuples. The proof uses the
restricted global structure, Theorem 3.9. For convenience, we write again the test and theorem
from the introduction.
Test 1: Z-test with parameter ๐ก = ๐/10 (3-query test)
1. Choose ๐ด, ๐ต, ๐ถ to be a random partition of [๐], ๐ด ๐ถ ๐ต
such that |๐ด| = |๐ต| = ๐/10 . ๐ฅ
2. Choose uniformly at random ๐ฅ, ๐ฆ, ๐ง โ [๐] ๐ such ๐ฆ
that ๐ฅ ๐ด = ๐ฆ๐ด and ๐ฆ๐ต = ๐ง ๐ต .
๐ง
3. Accept if ๐ (๐ฅ)๐ด = ๐ (๐ฆ)๐ด and ๐ (๐ง)๐ต = ๐ (๐ฆ)๐ต .
Denote by agr๐๐/10 ( ๐ ) the success probability of ๐ on this test.
Let ๐ z be the distribution over ๐ด, ๐ต, ๐ถ, ๐ฅ, ๐ฆ, ๐ง as described above in the test.
Theorem 5.1 (Main theorem โ Global Structure for tuples, restated). For every ๐ , ๐ > 1, there
exists a small constant ๐ > 0 such that for every constant ๐ > 0 and large enough ๐, if ๐ : [๐] ๐ โ [๐] ๐
is a function that passes Test 1 with probability ๐ = agr๐๐/10 ( ๐ ) โฅ eโ๐๐ ๐ , then there exist functions
2
(๐1 , . . . , ๐ ๐ ) , ๐ ๐ : [๐] โ [๐] such that
๐
๐๐
Pr ๐ (๐ฅ) โ (๐1 (๐ฅ 1 ), . . . , ๐ ๐ (๐ฅ ๐ )) โฅ .
๐ฅโ[๐] ๐ 10
Fix a function ๐ : [๐] ๐ โ [๐] ๐ , such that agr๐๐/10 ( ๐ ) = ๐ โฅ eโ๐๐ ๐ .
2
Similar to the proof of the restricted global structure, in the proof we use several values for
the slack parameter ๐. These are constant multiples of each other, and are denoted by ๐0 , ๐1 etc.
Our proof of Theorem 1.1 relies on Theorem 3.9. The theorem states that many restrictions ๐
are DP restrictions (see Definition 3.6). Fix ๐0 = ๐/10000 . We apply theorem Theorem 3.9 with
the slack parameter ๐ผ = ๐0 . For every ๐0 -DP restriction ๐, we denote by ๐๐ the direct product
function corresponding to ๐.
For the proof, we need a few definitions.
Definition 5.2 (Successful set). For every ๐ฅ โ [๐] ๐ , a set ๐ด โ [๐], |๐ด| = ๐/10 , is successful with
respect to ๐ฅ if
1. Pr ๐ฆ,๐ต,๐งโผ๐ z
|๐ด,๐ฅ
[Test 1 succeeds] โฅ ๐/3 .
2. ๐ = (๐ด, ๐ฅ ๐ด , ๐ (๐ฅ)๐ด ) is a ๐0 -DP-restriction.
T HEORY OF C OMPUTING, Volume 19 (3), 2023, pp. 1โ56 32
E XPONENTIALLY S MALL S OUNDNESS FOR THE D IRECT P RODUCT Z- TEST
Definition 5.3 (Consistent functions). Let ๐1 , ๐2 โ [๐] and let ๐ : [๐]๐1 โ [๐]๐1 and ๐ 0 :
[๐]๐2 โ [๐]๐2 be two direct product functions. We say that ๐, ๐ 0 are ๐ฝ-consistent if for a
uniform ๐ โ ๐1 โฉ ๐2 and ๐ โ [๐],
Pr ๐ ๐ (๐) โ ๐ 0๐ (๐) โค ๐ฝ .
๐,๐
We prove the main theorem in Section 5.1, and prove the lemmas used in the proof in the
next sections.
5.1 Proof of Theorem 1.1
Let ๐ : [๐] ๐ โ [๐] ๐ be a function that passes Test 1 with probability ๐.
By Theorem 3.9, a restriction ๐ = (๐ด, ๐ฅ ๐ด , ๐ (๐ฅ)๐ด ) is a ๐0 -DP-restriction with probability at
ยฏ ยฏ
least ๐/2 ยท (1 โ ๐2 ) . We denote by ๐๐ : [๐]๐ด โ [๐]๐ด the DP function associated with ๐.
We start by finding a single string ๐ฅ which is โglobally goodโ. Fix ๐1 = 60๐0 .
Lemma 5.4. There exists ๐ฅ โ [๐] ๐ , such that
1. Pr๐ด [๐ด is successful with respect to ๐ฅ] โฅ ๐/4 .
2. Pr๐ด ,๐ด โ [๐] [๐ด1 , ๐ด2 are successful w.r.t. ๐ฅ and ๐๐1 , ๐๐2 are ๐1 -consistent] โฅ ๐ 5 , where the tu-
1 2 ( ๐/10)
ples are ๐1 = (๐ด1 , ๐ฅ ๐ด1 , ๐ (๐ฅ)๐ด1 ) and ๐2 = (๐ด2 , ๐ฅ ๐ด2 , ๐ (๐ฅ)๐ด2 ) .
The proof appears on Section 5.2.
We fix the string ๐ฅ โ [๐] ๐ promised from Lemma 5.4. Let ๐ โ [๐]
๐/10
be the set of sets that
ยฏ ๐ดยฏ
are successful with respect to ๐ฅ. For every ๐ด โ ๐, let ๐ ๐ด : [๐]๐ด โ [๐] be the direct product
function ๐๐ , for ๐ = (๐ด, ๐ฅ ๐ด , ๐ (๐ฅ)๐ด ) .
Theorem 5.5. For all integers ๐ , ๐ โ โ and large enough ๐ โ โ , and all small constants ๐ฝ, ๐ > 0
such that ๐ > eโ 3 ๐ฝ ๐ , the following holds. Let ๐ โ ๐/10
ยฏ
[๐]
be a set of sets, and let โฑ = {๐ ๐ด : [๐]๐ด โ
1 2
ยฏ
[๐]๐ด } ๐ดโ๐ be a family of direct product functions. If
Pr [๐ด1 , ๐ด2 โ ๐ and ๐ ๐ด1 , ๐ ๐ด2 are ๐ฝ-consistent] โฅ ๐ ,
[๐]
๐ด1 ,๐ด2 โ( ๐/10)
then there exists a global function ๐ : [๐] ๐ โ [๐] ๐ such that
1
Pr [๐ด โ ๐ and ๐ ๐ด , ๐ are 50๐ฝ-consistent] โฅ ๐ .
[๐] 4
๐ดโ( ๐/10)
We prove the theorem in Section 5.3 (in fact we prove a slightly stronger statement).
The family {๐ ๐ด } ๐ดโ๐ satisfies the conditions of the theorem, with parameters ๐ = ๐ 5 and
๐ฝ = ๐1 . Let ๐ : [๐] ๐ โ [๐] ๐ be the direct product function promised from the theorem. Fix
๐3 = 160๐1 . We finally claim that ๐ is the required global DP function,
๐3 ๐
๐
Lemma 5.6. Pr๐งโ[๐]๐ ๐ (๐ง) โ ๐(๐ง) โฅ 10 .
The proof appears in Section 5.4. This finishes the proof since ๐3 < ๐ .
T HEORY OF C OMPUTING, Volume 19 (3), 2023, pp. 1โ56 33
I RIT D INUR AND I NBAL L IVNI NAVON
5.2 Consistency between restricted global functions
In this section we find a string ๐ฅ โ [๐] ๐ which is โglobally goodโ, proving Lemma 5.4.
Claim 5.7. There exists ๐ฅ โ [๐] ๐ such that
1. Pr๐ด,๐ฆ,๐ต,๐งโผ๐ z [Test 1 passes] โฅ ๐/3 and,
|๐ฅ
2. Pr๐ด [๐ด is successful w.r.t. ๐ฅ] โฅ 3๐ .
Proof. Let ๐บ = (๐ฟ โช ๐
, ๐ธ) be the full bipartite graph, with vertex sets ๐ฟ = ๐/10 [๐]
and ๐
= [๐] ๐ .
Let ๐ : ๐ธ โ [0, 1] be a function matching each edge (๐ด, ๐ฅ) the success probability of Test 1 given
that ๐ด, ๐ฅ are chosen, i. e., ๐(๐ด, ๐ฅ) = Pr ๐ฆ,๐ต,๐งโผ๐ z [Test 1 passes] . Then ๐ผ(๐ด,๐ฅ)โ๐ธ [๐(๐ด, ๐ฅ)] โฅ ๐ .
|๐ด,๐ฅ
Suppose that for each edge ๐ with ๐(๐) โค ๐/2 , we change ๐(๐) to 0. The expected value of ๐
is reduced by at most ๐/2 , i. e., ๐ผ(๐ด,๐ฅ)โ๐ธ [๐(๐ด, ๐ฅ)] โฅ ๐/2 . All the edges (๐ด, ๐ฅ) that remain with
positive value ๐ are of edges (๐ด, ๐ฅ) such that ๐ = (๐ด, ๐ฅ, ๐ (๐ฅ)๐ด ) is good2.
We further change ๐(๐) to 0 for all edges ๐ = (๐ด, ๐ฅ) such that ๐ = (๐ด, ๐ฅ ๐ด , ๐ (๐ฅ)๐ด ) is not a
๐0 -DP restriction. From Theorem 3.9, a good ๐ โผ ๐ is a DP-restriction with probability at least
1 โ ๐ 2 . The distribution ๐ โผ ๐ corresponds to a uniform choice of (๐ด, ๐ฅ) โ ๐ธ. Therefore, we
have changed ๐(๐) to 0 on at most ๐ 2 fraction of the edges. The maximal value of ๐ is 1, so this
step reduces the expectation of ๐ over ๐ธ by at most ๐ 2 , and ๐ผ(๐ด,๐ฅ)โ๐ธ [๐(๐ด, ๐ฅ)] โฅ ๐/2 โ ๐ 2 โฅ ๐/3 .
Let ๐ฅ be a vertex which maximizes ๐ผ๐ด [๐(๐ด, ๐ฅ)], then
๐
Pr z Test 1 passes โฅ ๐ผ [๐(๐ด, ๐ฅ)] โฅ .
๐ด,๐ฆ,๐ต,๐งโผ๐ |๐ฅ ๐ด 3
All edges (๐ด, ๐ฅ) such that ๐(๐ด, ๐ฅ) > 0 are such that ๐ด is successful with respect to ๐ฅ, so
๐
Pr [๐ด is successful w.r.t. ๐ฅ] = Pr [๐(๐ด, ๐ฅ) > 0] โฅ ,
๐ด ๐ด 3
where the last inequality holds because the maximal value of ๐ is 1.
In the rest of this subsection, we fix an ๐ฅ satisfying the properties of Claim 5.7. For every
ยฏ ยฏ
set ๐ด that is successful with respect to ๐ฅ, denote by ๐ ๐ด : [๐]๐ด โ [๐]๐ด the function ๐๐ for
๐ = (๐ด, ๐ฅ ๐ด , ๐ (๐ฅ)๐ด ) . Denote by ๐ต๐ด the set
( ๐1 ๐
)
๐ต๐ด = ๐ง โ [๐] ๐ ๐ (๐ง)๐ดยฏ โ ๐ ๐ด (๐ง ๐ดยฏ ) .
3
Note that the set ๐ต๐ด might be all of [๐] ๐ .
We prove in the next claim that if ๐ด is successful with respect to ๐ฅ, then ๐ ๐ด is consistent
with the original function ๐ . This consistency is much stronger than what is guaranteed by
Theorem 3.9. By Theorem 3.9, ๐ ๐ด , ๐ are consistent on a set of inputs contained in the set
๐ค โ [๐] ๐ ๐ค ๐ด = ๐ฅ ๐ด . In the claim below, we prove that ๐ ๐ด , ๐ are consistent on ฮฉ(๐) fraction
of [๐] ๐ , which is a much larger set.
2There may also be good tuples with value 0, if Test 2 passes with probability larger than ๐/2 but Test 1 doesnโt.
T HEORY OF C OMPUTING, Volume 19 (3), 2023, pp. 1โ56 34
E XPONENTIALLY S MALL S OUNDNESS FOR THE D IRECT P RODUCT Z- TEST
Claim 5.8. For every ๐ด that is successful with respect to ๐ฅ,
๐
Pr [๐ง โ ๐ต๐ด ] โฅ .
๐งโ[๐] ๐ 4
Proof. Fix an ๐ด that is successful with respect to
๐ฅ, and assume for a contradiction that
Pr๐งโ[๐]๐ [๐ง โ ๐ต๐ด ] < ๐/4 . For every ๐ง, let ๐ท๐ง = ๐ โ ๐ดยฏ ๐ (๐ง)๐ โ ๐ ๐ด,๐ (๐ง ๐ ) , then for ๐ง โ ๐ต๐ด ,
|๐ท๐ง | โฅ ๐๐1 /3 .
๐0 ๐
Let ๐ฆ, ๐ง, ๐ต โผ ๐ z |๐ด, ๐ฅ . Suppose ๐ฆ is such that ๐ (๐ฆ)๐ดยฏ โ ๐ ๐ด (๐ฆ๐ดยฏ ) . The test passes if
๐ (๐ฆ)๐ต = ๐ (๐ง)๐ต , which implies (since ๐ต โ ๐ด) ยฏ that also ๐ (๐ง)๐ต ๐โ0 ๐ ๐ ๐ด (๐ฆ ยฏ )๐ต . The function ๐ ๐ด is a
๐ด
product function and ๐ฆ๐ต = ๐ง ๐ต , so ๐ ๐ด (๐ฆ๐ดยฏ )๐ต = ๐ ๐ด (๐ง ๐ดยฏ )๐ต and we get from the previous inequality
that
๐0 ๐
๐ (๐ง)๐ต โ ๐ ๐ด (๐ฆ๐ดยฏ )๐ต = ๐ ๐ด (๐ง ๐ดยฏ )๐ต .
From the definition of ๐ท๐ง , this only happens if |๐ท๐ง โฉ ๐ต| โค ๐0 ๐ . To summarize, if the test passes
๐0 ๐
and ๐ฆ is such that ๐ (๐ฆ)๐ดยฏ โ ๐ ๐ด (๐ฆ๐ดยฏ ) , it must be that |๐ท๐ง โฉ ๐ต| โค ๐0 ๐ .
From the above paragraph,
๐0 ๐
Pr [Test passes|๐ง โ ๐ต๐ด ] = Pr Test passes and ๐ (๐ฆ)๐ดยฏ 0 ๐ ๐ด (๐ฆ๐ดยฏ ) ๐ง โ ๐ต๐ด
๐ต,๐ฆ,๐งโผ๐ |๐ด,๐ฅ
z ๐ต,๐ฆ,๐ง
๐0 ๐
+ Pr Test passes and ๐ (๐ฆ)๐ดยฏ โ ๐ ๐ด (๐ฆ๐ดยฏ ) ๐ง โ ๐ต๐ด
๐ต,๐ฆ,๐ง
๐0 ๐
โค Pr ๐ (๐ฆ)๐ดยฏ 0 ๐ ๐ด (๐ฆ๐ดยฏ ) ๐ (๐ฅ)๐ด = ๐ (๐ฆ)๐ด , ๐ง โ ๐ต๐ด
๐ฆ
+ Pr [|๐ต โฉ ๐ท๐ง | โค ๐0 ๐ | ๐ง โ ๐ต๐ด ] .
๐ต,๐ง
We bound the two expressions. For the first, from Theorem 3.9,
๐0 ๐
Pr ๐ (๐ฆ)๐ดยฏ 0 ๐ ๐ด (๐ฆ๐ดยฏ ) ๐ (๐ฅ)๐ด = ๐ (๐ฆ)๐ด โค ๐ 2 .
๐ฆ
Conditioning on ๐ง โ ๐ต๐ด , which occurs with probability at least 1 โ 4๐ , increases the probability
by a factor of at most 1โ1 ๐ < 2 .
4
For the second expression, the set ๐ต is a random subset of ๐ดยฏ of size ๐/10 , and |๐ท๐ง | โฅ ๐๐1 /3 =
20๐0 ๐ . Using the Hoeffding bound for random subset (Fact 2.4),
๐1 ๐
Pr [|๐ต โฉ ๐ท๐ง | โค ๐0 ๐ | ๐ง โ ๐ต๐ด ] โค eโ 20 < ๐2 .
๐ต,๐ง
We conclude that
Pr [Test passes|๐ง โ ๐ต๐ด ] โค 3๐ 2 .
๐ต,๐ฆ,๐งโผ๐ |๐ด,๐ฅ
z
T HEORY OF C OMPUTING, Volume 19 (3), 2023, pp. 1โ56 35
I RIT D INUR AND I NBAL L IVNI NAVON
This implies that
Pr [Test passes] โค Pr [Test passes|๐ง โ ๐ต๐ด ] + Pr[๐ง โ ๐ต๐ด ]
๐ต,๐ฆ,๐งโผ๐ |๐ด,๐ฅ
z
๐ต,๐ฆ,๐งโผ๐ |๐ด,๐ฅ
z ๐ง
๐ ๐
โค3๐ 2 + < .
4 3
This contradicts ๐ด being successful with respect to ๐ฅ.
In the introduction, we explained the difference between our restricted global structure
and the result of [8]. In our result, Theorem 3.9, ๐ (๐ฆ)๐ดยฏ โ ๐ ๐ด (๐ฆ) for 1 โ ๐ 2 of ๐ฆ โ ๐ฑ๐ (for
๐ = (๐ด, ๐ฅ ๐ด , ๐ (๐ฅ)๐ด ) , whereas in their result this probability was not as overwhelmingly close to 1.
We require this for proving the above claim, as well as for proving the global structure.
Claim 5.9.
๐2 ๐ ๐2
Pr |๐ต๐ด1 โฉ ๐ต๐ด2 | โฅ ๐ ๐ด1 , ๐ด2 are successful w.r.t. ๐ฅ โฅ .
[๐] 32 32
๐ด1 ,๐ด2 โ(๐/10 )
Proof. Let ๐ด1 , ๐ด2 be two uniform sets that are successful with respect to ๐ฅ, then
ร
๐ผ [|๐ต๐ด1 โฉ ๐ต๐ด2 |] = ๐ผ [๐(๐ง โ ๐ต๐ด1 โฉ ๐ต๐ด2 )]
๐ด1 ,๐ด2 ๐ด1 ,๐ด2
๐งโ[๐] ๐
ร
= ๐ผ [๐(๐ง โ ๐ต๐ด1 )๐(๐ง โ ๐ต๐ด2 )]
๐ด1 ,๐ด2
๐งโ[๐] ๐
ร
= ๐ผ [๐(๐ง โ ๐ต๐ด )]2 ,
๐ด
๐งโ[๐] ๐
where ๐ is an indicator. The last equality holds since ๐ด1 , ๐ด2 are independent uniform sets that
are successful with respect to ๐ฅ.
By Cauchy Schwarz,
2
ยฉ ร โ 2๐ ยฉ ร โ๐ ยช ยฉ ร
๐ ๐ผ [๐(๐ง โ ๐ต๐ด )]ยฎ โค ยญ ๐ ยฎยญ ๐ผ [๐(๐ง โ ๐ต๐ด )]2 ยฎ
ยช ยช
ยญ
๐ด ๐ด
ยซ๐งโ[๐]๐ ยฌ ยซ๐งโ[๐]
ร
๐
ยฌ ยซ๐งโ[๐]๐ ยฌ
=1 ยท ๐ผ [๐(๐ง โ ๐ต๐ด )] .
2
๐ด
๐งโ[๐] ๐
From Claim 5.8, for every ๐ด which is successful with respect to ๐ฅ, Pr๐ง [๐ง โ ๐ต๐ด ] โฅ ๐/4 . This
means that for every such ๐ด, ๐ง ๐(๐ง โ ๐ต๐ด ) โฅ ๐ ๐ ๐/4 . This also holds for a uniform ๐ด that is
ร
successful with respect to ๐ฅ. Combining it together with the above equations,
!2
๐ 2
โ 2๐ ๐
ร ร
๐ผ [|๐ต๐ด1 โฉ ๐ต๐ด2 |] = ๐ผ [๐(๐ง โ ๐ต๐ด )] โฅ 2
๐ ๐ผ [๐(๐ง โ ๐ต๐ด )] โฅ ๐2 .
๐ด1 ,๐ด2 ๐ด ๐ด 4
๐งโ[๐] ๐ ๐ง
T HEORY OF C OMPUTING, Volume 19 (3), 2023, pp. 1โ56 36
E XPONENTIALLY S MALL S OUNDNESS FOR THE D IRECT P RODUCT Z- TEST
The maximal value of |๐ต๐ด1 โฉ ๐ต๐ด2 | is ๐ ๐ , therefore by averaging
๐2 ๐ ๐2
Pr |๐ต๐ด1 โฉ ๐ต๐ด2 | โฅ ๐ โฅ .
๐ด1 ,๐ด2 32 32
Claim 5.10. For every ๐ด1 , ๐ด2 โ [๐]
๐/10
such that |๐ต๐ด1 โฉ ๐ต๐ด2 | โฅ ๐ ๐ ๐ 2 /32 , the functions ๐ ๐ด1 , ๐ ๐ด2 are
๐1 -consistent.
Proof. Fix ๐ด1 , ๐ด2 such that |๐ต๐ด1 โฉ ๐ต๐ด2 | โฅ ๐ ๐ ๐ 2 /32 . Let ๐ = [๐] \ {๐ด1 โช ๐ด2 } . ๐ is the set of
coordinates both ๐ ๐ด1 , ๐ ๐ด2 are defined on, and |๐| โฅ 0.8๐ .
Assume for a contradiction that ๐ ๐ด1 , ๐ ๐ด2 are not ๐1 -consistent, i. e.,
Pr [๐ ๐ด1 ,๐ (๐) โ ๐ ๐ด2 ,๐ (๐)] > ๐1 .
๐โ๐,๐โ[๐]
By the Chernoff tail bound (Fact 2.3),
3 ๐1 ๐
2
๐ ๐ด1 (๐ง ๐ดยฏ1 )๐ โ ๐ ๐ด2 (๐ง ๐ดยฏ2 )๐ โค eโ 10 ๐1 ๐ .
1
Pr (5.1)
๐งโ[๐] ๐
We can use the Chernoff bound on the different coordinates ๐ โ ๐ because the functions ๐ ๐ด1 , ๐ ๐ด2
are direct product functions, so their output on different coordinates is independent.
3 ๐1 ๐ 3 ๐1
1 1
Any input ๐ง โ ๐ต1 โฉ ๐ต2 satisfies both ๐ (๐ง)๐ดยฏ1 โ ๐ ๐ด1 (๐ง ๐ดยฏ1 ) and ๐ (๐ง)๐ดยฏ2 โ ๐ ๐ด2 (๐ง ๐ดยฏ2 ) which
3 ๐1 ๐
2
implies that ๐ ๐ด1 (๐ง ๐ ) โ ๐ ๐ด2 (๐ง ๐ ) . That is,
3 ๐1 ๐ ๐2
2
Pr ๐ ๐ด1 (๐ง ๐ดยฏ1 )๐ โ ๐ ๐ด2 (๐ง ๐ดยฏ2 )๐ โฅ Pr [๐ง โ ๐ต๐ด1 โฉ ๐ต๐ด2 ] โฅ ,
๐งโ[๐] ๐ ๐งโ[๐] ๐ 32
which contradicts (5.1).
Proof of Lemma 5.4. Let ๐ฅ โ [๐] ๐ be the input promised from Claim 5.7.
A set ๐ด is successful with respect to ๐ฅ with probability at least 3๐ . From Claim 5.9,
๐2 ๐ ๐2
Pr |๐ต๐ด1 โฉ ๐ต๐ด2 | โฅ ๐ ๐ด1 , ๐ด2 are successful w.r.t. ๐ฅ โฅ .
[๐] 32 32
๐ด1 ,๐ด2 โ(
๐/10 )
By Claim 5.10, such sets ๐ด1 , ๐ด2 are ๐1 consistent, i. e.,
๐ด ๐ด ๐2
Pr ๐ 1 , ๐ 2 are ๐1 consistent ๐ด1 , ๐ด2 are successful w.r.t. ๐ฅ โฅ .
[๐] 32
๐ด1 ,๐ด2 โ( ๐/10)
Therefore, the probability of ๐ด1 , ๐ด2 to be successful with respect to ๐ฅ and ๐1 consistent is at least
๐ 2 ๐2
32 > ๐ .
4
5
T HEORY OF C OMPUTING, Volume 19 (3), 2023, pp. 1โ56 37
I RIT D INUR AND I NBAL L IVNI NAVON
5.3 Agreement theorem in the dense case
In this section we prove Theorem 5.5, which is an agreement theorem for functions. In fact, we
prove a more general version of the theorem, Theorem 5.13 below.
Let ฮฃ be an alphabet with a distance function dist : ฮฃ ร ฮฃ โ [0, 1] that satisfies the triangle
inequality, i. e., dist(๐ฅ, ๐ฆ) + dist(๐ฆ, ๐ง) โฅ dist(๐ฅ, ๐ง) for all ๐ฅ, ๐ฆ, ๐ง โ ฮฃ. We look at a family of
functions โฑ = { ๐๐ : ๐ โ ฮฃ} ๐โ [๐] .
(9๐/10)
Definition 5.11. The difference between ๐๐1 , ๐๐2 โ โฑ , denoted by ฮ( ๐๐1 , ๐๐2 ) , is defined by the
equation
ฮ( ๐๐1 , ๐๐2 ) = ๐ผ [dist( ๐๐1 (๐), ๐๐1 (๐))] .
๐โ๐1 โฉ๐2
The difference between ๐๐ โ โฑ and a function ๐ : [๐] โ ฮฃ is defined by the equation
ฮ( ๐๐ , ๐) = ๐ผ [dist( ๐๐ (๐), ๐(๐))] .
๐โ๐
Definition 5.12. The agreement of the collection of local functions โฑ regarding the uniform
distribution with parameter ๐ฝ, denoted by agree๐ฝ (โฑ ) is defined by the equation
agree๐ฝ (โฑ ) = Pr [ฮ( ๐๐1 , ๐๐2 ) < ๐ฝ] .
๐๐1 , ๐๐2 โโฑ
Theorem 5.13. For every small constant ๐ฝ โ (0, 1), large enough ๐ โ โ , every ๐ > eโ 3 ๐ฝ ๐ , and every
1 2
alphabet ฮฃ with a distance measure ๐๐๐ ๐ก : ฮฃ ร ฮฃ โ [0, 1] the following holds.
If a collection of local functions โฑ = { ๐๐ : ๐ โ ฮฃ} ๐โ [๐] has agree๐ฝ (โฑ ) > ๐ , then there exists a
(9๐/10)
global function ๐ : [๐] โ ฮฃ such that
1
Pr [ฮ( ๐๐ , ๐) โค 50๐ฝ] โฅ ๐ .
[๐] 4
๐โ(9๐/10)
Claim 5.14. Theorem 5.13 implies Theorem 5.5.
๐] ยฏ ยฏ
Proof. Let ๐ , ๐, ๐ โ โ , and let ๐ โ ๐/10 be a set of sets. Let {๐ ๐ด } ๐ดโ๐ , โ๐ด, ๐ ๐ด : [๐]๐ด โ [๐]๐ด
be a family of direct product functions satisfying the conditions of Theorem 5.5.
ยฏ ยฏ
Set ฮฃ = [๐]๐ โช โฅ. For every ๐ด โ ๐ and every direct product function ๐ ๐ด : [๐]๐ด โ [๐]๐ด ,
๐ ๐ด = (๐ ๐ )๐โ๐ดยฏ , we define ๐๐ดยฏ : ๐ดยฏ โ [๐]๐ by
โ๐ โ ๐ดยฏ ๐๐ดยฏ (๐) = the truth table of ๐ ๐ .
Since ๐ ๐ : [๐] โ [๐], its truth table is in [๐]๐ . For every ๐ด โ ๐ we set ๐๐ดยฏ to equal โฅ on all
inputs.
We define the distance measure inside ฮฃ as follows,
(
0 0 Pr๐โ[๐] [๐๐ โ ๐0๐ ] if ๐, ๐0 โ โฅ
โ๐, ๐ โ ฮฃ dist(๐, ๐ ) =
1 otherwise.
T HEORY OF C OMPUTING, Volume 19 (3), 2023, pp. 1โ56 38
E XPONENTIALLY S MALL S OUNDNESS FOR THE D IRECT P RODUCT Z- TEST
The distance is the normalized Hamming distance for strings that are not โฅ.
We show that the collection of functions { ๐๐ } ๐โ [๐] satisfies the conditions of Theorem 5.13.
(9๐/10)
If ๐ด1 , ๐ด2 โ ๐ and ๐ ๐ด1 , ๐ ๐ด2 are ๐ฝ-consistent, then by definition ฮ( ๐๐ดยฏ1 , ๐๐ดยฏ2 ) < ๐ฝ , thus by the
assumptions of Theorem 5.5, agree๐ฝ (โฑ ) > ๐.
Let ๐ : [๐] โ ฮฃ be the function promised from Theorem 5.13. Then ฮ( ๐๐ , ๐) โค 50๐ฝ for at
[๐]
least a ๐/4 fraction of the sets ๐ โ 9๐/10 , let this set of functions be โฑ 0 . Every function ๐๐ โ โฑ 0
must correspond to some ๐๐ยฏ for ๐ยฏ โ ๐, since for other sets ๐, ๐๐ equals โฅ and is at distance 1
from any other function.
Let ๐ 0 : [๐] ๐ โ [๐] ๐ be the direct product function that for every ๐ โ [๐] has ๐ 0๐ : [๐] โ [๐]
be the functions defined by ๐(๐). If there is ๐ such that ๐(๐) = โฅ, we define ๐ 0๐ arbitrarily. By
Theorem 5.13, for every ๐๐ โ ๐ถ, ๐ยฏ โ ๐ and ๐๐ยฏ , ๐ are 50๐ฝ-consistent.
We now prove Theorem 5.13. In order to prove the theorem, it is helpful to look at the sets
[๐]
๐ โ 9๐/10 as vertices in a graph. Let ๐ข = (๐ , ๐ธ๐ โช ๐ธ๐ ) to be the graph with the vertex set
[๐]
๐ = 9๐/10
, and two edge sets, weak edges and strong edges.
Definition 5.15. For every two sets ๐1 , ๐2 โ ๐ ,
1. ๐1 , ๐2 are connected by a strong edge, denoted by ๐1 โ ๐2 , if ฮ( ๐๐1 , ๐๐2 ) < ๐ฝ.
2. ๐1 , ๐2 are connected by a weak edge, denoted by ๐1 โผ ๐2 , if ฮ( ๐๐1 , ๐๐2 ) < 10๐ฝ.
If ๐1 , ๐2 are not connected by a weak edge, we denote ๐1 6โผ ๐2 .
We want to find a very dense set of vertices in ๐ข. Such a subset will allow us to define a
global function ๐. We start by showing that there are many vertices with high degree in ๐ข.
Claim 5.16. There exists a set ๐ฎ โ ๐ of measure at least ๐/2 , such that for every ๐ โ ๐ฎ
1
Pr [๐ โ ๐0] โฅ ๐.
๐ โ๐
0 2
Proof. Let
0 1
๐ฎ= ๐โ๐ Pr0 [๐ โ ๐ ] โฅ ๐ .
๐ 2
By averaging
๐ โค Pr [๐1 โ ๐2 ]
๐1 ,๐2
โค Pr [๐1 โ ๐ฎ] Pr [๐1 โ ๐2 | ๐1 โ ๐ฎ] + Pr [๐1 โ ๐ฎ] Pr [๐1 โ ๐2 | ๐1 โ ๐ฎ]
๐1 ๐1 ,๐2 ๐1 ๐1 ,๐2
1
โค Pr [๐1 โ ๐ฎ] + ๐ 1 โ Pr [๐1 โ ๐ฎ] .
๐1 2 ๐1
Then Pr๐1 [๐1 โ ๐ฎ] โฅ ๐/2 .
T HEORY OF C OMPUTING, Volume 19 (3), 2023, pp. 1โ56 39
I RIT D INUR AND I NBAL L IVNI NAVON
Strong connectivity is not transitive, but we can have an โalmost transitiveโ property by
considering both strong and weak edges.
Claim 5.17. For ๐, ๐1 , ๐2 โ ๐ uniformly and independently,
Pr [๐ โ ๐1 , ๐ โ ๐2 , ๐1 6โผ ๐2 ] โค 2eโ๐ฝ ๐ .
2
๐,๐1 ,๐2
From the claim we get that if ๐ is connected to ๐1 , ๐2 by a strong edge, then almost always
๐1 , ๐2 are connected by a weak edge.
Proof. Fix ๐1 , ๐2 โ ๐ to be two vertices such that ๐1 6โผ ๐2 (if there are no such vertices, the
probability is 0 and we are done). For every ๐ โ [๐] let ๐ ๐ โ [0, 1] be
(
dist( ๐๐1 (๐), ๐๐2 (๐)) if ๐ โ ๐1 โฉ ๐2
๐๐ =
0 otherwise.
Since ๐1 6โผ ๐2 , ๐โ[๐] ๐ ๐ โฅ (8๐/10) ยท 10๐ฝ = 8๐ฝ๐ (the minimal size of ๐1 โฉ ๐2 is 8๐/10).
ร
If ๐ is a set that is strongly connected to both ๐1 and ๐2 , then by the triangle inequality
ร ร
dist( ๐๐1 (๐), ๐๐2 (๐)) โค dist( ๐๐ (๐), ๐๐1 (๐)) + dist( ๐๐ (๐), ๐๐2 (๐)) โค 2๐ฝ๐ .
๐โ๐โฉ๐1 โฉ๐2 ๐โ๐โฉ๐1 โฉ๐2
That is, ๐โ๐ ๐ ๐ โค 2๐ฝ๐ .
ร
The set ๐ is a uniform subset of [๐] of size 9๐/10 . Using the Hoeffding bound for random
sampling without replacement (Fact 2.5)
" #
ร
Pr [๐ โ ๐1 and ๐ โ ๐2 ] โค Pr ๐ ๐ โค 2๐ฝ๐ โค eโ2๐ฝ ๐ .
2
๐ ๐
๐โ๐
Since the bound holds for every ๐1 6โผ ๐2 , then it holds also for the uniform distribution over sets
๐1 , ๐2 .
From the last two claims, Claim 5.16 and Claim 5.17, we conclude that there is a high degree
vertex in ๐ whose neighbors form a very dense graph with respect to weak edges.
Claim 5.18. There exists a set ๐ โ ๐ฎ such that
Pr [๐1 โผ ๐2 | ๐1 โ ๐, ๐2 โ ๐] โฅ 1 โ ๐ฝ .
๐1 ,๐2 โ๐ฑ
Proof. From Claim 5.16, we know that if we choose ๐, ๐1 , ๐2 โ ๐ independently,
๐ 3
Pr [๐ โ ๐ฎ, ๐ โ ๐1 , ๐ โ ๐2 ] โฅ Pr [๐ โ ๐ฎ] Pr [๐ โ ๐1 | ๐ โ ๐ฎ]2 โฅ .
๐,๐1 ,๐2 ๐ ๐,๐1 2
T HEORY OF C OMPUTING, Volume 19 (3), 2023, pp. 1โ56 40
E XPONENTIALLY S MALL S OUNDNESS FOR THE D IRECT P RODUCT Z- TEST
From Claim 5.17, on the same distribution
Pr [๐ โ ๐1 , ๐ โ ๐2 , ๐1 6โผ ๐2 ] โค eโ2๐ฝ ๐ .
2
๐,๐1 ,๐2
Therefore 3
2
Pr [๐1 6โผ ๐2 | ๐ โ ๐ฎ, ๐ โ ๐1 , ๐ โ ๐2 ] โค eโ2๐ฝ ๐ .
2
๐,๐1 ,๐2 ๐
Since ๐ > eโ 3 ๐ฝ ๐ , the bound on the probability ๐2 eโ2๐ฝ ๐ is tiny and surely smaller than ๐ฝ.
1 2 3 2
By averaging, there must be ๐ โ ๐ฎ that achieves this bound.
Claim 5.19. Let ๐ถ โ ๐ satisfy Pr๐โ๐ [๐ โ ๐ถ] โฅ ๐/2 , then the number of indices ๐ โ ๐ such that
Pr๐โ๐ถ [๐ โ ๐] โค 1/2 is at most ๐ฝ๐.
Proof. Let ๐ท โ [๐] be the set
1
๐ท = ๐ โ [๐] Pr [๐ โ ๐] โค .
๐โ๐ถ 2
[๐]
If we pick a completely uniform ๐ โ , then ๐ผ๐ [|๐ โฉ ๐ท|] = 10
9
|๐ท|.
10 ๐
9
|๐ท|
Using the the Hoeffding bound for random subset (Fact 2.4), Pr๐ |๐ โฉ ๐ท| โค 23 |๐ท| โค eโ 100 .
If instead we pick a uniform subset in ๐ โ ๐ถ, the probability of the event |๐ โฉ ๐ท| โค 32 |๐ท| may
increase by a factor of 2/๐ .
2 2 |๐ท|
Pr |๐ โฉ ๐ท| โค |๐ท| โค eโ 100 .
๐โ๐ถ 3 ๐
By the definition of ๐ท, for each ๐ โ ๐ท, Pr๐โ๐ถ [๐ โ ๐] โค 21 , so ๐ผ๐โ๐ถ [|๐ โฉ ๐ท|] โค |๐ท|/ . From
averaging Pr๐โ๐ถ [|๐ โฉ ๐ท| โค 2|๐ท|/3] โฅ 1/4.
|๐ท|
Combining the two bounds, we get that 2/๐ ยท eโ 100 โฅ 1/4 , which means that |๐ท| โค ๐ฝ๐ (recall
that ๐ > eโ๐ฝ ๐ and ๐ฝ is a small constant).
2
Proof of Theorem 5.5. Let ๐ห โ ๐ฎ be the vertex promised from Claim 5.18, and denote by ๐ถ its
strong neighbors,
๐ถ = ๐ โ ๐ ๐ โ ๐ห .
The measure of ๐ถ is at least ๐2 and Pr๐1 ,๐2 โ๐ถ [๐1 6โผ ๐2 ] โค ๐ฝ, which implies that
๐ผ [ฮ( ๐๐1 , ๐๐2 )] โค1 ยท Pr [๐1 6โผ ๐2 ] + ๐ผ [ฮ( ๐๐1 , ๐๐2 ) | ๐1 โผ ๐2 ] โค ๐ฝ + 10๐ฝ . (5.2)
๐1 ,๐2 โ๐ถ ๐1 ,๐2 โ๐ถ ๐1 ,๐2 โ๐ถ
We define our direct product function ๐ : [๐] โ ฮฃ as follows.
โ๐ โ [๐] ๐(๐) = arg min ๐ผ [dist( ๐๐ (๐), ๐)] .
๐โฮฃ ๐โ๐ถ s.t. ๐โ๐
Ties are broken arbitrarily. If there is no ๐ โ ๐ถ such that ๐ โ ๐, we set ๐(๐) to an arbitrary value.
T HEORY OF C OMPUTING, Volume 19 (3), 2023, pp. 1โ56 41
I RIT D INUR AND I NBAL L IVNI NAVON
We prove that the function ๐ satisfies the theorem requirements. It is enough to prove that
ฮ(๐, ๐๐ ) < 50๐ฝ for half of the sets ๐ โ ๐ถ.
We want to bound the expected difference ๐ผ๐โ๐ถ [ฮ(๐, ๐๐ )] . If we could say that ๐ผ๐โ๐ถ [ฮ(๐, ๐๐ )] โค
๐ผ๐1 ,๐2 โ๐ถ [ฮ( ๐๐1 , ๐๐2 )] , then by (5.2) we would be done. Unfortunately there is a slight complication,
which we explain and solve below. We write the two expectations explicitly.
1. ๐ผ๐โ๐ถ [ฮ(๐, ๐๐ )] = ๐ผ๐โ๐ถ,๐โ๐ [dist(๐(๐), ๐๐ (๐)]. Let ๐1 : [๐] โ [0, 1] be the distribution over ๐ in
this expectation, i. e., picking ๐ โ ๐ถ and then a uniform ๐ โ ๐.
2. ๐ผ๐1 ,๐2 โ๐ถ [ฮ( ๐๐1 , ๐๐2 )] = ๐ผ๐1 ,๐2 โ๐ถ,๐โ๐1 โฉ๐2 [dist( ๐๐1 (๐), ๐๐2 (๐))]. Let ๐2 : [๐] โ [0, 1] be the distri-
bution over ๐ described in this expectation, i. e., picking ๐1 , ๐2 โ ๐ถ and then ๐ โ ๐1 โฉ ๐2 .
We prove that the two distributions are rather similar. Let ๐ท be the set of โbad locationsโ, which
appear too little in ๐ถ,
1
๐ท = ๐ โ [๐] Pr [๐ โ ๐] < .
๐โ๐ถ 2
By Claim 5.19, |๐ท| โค ๐ฝ๐, and clearly also Pr๐โผ๐1 [๐ โ ๐ท] โค ๐ฝ.
For every ๐ โ ๐ท, the index ๐ appears in at least half of the sets ๐ โ ๐ถ. This means that for
every such ๐, ๐2 (๐) โฅ ๐1 (๐)/2 .
For every ๐ โ [๐], by the definition of ๐,
๐ผ [dist( ๐๐ (๐), ๐(๐))|๐ โ ๐] โค ๐ผ [dist( ๐๐1 (๐), ๐๐2 (๐))|๐ โ ๐1 โฉ ๐2 ] . (5.3)
๐โ๐ถ ๐1 ,๐2 โ๐ถ
Therefore,
๐ผ [ฮ(๐, ๐๐ )] = ๐ผ [dist(๐(๐), ๐๐ (๐)|๐ โ ๐]
๐โ๐ถ ๐โผ๐1 ,๐โ๐ถ
โค Pr [๐ โ ๐ท] + ๐ผ [dist(๐(๐), ๐๐ (๐))|๐ โ ๐ท, ๐ โ ๐]
๐โผ๐1 ๐โผ๐1 ,๐โ๐ถ
โค๐ฝ + ๐ผ [dist( ๐๐1 (๐), ๐๐2 (๐))|๐ โ ๐ท, ๐ โ ๐1 โฉ ๐2 ] (by (5.3))
๐โผ๐1 ,๐1 ,๐2 โ๐ถ
โค๐ฝ + 2 ๐ผ [dist( ๐๐1 (๐), ๐๐2 (๐))|๐ โ ๐ท, ๐ โ ๐1 โฉ ๐2 ]
๐โผ๐2 ,๐1 ,๐2 โ๐ถ
โค๐ฝ + 2 ยท 11๐ฝ โค 25๐ฝ . (by (5.2))
To finish the proof, the only thing left is a Markov argument. If ๐ผ๐โ๐ถ [ฮ( ๐๐ , ๐)] โค 25๐ฝ , then
at least half of the sets ๐ โ ๐ถ satisfies ฮ( ๐๐ , ๐) โค 50๐ฝ, and we finish the proof.
5.4 Global direct product function
Proof of Lemma 5.6. Recall ๐ is the set of sets which are successful with respect to our fixed
string ๐ฅ. From Lemma 5.4,
Pr [๐ด1 , ๐ด2 โ ๐ and ๐ ๐ด1 , ๐ ๐ด2 are ๐1 -consistent] โฅ ๐ 5 .
[๐]
๐ด1 ,๐ด2 โ( ๐/10)
T HEORY OF C OMPUTING, Volume 19 (3), 2023, pp. 1โ56 42
E XPONENTIALLY S MALL S OUNDNESS FOR THE D IRECT P RODUCT Z- TEST
We apply Theorem 5.5 on the family of functions โฑ = {๐ ๐ด } ๐ดโ๐ . Let ๐ : [๐] ๐ โ [๐] ๐ be the
global direct product function promised from the theorem. Fix ๐2 = 50๐1 and let ๐ โ be
๐ โ = {๐ด | ๐ด โ ๐, ๐ ๐ด is ๐2 -consistent with ๐} .
From the theorem, Pr๐ดโ [๐] [๐ด โ ๐ โ ] โฅ ๐ 5 /4 .
(๐/10)
For every ๐ง โ [๐] ๐ , ๐ด โ ๐ โ , let ๐ธ(๐ด, ๐ง) be the event
๐1 ๐ 2๐2 ๐
๐ (๐ง)๐ดยฏ โ ๐ ๐ด (๐ง ๐ดยฏ ) and ๐ ๐ด (๐ง ๐ดยฏ ) โ ๐(๐ง)๐ดยฏ .
For every ๐ด โ ๐ โ , the direct product functions ๐ ๐ด , ๐ are ๐2 -consistent. By the Chernoff bound
(Fact 2.3), for a uniform input ๐ง โ [๐] ๐ ,
2๐2 ๐ ๐2 ๐
Pr[๐ ๐ด (๐ง ๐ดยฏ ) 0 ๐(๐ง)๐ดยฏ ] โค eโ 3 .
๐ง
๐1 ๐
From Claim 5.8, for every ๐ด โ ๐, Pr๐ง [ ๐ (๐ง)๐ดยฏ โ ๐ ๐ด (๐ง ๐ดยฏ )] โฅ ๐/4 .
Therefore, for every ๐ด โ ๐ โ ,
๐1 ๐ 2๐2 ๐ ๐ ๐2 ๐
Pr [๐ธ(๐ด, ๐ง)] โฅ Pr[ ๐ (๐ง)๐ดยฏ โ ๐ ๐ด (๐ง ๐ดยฏ )] โ Pr[๐ ๐ด (๐ง) 0 ๐(๐ง)๐ดยฏ ] โฅ โ eโ 3 .
๐งโ[๐] ๐ ๐ง ๐ง 4
The same bound holds also for a uniform ๐ด โ ๐ โ .
Let ๐ต be the set of inputs,
๐
๐
๐ต = ๐ง โ [๐] Pr โ [๐ธ(๐ด, ๐ง)] โฅ .
๐ดโ๐ 8
From averaging,
๐
Pr [๐ธ(๐ด, ๐ง)] โค Pr[๐ง โ ๐ต] ยท 1 + Pr[๐ง โ ๐ต] .
๐งโ[๐] ๐ ,๐ดโ๐ โ ๐ง ๐ง 8
๐2 ๐
That is, Pr๐ง [๐ง โ ๐ต] โฅ ๐/4 โ eโ 3 โ ๐/8 โฅ ๐/10 . Fix ๐3 = 3/2 (๐1 + 2๐2 ) . We prove that for every
๐3 ๐
๐ง โ ๐ต , ๐ (๐ง) โ ๐(๐ง) , which finishes the proof.
Fix ๐ง โ ๐ต and let ๐ท โ [๐] be the set
๐ท = {๐ โ [๐] | ๐ (๐ง)๐ โ ๐(๐ง)๐ } .
๐3 ๐
Assume for a contradiction that ๐ (๐ง) 0 ๐(๐ง), i. e., |๐ท| > ๐3 ๐ .
๐1 ๐+2๐2 ๐
For each ๐ด โ ๐ โ such that ๐ธ(๐ด, ๐ง) happen, by the triangle inequality, ๐ (๐ง)๐ดยฏ โ ๐(๐ง)๐ดยฏ .
This can only happen if ๐ด is such that | ๐ดยฏ โฉ ๐ท| โค ๐1 ๐ + 2๐2 ๐ = 2|๐ท|/3 . The set ๐ด is a
uniform subset of [๐] of size ๐/10 . By the Hoeffding bound for random subset (Fact 2.4),
๐ ๐
Pr๐ด [| ๐ดยฏ โฉ ๐ท| โค 2|๐ท|/3] โค eโ 20 ๐3 . We conclude that Pr๐ด [๐ด โ ๐ โ and ๐ธ(๐ด, ๐ง)] โค eโ 20 ๐3 .
This contradicts ๐ง โ ๐ต , because for ๐ง โ ๐ต ,
1 5 ๐
Pr[๐ด โ ๐ โ and ๐ธ(๐ด, ๐ง)] โฅ Pr[๐ด โ ๐ โ ] Pr[๐ธ(๐ด, ๐ง)|๐ด โ ๐ โ ] โฅ ๐ ยท .
๐ด ๐ด ๐ด 4 8
T HEORY OF C OMPUTING, Volume 19 (3), 2023, pp. 1โ56 43
I RIT D INUR AND I NBAL L IVNI NAVON
6 Lower bounds for approximate equality
In this section we prove lower bounds for different variants of the direct product test. The lower
bounds are proven by finding a function that passes the test with some probability ๐, but is far
from any direct product function.
We start by defining when a function is far from any direct product function.
Definition 6.1. Two functions ๐1 , ๐2 : [๐] ๐ โ [๐] ๐ are (๐, ๐) close, if
๐๐
Pr ๐1 (๐ฅ) โ ๐2 (๐ฅ) โฅ ๐ .
๐ฅโ[๐] ๐
A function ๐ : [๐] ๐ โ [๐] ๐ is (๐, ๐) close to a direct product function if there are functions
๐1 , . . . , ๐ ๐ : [๐] โ [๐] such that (๐1 , . . . , ๐ ๐ ) is (๐, ๐) close to ๐ . Otherwise, ๐ : [๐] ๐ โ [๐] ๐ is
(๐, ๐) far from any direct product function.
Our direct product theorem states that if a function ๐ : [๐] ๐ โ [๐] ๐ passes Test 1 with
๐ก = ๐/10 with probability ๐ > eโ๐๐ ๐ , then ๐ is (๐/10, ๐) close to a direct product function.
2
Ideally, we want the even stronger conclusion that ๐ is (ฮฉ(๐), 0) close to a direct product function.
However, we next show that this is not possible.
Claim 6.2. For every ๐ โ โ and large enough ๐, the following holds. Let ๐ : [๐] ๐ โ {0, 1} ๐ be a
random function, i. e., such that ๐ (๐ฅ) is a uniformly chosen string in [๐] ๐ for each ๐ฅ independently.
With high probability, ๐ is (2eโ๐/10 , ๐/10) far from any direct product function.
Proof. Fix a direct product function ๐ : [๐] ๐ โ {0, 1} ๐ . For every ๐ฅ โ [๐] ๐ , by the Chernoff
๐/10 ๐/10
bound, Pr ๐ [ ๐ (๐ฅ) โ ๐(๐ฅ)] โค eโ๐/10 . The probability that ๐ (๐ฅ) โ ๐(๐ฅ) on more than 2eโ๐/10 of
1 ๐ โ๐/10 1 ๐ ๐
the inputs ๐ฅ โ [๐] ๐ is smaller than eโ 3 ๐ ยทe โค eโ 3 ( 2 ) .
There are 2๐ ๐ different direct product functions ๐ : [๐] ๐ โ {0, 1} ๐ . By union bound, with
1 ๐ ๐
probability at least 1 โ 2๐ ๐ eโ 3 ( 2 ) , the random function ๐ is (2eโ๐/10 , ๐/10) far from any direct
product function.
6.1 Testing different intersection sizes.
We next analyze a family of tests, parameterized by ๐ก1 , ๐ก2 โ [๐], that generalize our basic ๐-test
and appear as Test 5. We show that there is no direct product testing theorem for these tests,
with (ฮฉ(๐), 0) closeness, for an exponentially small ๐.
Claim 6.3. For every constant ๐ฟ > 0, large enough ๐, ๐ , ๐ โ โ such that ๐ โฅ ๐ โฅ ๐ 12 and every
๐ก1 , ๐ก2 โ [๐] such that ๐ก1 + ๐ก2 โค ๐, there exists a constant ๐ฝ > 0 and a function ๐ : [๐] ๐ โ [๐] ๐ , such
๐ฝ
that agr๐ก๐1 ,๐ก2 ( ๐ ) = ๐ โฅ eโ๐ฟ๐ , but ๐ is (๐ 2 , log ๐ ) far from any direct product function.
Proof. Let ๐ฝ be a constant that will be determined later, and denote โ = log ๐ . Let โ : [๐] โ
2๐ฝ๐
[๐] \ {1} be any function satisfying: for every ๐ โ [๐] \ {1}, Pr๐โ[๐] [โ(๐) = ๐] โค 2/๐ .
T HEORY OF C OMPUTING, Volume 19 (3), 2023, pp. 1โ56 44
E XPONENTIALLY S MALL S OUNDNESS FOR THE D IRECT P RODUCT Z- TEST
Test 5: Z-test with parameters ๐ก1 , ๐ก2 (3-query test)
1. Choose ๐ด, ๐ต, ๐ถ to be a random partition of [๐], ๐ด ๐ถ ๐ต
such that |๐ด| = ๐ก1 , |๐ต| = ๐ก2 .
๐ฅ
2. Choose uniformly at random ๐ฅ, ๐ฆ, ๐ง โ [๐] ๐ such ๐ฆ
that ๐ฅ ๐ด = ๐ฆ๐ด and ๐ฆ๐ต = ๐ง ๐ต .
๐ง
3. Accept if ๐ (๐ฅ)๐ด = ๐ (๐ฆ)๐ด and ๐ (๐ง)๐ต = ๐ (๐ฆ)๐ต .
Denote by agr๐ก๐1 ,๐ก2 ( ๐ ) the success probability of ๐ on this test.
Let ๐ : [๐] ๐ โ [๐] ๐ be the following function: for every ๐ฅ โ [๐] ๐ let ๐1 , . . . , ๐โ , ๐1 , . . . , ๐โ โ [๐]
be different random coordinates.
(
โ(๐ฅ ๐๐ ) if ๐ = ๐ ๐ for some ๐ โ [โ ]
โ๐ โ [๐], ๐ (๐ฅ)๐ =
1 otherwise.
The function ๐ has โ random โcorruptedโ coordinates per input, ๐1 , . . . , ๐โ , in which ๐ (๐ฅ)๐ ๐ is
determined by the value of ๐ฅ ๐๐ .
We analyze the success probability of Test 5 with parameters ๐ก1 , ๐ก2 on ๐ . We divide into two
cases.
1. In case max{๐ก1 , ๐ก2 } โค 0.4๐. Let ๐ฅ, ๐ฆ, ๐ง, ๐ด, ๐ต be the sets and strings chosen by the test. Then
๐ฆ
|๐ด โช ๐ต| โค 0.8๐. Let ๐1๐ฅ , . . . , ๐โ๐ฅ be the corrupted coordinates of ๐ฅ (and ๐ ๐ , ๐ ๐๐ง for ๐ฆ, ๐ง). If
๐ฆ ๐ฆ
๐1๐ฅ , . . . , ๐โ๐ฅ , ๐1 , . . . , ๐โ , ๐1๐ง , . . . , ๐โ๐ง โ ๐ด โช ๐ต, the test โmissesโ all of the corrupted coordinates,
so the test passes.
Pr[๐1๐ฅ , . . . ๐โ๐ฅ โ ๐ด โช ๐ต] = Pr[๐1๐ฅ โ ๐ด โช ๐ต] ยท ยท ยท Pr[๐โ๐ฅ โ ๐ด โช ๐ต|๐1๐ฅ . . . , ๐โ๐ฅโ1 โ ๐ด โช ๐ต] โฅ (0.1)โ ,
๐ ๐ ๐
where the last inequality is because |๐ด โช ๐ต| โค 0.8๐ and โ < 0.1๐. Therefore, even
conditioning on ๐1๐ฅ . . . , ๐โ๐ฅโ1 โ ๐ด โช ๐ต, the probability of ๐โ๐ฅ โ ๐ด โช ๐ต is at least 0.1. The same
inequality holds also for ๐ฆ and ๐ง, and we get that ๐ passes Test 5 with probability at least
(0.1)3โ .
2. In case max{๐ก1 , ๐ก2 } > 0.4๐. The test is symmetric with respect to ๐ก1 , ๐ก2 , so we can assume
w.l.o.g. that ๐ก1 โฅ ๐ก2 . Let ๐ฅ, ๐ฆ, ๐ง, ๐ด, ๐ต be the sets and strings chosen by the test. Let
๐1๐ฅ , . . . , ๐โ๐ฅ and ๐1๐ฅ , . . . , ๐โ๐ฅ be the chosen coordinates of ๐ฅ, and the same for ๐ฆ and ๐ง. If for all
๐ฆ ๐ฆ
๐ โ [โ ], ๐ ๐๐ฅ = ๐ ๐ and ๐๐๐ฅ = ๐๐ and also ๐1๐ฅ , . . . , ๐โ๐ฅ โ ๐ด and ๐1๐ฅ , . . . , ๐๐๐ฅ โ ๐ด, then the corrupted
coordinates of ๐ฅ and ๐ฆ are corrupted to the same value. If in addition ๐1๐ง , . . . , ๐โ๐ง โ ๐ด, then
the corrupted coordinates of ๐ง are not checked, and the test passes. We lower bound the
probability of these events.
2โ
๐ฆ ๐ฆ 1 1 1 1
Pr[โ๐ โ [โ ], ๐ ๐๐ฅ = ๐ ๐ and ๐๐๐ฅ = ๐๐ ] = ยท ยทยทยท โฅ .
๐ ๐ ๐โ1 ๐ โ 2โ + 1 ๐
T HEORY OF C OMPUTING, Volume 19 (3), 2023, pp. 1โ56 45
I RIT D INUR AND I NBAL L IVNI NAVON
๐ฆ ๐ฆ
This is because the probability of ๐1๐ฅ = ๐1 is 1๐ , and the probability of ๐2๐ฅ = ๐2 given that
๐ฆ
๐1๐ฅ = ๐1 is 1/(๐ โ 1) , and so forth.
Pr[๐1๐ฅ , . . . , ๐โ๐ฅ โ ๐ด and ๐1๐ฅ , . . . ๐โ๐ฅ โ ๐ด]
๐
= Pr[๐1๐ฅ โ ๐ด] ยท ยท ยท Pr[๐โ๐ฅ โ ๐ด|๐1๐ฅ , . . . , ๐โ๐ฅ , ๐1๐ฅ , . . . , ๐โ๐ฅโ1 โ ๐ด] โฅ (0.3)2โ ,
๐ ๐
where the last inequality is because |๐ด| โฅ 0.4๐, and โ < 0.05๐. Therefore, ๐ passes the
test with probability at least (1/๐)2โ ยท (0.3)2โ ยท (0.3)2โ . We pick the constant ๐ฝ such that
โ = 2๐ฝ๐/(log ๐) satisfies (1/๐)2โ ยท (0.3)4โ โฅ eโ๐ฟ๐ .
We prove next that ๐ is (๐ 2 , ๐ฝ/(log ๐)) far from any direct product function. For every
๐ โ [๐], |๐| = โ2 , ๐ค โ [๐]๐ and ๐พ โ ([๐] \ {1})๐ , let ๐ฎ๐,๐ค,๐พ = ๐ฅ โ [๐] ๐ ๐ฅ ๐ = ๐ค, ๐ (๐ฅ)๐ = ๐พ .
We say that ๐ is balanced if for every ๐, ๐ค, ๐พ,
โ2
2๐
Pr[๐ฅ โ ๐ฎ๐,๐ค,๐พ |๐ฅ ๐ = ๐ค] โค .
๐ฅ ๐
We prove that ๐ is balanced. Fix any ๐, ๐ค and ๐พ. For every ๐ฅ, ๐ (๐ฅ)๐ = ๐พ only if for every
๐ โ ๐, ๐ (๐ฅ)๐ is chosen to be corrupted to some โ(๐ฅ ๐ ) = ๐พ๐ . If there is no ๐ such that โ(๐ฅ ๐ ) = ๐พ๐ ,
it is not possible that ๐ (๐ฅ)๐ = ๐พ. For each ๐พ๐ , the probability over ๐ฅ โ [๐] ๐ , ๐ฅ ๐ = ๐ค that ๐ฅ ๐ยฏ
contains a coordinate ๐ such that โ(๐ฅ ๐ ) = ๐พ๐ is smaller than 2๐/๐ . Therefore, the probability
over ๐ฅ that there are โ2 different coordinates ๐1 , . . . , ๐ โ โ ๐ยฏ such that for all ๐, โ(๐ฅ ๐๐ ) = ๐พ๐ is
2
โ
less than (2๐/๐) (if ๐พ๐ = ๐พ๐ , then ๐ฅ needs to contain two different coordinates ๐๐ , ๐๐ such
2
that โ(๐ฅ ๐๐ ) = โ(๐ฅ ๐๐ ) = ๐พ๐ ). From this we deduce that for every ๐ โ [๐], |๐| = โ2 , ๐ค โ [๐]๐ ,
โ
Pr๐ฅ [๐ฅ โ ๐ฎ๐,๐ค,๐พ |๐ฅ ๐ = ๐ค] โค (2๐/๐) 2 , and ๐ is balanced.
We prove that a balanced function ๐ is far from any direct product function. Fix a direct
โ /2
product function ๐ : [๐] ๐ โ [๐] ๐ , and let ๐น = ๐ฅ โ [๐] ๐ ๐ (๐ฅ) โ ๐(๐ฅ) . For every ๐ฅ โ ๐น, ๐ (๐ฅ)
and ๐(๐ฅ) are equal on at least โ /2 โcorruptedโ coordinates, i. e., for every ๐ฅ โ ๐น there exists a set
๐ โ [๐], |๐| = โ /2 such that ๐ (๐ฅ)๐ = ๐(๐ฅ)๐ โ ([๐] \ {1})๐ .
For every ๐ โ [๐], |๐| = โ2 and ๐ค โ [๐]๐ let
n o
๐น๐,๐ค = ๐ฅ โ ๐น ๐ฅ ๐ = ๐ค, ๐ (๐ฅ)๐ = ๐(๐ฅ)๐ โ ([๐] \ {1})๐ .
From above, ๐น โ โช๐,๐ค ๐น๐,๐ค . The function ๐ is a direct product function, so for every ๐ and ๐ค
there is a single ๐พ such that ๐(๐ฅ)๐ = ๐พ for all ๐ฅ such that ๐ฅ ๐ = ๐ค. That is, ๐น๐,๐ค โ ๐ฎ๐,๐ค,๐พ for some
๐พ โ ([๐] \ {1})๐ . Together we get that |๐น| โค ๐,๐ค |๐น๐,๐ค | โค ๐โ ยท (2๐/๐)โ /2 ๐ ๐ . Since ๐, ๐ โฅ ๐ 12
ร
2
๐
we get that Pr๐ฅ [๐ฅ โ ๐น] โค โ (2๐/๐)โ /2 โค (2/๐)5โ โค ๐ 2 .
2
T HEORY OF C OMPUTING, Volume 19 (3), 2023, pp. 1โ56 46
E XPONENTIALLY S MALL S OUNDNESS FOR THE D IRECT P RODUCT Z- TEST
6.2 The triangle test for functions over sets.
In Test 5 with ๐ก1 + ๐ก2 = ๐, we check ๐ (๐ฆ) on all coordinates, but only part of the coordinates of
๐ (๐ฅ), ๐ (๐ง). What if we check all coordinates of all three inputs? This brings us to the triangle
test, Test 6, for functions over sets. In this test, every two out of the three inputs in the test share
a joint subset of size 2๐ . For this test we must assume that ๐ is even.
We remark that Test 5 can only be defined on a function ๐ : [๐] โ [๐] ๐ , and it is not
๐
possible to define such test on a function on tuples. This is because for ๐ : [๐] ๐ โ [๐] ๐ ,
if we choose inputs ๐ฅ, ๐ฆ, ๐ง such that ๐ฅ ๐ด = ๐ฆ๐ด , ๐ฆ๐ต = ๐ง ๐ต , it is not possible to compare ๐ (๐ฅ)๐ต
to ๐ (๐ง)๐ด , since these are different coordinates. We remark that it is possible to define a 4-
query test on functions over tuples, similar to the triangle test, with inputs ๐ฅ, ๐ฆ, ๐ง, ๐ค such that
๐ฅ ๐ด = ๐ฆ๐ด , ๐ง ๐ด = ๐ค ๐ด , ๐ฅ ๐ต = ๐ง ๐ต , ๐ฆ๐ต = ๐ค ๐ต , but we do not analyze it here.
We define distance from a direct product function in a similar way to functions over tuples.
Definition 6.4. A function ๐ : [๐] โ [๐] ๐ is (๐, ๐) far from any direct product function, if for
๐
every ๐ : [๐] โ [๐],
๐๐
Pr [ ๐ (๐) โ ๐(๐)] โค ๐.
๐โ([๐]
๐ )
Test 6: Triangle test (3-query test, for even ๐)
1. Choose disjoint ๐ , ๐ , ๐ โ [๐] of size 2๐ .
๐ ๐
2. Accept if ๐ (๐ โช ๐)๐ = ๐ (๐ โช ๐)๐ , ๐ (๐ โช ๐)๐ =
๐ (๐ โช ๐)๐ and ๐ (๐ โช ๐)๐ = (๐ โช ๐)๐ . ๐
Denote by agrฮ ( ๐ ) the success probability of ๐ on this test.
Claim 6.5. For every constant ๐ฟ > 0, large enough ๐, ๐ , ๐ โ โ such that ๐ โฅ ๐ โฅ ๐ 30 there exists a
๐ฝ
constant ๐ฝ > 0 and a function ๐ : [๐] โ [๐] ๐ , such that agrฮ ( ๐ ) = ๐ > eโ๐ฟ๐ , and ๐ is (๐ 2 , log ๐ ) far
๐
from any direct product function.
Proof. We prove the claim by constructing a function ๐ that passes the test but is far from any
direct product function.
Let ๐ฝ > 0 be a constant that will be decided later, and let โ = ๐ฝ๐/(log ๐) . We describe a
function ๐ : [๐] โ [๐] ๐ with 2โ โcorruptedโ elements per input. Let โ : [๐] โ [๐] \ {1} be
๐
an arbitrary function such that for every ๐พ โ [๐] \ {1}, Pr๐โ[๐] [โ(๐) = ๐พ] โค 2/๐ . For every
๐ โ [๐] we pick 2โ elements to corrupt ๐ on ๐ 1 , . . . , ๐ 2โ and 2โ index elements ๐1 , . . . , ๐ 2โ โ ๐.
๐
The function ๐ is defined by:
(
โ(๐ ๐ ) if ๐ = ๐ ๐ for some ๐ โ [2โ ]
โ๐ โ ๐, ๐ (๐)๐ =
1 otherwise.
T HEORY OF C OMPUTING, Volume 19 (3), 2023, pp. 1โ56 47
I RIT D INUR AND I NBAL L IVNI NAVON
Figure 2: The set ๐ โช ๐ is marked in gray.
๐๐ ๐๐
๐ ๐
๐๐ ๐๐
๐
๐๐ ๐๐
We analyze the success probability of the test. Let ๐ , ๐ , ๐ be the sets chosen by the test
algorithm. Let ๐ 1๐ , . . . , ๐โ๐ , ๐1๐ , . . . , ๐โ๐ โ ๐ be arbitrary 2โ elements in ๐, and the same for ๐, ๐.
If ๐ is such that
1. In ๐ (๐ โช ๐), the corrupted elements are ๐ 1๐ , . . . , ๐โ๐ and ๐1๐ , . . . , ๐โ๐ , and the index
elements are ๐1๐ , . . . , ๐โ๐ and ๐1๐ , . . . , ๐โ๐ .
2. In ๐ (๐ โช ๐), the corrupted elements are ๐ 1๐ , . . . , ๐โ๐ and ๐ 1๐ , . . . , ๐โ๐ , and the index elements
are ๐ 1๐ , . . . , ๐โ๐ and ๐ 1๐ , . . . , ๐โ๐ .
3. In ๐ (๐ โช๐), the corrupted elements are ๐ 1๐ , . . . , ๐โ๐ and ๐ 1๐ , . . . , ๐โ๐ , and the index elements
are ๐ 1๐ , . . . , ๐โ๐ and ๐1๐ , . . . , ๐โ๐ .
Then the corrupted elements are corrupted to the same value on all three queries ๐ (๐ โช๐), ๐ (๐ โช
๐) and ๐ (๐ โช ๐) and the test passes. See Figure 2 for an illustration (with โ = 1).
The probability that in ๐ (๐ โช ๐), the 2โ corrupted elements are ๐ 1๐ , . . . , ๐โ๐ and ๐ 1๐ , . . . , ๐โ๐
and the index elements are ๐1๐ , . . . , ๐โ๐ and ๐1๐ , . . . , ๐โ๐ is larger than ๐14โ . Therefore, ๐ satisfies
๐ฝ๐
agrฮ ( ๐ ) โฅ ๐ 12โ
1
. We choose the constant ๐ฝ to be small enough such that for โ = log ๐ , agrฮ ( ๐ ) โฅ
1
๐ 12โ
โฅ eโ๐ฟ๐ .
๐ฝ
We prove that ๐ is (๐ 2 , log ๐ )-far from any direct product function. For every ๐ฟ โ [๐], |๐ฟ| = โ
n o
and ๐พ โ ([๐] \ {1})๐ฟ , let ๐ฎ๐ฟ,๐พ = ๐ โ [๐]
๐
๐ฟ โ ๐, ๐ (๐)๐ฟ = ๐พ .
We say that the function ๐ : [๐]
๐
โ [๐] ๐ is balanced if for every ๐ฟ โ [๐], |๐ฟ| = โ and
๐พ โ ([๐] \ {1})๐ฟ ,
โ
4๐
Pr[๐ โ ๐ฎ๐ฟ,๐พ |๐ฟ โ ๐] โค .
๐ ๐
We claim that ๐ is balanced. Fix ๐ฟ and ๐พ, a set ๐ โ ๐ฎ๐ฟ,๐พ if for every ๐ โ ๐ฟ, ๐ (๐)๐ is corrupted
to โ(๐) = ๐พ๐ , if ๐ doesnโt contain ๐ such that โ(๐) = ๐พ๐ then its not possible that ๐ (๐)๐ = ๐พ๐ . For
every ๐พ๐ , the probability of ๐ โ [๐], ๐ฟ โ ๐ to be such that ๐ \ ๐ฟ contains a coordinate ๐ satisfying
๐
โ(๐) = ๐พ๐ is at most 2๐
๐ ๐โโ (the requirement that ๐ โ ๐ฟ can increase the probability of โ(๐) = ๐พ๐
T HEORY OF C OMPUTING, Volume 19 (3), 2023, pp. 1โ56 48
E XPONENTIALLY S MALL S OUNDNESS FOR THE D IRECT P RODUCT Z- TEST
๐
by a factor of at most ๐โโ < 2). The probability that ๐ \ ๐ฟ contains โ elements ๐ 1 , . . . , ๐โ such
โ โ
๐
that for all ๐ there is a different ๐ ๐ satisfying โ(๐ ๐ ) = ๐พ๐ is at most ๐ ยท ๐โ2โ
2๐
โค 4๐
๐ , so the
๐
function ๐ is balanced (the factor ๐โ2โ is because we require that the ๐ ๐ โ ๐ฟ, and are different).
We prove that a balanced ๐ is far from every direct product function. Fix a direct product
โ
n o
[๐]
function ๐ : [๐] โ [๐], and let ๐น be the set ๐น = ๐ โ ๐
๐ (๐) โ ๐(๐) . For every ๐ โ ๐น, there
is a set ๐ฟ โ ๐ of size โ such that for every ๐ โ ๐ฟ, ๐ (๐)๐ = ๐(๐) โ 1. Therefore, ๐น โ โช๐ฟโ([๐]) ๐ฎ๐ฟ,๐(๐ฟ) ,
โ
and ๐(๐ฟ) is different from 1 on all elements. This implies an upper bound on |๐น|,
โ โ
๐ ๐ โโ ๐
ร
4๐ 4๐
|๐น| โค |๐ฎ๐ฟ,๐(๐ฟ) | โค โค .
โ ๐ ๐ โโ ๐ ๐
๐ฟโ([๐]
โ )
For our choice of parameters ๐ , ๐ โฅ ๐ 30 and ๐ is (๐ 2 , โ๐ ) far from any direct product function.
A Tuples to sets restricted global structure proof
In this section we prove Lemma 4.4, restricted global structure for sets, which we restate below.
Lemma A.1 (Lemma 4.4, restated). There exists a small constant ๐ > 0, such that for every constant
๐ผ > 0, large enough ๐ โ โ and ๐ > e๐๐๐ , ๐ โ โ , the following holds.
For every function ๐ : [๐] โ [๐] ๐ , if agr๐๐/10
๐ ๐๐ก
( ๐ ) = ๐ > eโ๐๐ผ๐ , then at least (1 โ ๐ 2 โ ๐ 2 /๐) of
๐
the good pairs ๐ , ๐ are ๐ผ-DP pairs.
The restricted global structure only uses the first two queries of the test. For convenience, we
rewrite the test such that the two checks are not preformed in the same step.
Test 7: Z-test for functions over sets, with ๐ก = ๐/10 (3-query test)
1. Choose a random set ๐ โ [๐] of size ๐/10 .
๐ ๐
2. Choose ๐ , ๐ โ [๐] \ ๐ of size 9๐/10 .
3. If ๐ (๐ โช ๐)๐ โ ๐ (๐ โช ๐)๐ reject.
๐ ๐
4. Choose ๐ โ [๐] \ ๐ of size ๐/10 .
5. If ๐ (๐ โช ๐)๐ โ ๐ (๐ โช ๐)๐ reject, else accept.
Denote by agr๐๐/10
๐ ๐๐ก
( ๐ ) the success probability of ๐ on this test.
We prove the lemma by a reduction from Theorem 3.9.
Definition A.2. We associate each ๐ โ [๐] with the tuple ๐ยฎ โ [๐]|๐| obtained by sorting the
elements of ๐ in increasing order. For every string ๐ฅ โ [๐] ๐ , we define ๐(๐ฅ) = 1 if ๐ฅ has distinct
coordinates, i. e., there is no ๐ โ ๐ such that ๐ฅ ๐ = ๐ฅ ๐ , else ๐(๐ฅ) = 0.
T HEORY OF C OMPUTING, Volume 19 (3), 2023, pp. 1โ56 49
I RIT D INUR AND I NBAL L IVNI NAVON
For a string ๐ = (๐ 1 , . . . , ๐ ๐ ) and a permutation ๐ : [๐] โ [๐] let ๐ ๐ = (๐ ๐(1) , . . . , ๐ ๐(๐) ).
Definition A.3. Given a function ๐ : [๐]
๐
โ [๐] ๐ , let ๐ 0 : [๐] ๐ โ [๐] ๐ โช โฅ be defined as
follows. If ๐(๐ฅ) = 0 we set ๐ 0(๐ฅ) = โฅ. If ๐(๐ฅ) = 1 then if ๐ฅ = ๐ ยฎ (namely ๐ฅ 1 < ๐ฅ 2 < ยท ยท ยท < ๐ฅ ๐ )
we let ๐ (๐ฅ) = ๐ (๐). Otherwise there is some permutation ๐ such that ๐ฅ = (๐) ยฎ ๐ and we let
ยฎ ๐ . We call ๐ the sorting permutation for the tuple ๐ฅ.
๐ 0(๐ฅ) = ๐ (๐)
When testing the function ๐ 0 , whenever the tester queries an input ๐ฅ such that ๐ 0(๐ฅ) = โฅ, we
assume the tester rejects.
[๐] [๐] [๐]
Definition A.4. Let ๐ : ๐/10
ร 9๐/10 ร 9๐/10 โ [0, 1] be the following distribution:
1. Choose ๐ โ [๐] of size ๐/10 .
2. Choose ๐ โ [๐] of size 9๐/10 such that ๐ โฉ ๐ = โ
.
3. Choose ๐ โ [๐] of size 9๐/10 such that ๐ โฉ ๐ = โ
.
Let ๐ 0 : [๐]
๐/10
ร [๐] ๐ ร [๐] ๐ โ [0, 1] be the following distribution:
1. Choose a set ๐ด โ [๐] of size ๐/10 .
2. Choose ๐ฅ โ [๐] ๐ such that ๐(๐ฅ) = 1.
3. Choose ๐ฆ โ [๐] ๐ such that ๐ฅ ๐ด = ๐ฆ๐ด and ๐(๐ฆ) = 1.
The distribution (๐ , ๐ , ๐) โผ ๐ is the distribution used in Test 4. The distribution (๐ด, ๐ฅ, ๐ฆ) โผ
๐ 0 is the distribution of Test 2, conditioning on ๐(๐ฅ) = ๐(๐ฆ) = 1.
[๐]
If we pick (๐ , ๐ , ๐) โผ ๐, a random set ๐ด โ ๐/10 and random permutations ๐1 โ
๐ฎ๐/10 , ๐2 , ๐3 โ ๐ฎ9๐/10 , then ๐ฅ = ((๐ยฎ ๐1 ) ๐ด , ( ๐
ยฎ ๐2 ) ยฏ ) and ๐ฆ = ((๐ ยฎ ๐1 )๐ด , (๐
ยฎ ๐3 ) ยฏ ) , are distributed
๐ด ๐ด
according to ๐ . 0
Let ๐ 1 = Pr๐ฅโ[๐]๐ [๐(๐ฅ) = 0] . We bound its value. Choosing a uniform ๐ฅ โ [๐] ๐ can be done
coordinate by coordinate. For each coordinate ๐, the probability that ๐ฅ ๐ = ๐ฅ ๐ for some ๐ < ๐ is at
most ๐โ1๐ , therefore
๐
ร ๐โ1 ๐2
๐ 1 = Pr [๐(๐ฅ) = 0] โค โค .
๐ฅโ[๐] ๐ ๐ 2๐
๐=1
Fix an arbitrary ๐ฅ โ [๐] ๐ such that ๐(๐ฅ) = 1 and a set ๐ด โ [๐]. Let
๐ 2 = Pr [๐(๐ฆ) = 0 | ๐ฆ๐ด = ๐ฅ ๐ด ] .
๐ฆโ[๐] ๐
We note that the value of ๐ 2 does not depend on ๐ฅ, ๐ด. We can think of ๐ฆ as being chosen by
starting from ๐ฆ๐ด , and choosing the rest of the coordinates one by one.
๐
ร ๐โ1 ๐2
๐ 2 = Pr [๐(๐ฆ) = 0 | ๐ฆ๐ด = ๐ฅ ๐ด ] โค โค .
๐ฆ ๐ 2๐
๐=๐/10
T HEORY OF C OMPUTING, Volume 19 (3), 2023, pp. 1โ56 50
E XPONENTIALLY S MALL S OUNDNESS FOR THE D IRECT P RODUCT Z- TEST
We prove two claims connecting the test success probability on ๐ : [๐] โ [๐] ๐ to the
๐
success probability of the two-query test on the function ๐ 0 : [๐] ๐ โ [๐] ๐ โช โฅ. Recall the
notation of agrโจ๐/10 (ยท) from Test 2.
Claim A.5. For every function ๐ : [๐]
๐
โ [๐] ๐ , the function ๐ 0 : [๐] ๐ โ [๐] ๐ โช โฅ from
Definition A.3 satisfies
agrโจ๐/10 ( ๐ 0) = (1 โ ๐ 1 )(1 โ ๐2 ) Pr[ ๐ passes Item 3 of Test 4].
Proof. Choose ๐ฅ, ๐ฆ, ๐ด according to the distribution of Test 2. If ๐(๐ฅ) = 0 or ๐(๐ฆ) = 0 the test fails
by definition. When we condition on ๐(๐ฅ) = ๐(๐ฆ) = 1, the test distribution is (๐ด, ๐ฅ, ๐ฆ) โผ ๐ 0 .
Denote by ๐ the set of elements in ๐ฅ ๐ด , by ๐ the set of elements in ๐ฅ ๐ดยฏ and by ๐ the set of
elements in ๐ฆ๐ดยฏ . Let ๐1 โ ๐ฎ๐/10 be the sorting permutation for ๐ฅ ๐ด . Then ๐ , ๐ 0 satisfy ๐ 0(๐ฅ)๐ด =
( ๐ (๐ , ๐)๐ )๐1 , and ๐ 0(๐ฆ)๐ด = ( ๐ (๐, ๐)๐ )๐1 . Therefore, ๐ 0(๐ฅ)๐ด = ๐ 0(๐ฆ)๐ด โโ ๐ (๐ , ๐)๐ =
๐ (๐, ๐)๐ .
Pr[ ๐ 0 passes Test 2] = Pr [ ๐ 0(๐ฅ)๐ด = ๐ 0(๐ฆ)๐ด | ๐ฅ ๐ด = ๐ฆ๐ด ]
๐ด,๐ฅ,๐ฆ
= Pr [๐(๐ฅ) = ๐(๐ฆ) = 1 | ๐ฅ ๐ด = ๐ฆ๐ด ] Pr [ ๐ 0(๐ฅ)๐ด = ๐ 0(๐ฆ)๐ด ]
๐ด,๐ฅ,๐ฆ (๐ด,๐ฅ,๐ฆ)โผ๐ 0
=(1 โ ๐ 1 )(1 โ ๐ 2 ) Pr [ ๐ (๐ , ๐)๐ = ๐ (๐, ๐)๐ ]
(๐ ,๐ ,๐)โผ๐
=(1 โ ๐ 1 )(1 โ ๐ 2 ) Pr[ ๐ passes Item 3 of Test 4]
where Pr๐ด,๐ฅ,๐ฆ [๐(๐ฅ) = ๐(๐ฆ) = 1 | ๐ฅ ๐ด = ๐ฆ๐ด ] = (1 โ ๐1 )(1 โ ๐ 2 ) by the definition of ๐ 1 , ๐2 .
Claim A.6. For every function ๐ : [๐]
๐
โ [๐] ๐ , the function ๐ 0 : [๐] ๐ โ [๐] ๐ โช โฅ from
[๐]
[๐]
Definition A.3 satisfies the following. For every disjoint ๐ โ ๐/10
9๐/10
,๐
, every set ๐ด โ
โ
[๐], |๐ด| = ๐/10 and every pair of permutations ๐1 โ ๐ ๐/10 , ๐2 โ ๐9๐/10 , let ๐ฅ = ((๐ ยฎ ๐1 ) ๐ด , ( ๐
ยฎ ๐2 ) ยฏ )
๐ด
where the notation (๐ฆ๐ด , ๐ง ๐ดยฏ ) means that we put the elements of ๐ฆ in order in coordinates ๐ด, and we put
the elements of ๐ง in order in the remaining coordinates. Then
Pr [ ๐ 0(๐ฅ)๐ด = ๐ 0(๐ฆ)๐ด | ๐ฆ๐ด = ๐ฅ ๐ด ] = (1 โ ๐ 2 ) Pr [ ๐ (๐ โช ๐)๐ = ๐ (๐ โช ๐)๐ ] .
๐ฆ ๐โผ๐ |๐ ,๐
[๐] [๐]
Proof. Fix two disjoint subsets ๐ โ ๐/10
,๐ โ 9๐/10
, a subset ๐ด โ [๐], |๐ด| = ๐/10 , and
permutations ๐1 โ ๐ ๐/10 , ๐2 โ ๐9๐/10 . Set ๐ฅ = ((๐ ๐ ยฎ ๐2 ) ยฏ ) , since ๐ , ๐ are disjoint,
ยฎ 1 )๐ด , ( ๐
๐ด
๐(๐ฅ) = 1.
Let ๐ฆ โ [๐] ๐ be a random string such that ๐ฅ ๐ด = ๐ฆ๐ด . If ๐(๐ฆ) = 0, then ๐ 0(๐ฆ) = โฅ and
๐ 0(๐ฅ)๐ด โ ๐ 0(๐ฆ)๐ด . Conditioning on ๐(๐ฆ) = 1, the distribution over ๐ฆ is ๐ 0 |๐ด, ๐ฅ. If we take ๐ to
be the elements of ๐ฆ๐ดยฏ , then the distribution over ๐ is ๐ |๐ , ๐.
Clearly, ๐ 0(๐ฅ)๐ด = ๐ 0(๐ฆ)๐ด โโ ๐ (๐ โช ๐)๐ = ๐ (๐ โช ๐)๐ , so
Pr [ ๐ 0(๐ฅ)๐ด = ๐ 0(๐ฆ)๐ด | ๐ฆ๐ด = ๐ฅ ๐ด ] = Pr [๐(๐ฆ) = 0 | ๐ฅ ๐ด = ๐ฆ๐ด ] Pr [ ๐ 0(๐ฅ)๐ด = ๐ 0(๐ฆ)๐ด ]
๐ฆ ๐ฆ ๐ฆโผ๐ 0 |๐ด,๐ฅ
=(1 โ ๐ 2 ) Pr [ ๐ (๐ โช ๐)๐ = ๐ (๐ โช ๐)๐ ] .
๐โผ๐ |๐ ,๐
T HEORY OF C OMPUTING, Volume 19 (3), 2023, pp. 1โ56 51
I RIT D INUR AND I NBAL L IVNI NAVON
Proof of Lemma 4.4. Let ๐ : [๐] โ [๐] ๐ be a function such that agr๐๐/10
๐ ๐๐ก
( ๐ ) = ๐ > eโ๐๐ผ๐ , and let
๐
๐ 0 : [๐] ๐ โ [๐] ๐ โช โฅ be the function from Definition A.3. The constant ๐ is chosen to be small
enough so that we can apply Theorem 3.9 with ๐ผ = 1/200. Therefore, we can safely assume that
๐ผ โค 1/200.
By Claim A.5, ๐ 0 passes Test 2 with probability ๐0 = (1 โ ๐ 1 )(1 โ ๐ 2 )๐ โฅ eโ๐ ๐ผ๐ . Theorem 3.9
0
holds for the function ๐ 0 with success probability ๐0 and distance parameter ๐ผ.
[๐] [๐]
By Claim A.6, for every disjoint ๐ โ ๐/10 , ๐ โ 9๐/10 ,
Pr [ ๐ 0(๐ฅ)๐ด = ๐ 0(๐ฆ)๐ด | ๐ฆ๐ด = ๐ฅ ๐ด ] = (1 โ ๐ 2 ) Pr [ ๐ (๐ โช ๐)๐ = ๐ (๐ โช ๐)๐ ] .
๐ฆ ๐โผ๐๐ ,๐
Setting ๐ = 1 โ ๐ 1 , this means that if ๐ , ๐ are good, i. e., they satisfy
๐
Pr [ ๐ (๐ โช ๐)๐ = ๐ (๐ โช ๐)๐ ] โฅ ๐
๐ 2
then for every set ๐ด โ [๐] and permutations ๐1 , ๐2 , the restriction ๐ = (๐ด, ๐ฅ ๐ด , ๐ 0(๐ฅ)๐ด ) is good,
for ๐ฅ = ((๐ยฎ ๐1 ) ๐ด , ( ๐
ยฎ ๐2 ) ยฏ ).
๐ด
Theorem 3.9 states that with probability 1 โ ๐02 a good restriction is an ๐ผ-DP restriction. Every
pair ๐ , ๐ corresponds to the same number of pairs (๐ด, ๐ฅ), so for at least (1โ๐02 ) โฅ (1โ๐ 2 โ๐ 2 /๐) of
the pairs ๐ , ๐, there exists at least one set ๐ด and permutations ๐1 , ๐2 such that ๐ = (๐ด, ๐ฅ, ๐ 0(๐ฅ)๐ด )
is an ๐ผ-DP restriction, for ๐ฅ = ((๐ ยฎ ๐1 ) ๐ด , ( ๐
ยฎ ๐2 ) ยฏ ).
๐ด
Fix such a pair ๐ , ๐. We prove that it is an ๐ผ-DP pair. Let ๐๐ = (๐๐,๐ )๐โ๐ดยฏ be the direct product
function promised from ๐ being an ๐ผ-DP restriction.
We set ๐๐ ,๐ : [๐] โ [๐] to be the following function:
โ๐ โ [๐] ๐๐ ,๐ (๐) = Plurality {๐๐,๐ (๐)} ๐โ๐ดยฏ .
Let
[๐]
๐ฑ๐ ,๐ = ๐ โ ๐ โฉ ๐ = โ
, ๐ (๐, ๐)๐ = ๐ (๐ , ๐)๐ .
9๐/10
We show next that ๐๐ ,๐ approximates ๐ on ๐ฑ๐ ,๐ .
3๐ผ๐
Fix ๐ โ ๐ฑ๐ ,๐ such that ๐๐ ,๐ (๐) 0 ๐ (๐ โช ๐)๐ . We show that many of the tuples (๐ฅ ๐ด , ๐ค ๐ดยฏ )
obtained by permuting ๐ โช ๐ are โnot DPโ, namely ๐ (๐ฅ ๐ด , ๐ค ๐ดยฏ )๐ดยฏ is far from ๐๐ (๐ค) for ๐ค = ๐ ยฎ ๐3
for many choices of the permutation ๐3 . Since ๐ is a DP-restriction this must be a rare event,
allowing us to upper bound the fraction of such ๐.
Let ๐ต โ ๐ be a set of exactly 3๐ผ๐ elements on which ๐๐ ,๐ (๐) and ๐ (๐ โช ๐)๐ differ. That is,
|๐ต| = 3๐ผ๐ and for each ๐ โ ๐ต, ๐๐ ,๐ (๐) โ ๐ (๐ โช ๐)๐ .
For every ๐ โ ๐ต, since ๐๐ ,๐ (๐) is the most frequent value among ๐๐,๐ (๐), for at least half of
the coordinates ๐ โ ๐ด,ยฏ ๐๐,๐ (๐) โ ๐ (๐ โช ๐)๐ . We call such coordinates ๐ bad (for ๐), and the rest
of the coordinates good. Let ๐3 be a random permutation on 9๐/10 elements, so ๐ค = ๐ ยฎ ๐3 places
the element ๐ in a random location. Let ๐ผ๐ be the random variable indicating that ๐ is mapped,
via ๐3 , into a good location.
T HEORY OF C OMPUTING, Volume 19 (3), 2023, pp. 1โ56 52
E XPONENTIALLY S MALL S OUNDNESS FOR THE D IRECT P RODUCT Z- TEST
We will show that with high probability, a non-trivial portion of the elements in ๐ต are sent to
a bad location. For this we will apply the tail bound in Fact 2.6. We prove that {๐ผ๐ } ๐โ๐ต satisfy the
conditions of the fact. Fix a set ๐ ( ๐ต, denote |๐| = ๐ก and denote the elements of ๐ by ๐1 . . . , ๐ ๐ก
using an arbitrary order. Fix some ๐ 0 โ ๐ต \ ๐, then,
ร
Pr[๐ผ๐0 = 1| โง๐โ[๐ก] ๐ผ๐ ๐ = 1] = Pr โ๐ โ [๐ก], ๐3 (๐ ๐ ) = ๐ ๐ Pr ๐ผ๐0 = 1|โ๐ โ [๐ก], ๐3 (๐ ๐ ) = ๐ ๐
๐3 ๐3 ๐3
ยฏ ๐ โ ๐ ๐0
๐ 1 ,...,๐ ๐ก โ ๐ด,๐
Pr ๐ผ๐0 = 1|โ๐ โ [๐ก], ๐3 (๐ ๐ ) = ๐ ๐
โค max
ยฏ ๐ โ ๐ ๐0
๐ 1 ,...,๐ ๐ก โ ๐ด,๐ ๐3
ยฏ
0.5| ๐ด|
โค โค 0.51.
ยฏ โ |๐|
| ๐ด|
The last inequality is because |๐| โค |๐ต| โค 3๐ผ๐, and we used that ๐ผ โค 1/200. Using this inequality
we get that for every ๐ โ ๐ต, Pr๐3 [โง๐โ๐ ๐ผ๐ = 1] โค (0.51)|๐| . By Fact 2.6,
" #
ร 2
๐ผ๐ โฅ 2๐ผ๐ โค eโ3๐ผ๐ยท2( 3 โ0.51) โค e0.14๐ผ๐ .
2
Pr
๐3
๐โ๐ต
๐ผ๐
Whenever ๐3 is a permutation with ๐โ๐ต ๐ผ๐ < 2๐ผ๐, it follows that ๐ 0(๐ฅ ๐ด , ๐ค)๐ดยฏ 0 ๐๐ (๐ค) (for
ร
ยฎ ๐3 ). Therefore, we get that
๐ค = (๐)
3๐ผ๐ ๐ผ๐
โ0.14๐ผ๐
Pr ๐๐ ,๐ (๐) 0 ๐ (๐ โช ๐)๐ 1โe โค Pr ๐ (๐ฅ ๐ด , ๐ค)๐ดยฏ 0 ๐๐ (๐ค) โค ๐02 .
0
๐โ๐ฑ๐ ,๐ ๐คโ๐ฑ๐
This implies that
3๐ผ๐
Pr ๐๐ ,๐ (๐) 0 ๐ (๐ โช ๐)๐ โค ๐02 + eโ0.14๐ผ๐ โค 2๐ 2 .
๐โ๐ฑ๐ ,๐
Acknowledgement
The authors wish to thank Lรกszlรณ Babai for his infinite precision and hyper attention to detail,
and for pointing out Bernsteinโs work that predated Chernoff by decades.
References
[1] Sanjeev Arora and Madhu Sudan: Improved low-degree testing and its applications.
Combinatorica, 23(3):365โ426, 2003. Preliminary version in STOCโ97. [doi:10.1007/s00493-
003-0025-0, ECCC:TR97-003] 2
[2] Vitaly Bergelson, Terence Tao, and Tamar Ziegler: An inverse theorem for the uniformity
seminorms associated with the action of ๐ฝ ๐โ . Geom. Funct. Anal. (GAFA), 19(6):1539โ1596,
2010. [doi:10.1007/s00039-010-0051-1, arXiv:0901.2602] 2
T HEORY OF C OMPUTING, Volume 19 (3), 2023, pp. 1โ56 53
I RIT D INUR AND I NBAL L IVNI NAVON
[3] Amey Bhangale, Irit Dinur, and Inbal Livni Navon: Cube vs. cube low degree test. In
Proc. 8th Innovations in Theoret. Comp. Sci. Conf. (ITCSโ17), pp. 40:1โ31. Schloss Dagstuhlโ
Leibniz-Zentrum fuer Informatik, 2017. [doi:10.4230/LIPIcs.ITCS.2017.40, arXiv:1612.07491,
ECCC:TR16-205] 2
[4] Irit Dinur: The PCP theorem by gap amplification. J. ACM, 54(3):12, 2007. Preliminary
version in STOCโ06. [doi:10.1145/1236457.1236459, ECCC:TR05-046] 2
[5] Irit Dinur and Elazar Goldenberg: Locally testing direct product in the low error range.
In Proc. 49th FOCS, pp. 613โ622. IEEE Comp. Soc., 2008. [doi:10.1109/FOCS.2008.26] 4, 6
[6] Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra: Towards a proof
of the 2-to-1 games conjecture? In Proc. 50th STOC, pp. 376โ389. ACM Press, 2018.
[doi:10.1145/3188745.3188804, ECCC:TR16-198] 2
[7] Irit Dinur and Inbal Livni Navon: Exponentially small soundness for the direct product
Z-test. In Proc. 32nd Comput. Complexity Conf. (CCCโ17), pp. 29:1โ50. Schloss Dagstuhlโ
Leibniz-Zentrum fuer Informatik, 2017. [doi:10.4230/LIPIcs.CCC.2017.29] 1
[8] Irit Dinur and David Steurer: Direct product testing. In Proc. 29th IEEE Conf. on Comput.
Complexity (CCCโ14), pp. 188โ196. IEEE Comp. Soc., 2014. [doi:10.1109/CCC.2014.27,
ECCC:TR13-179] 6, 14, 31, 36
[9] Oded Goldreich and Shmuel Safra: A combinatorial consistency lemma with application
to proving the PCP theorem. SIAM J. Comput., 29(4):1132โ1154, 2000. Preliminary version
in RANDOMโ97. [doi:10.1137/S0097539797315744, ECCC:TR96-047] 2
[10] Torben Hagerup and Christine Rรผb: A guided tour of Chernoff bounds. Inform. Process.
Lett., 33(6):305โ308, 1990. [doi:10.1016/0020-0190(90)90214-I] 11
[11] Wassily Hoeffding: Probability inequalities for sums of bounded random variables. J. Amer.
Statistical Association, 58(301):13โ30, 1963. Also available in The Collected Works of Wassily
Hoeffding, 1994, pp. 409โ426, Springer and at JSTOR. [doi:10.1080/01621459.1963.10500830]
11, 12
[12] Russell Impagliazzo and Valentine Kabanets: Constructive proofs of concentration
bounds. In Proc. 14th Internat. Workshop on Randomization and Computation (RANDOMโ10),
pp. 617โ631. Springer, 2010. [doi:10.1007/978-3-642-15369-3_46] 10, 12
[13] Russell Impagliazzo, Valentine Kabanets, and Avi Wigderson: New direct-product testers
and 2-query PCPs. SIAM J. Comput., 41(6):1722โ1768, 2012. Preliminary version in STOCโ09.
[doi:10.1137/09077299X, ECCC:TR09-090] 2, 5, 6, 7, 8, 13, 28, 30
[14] Subhash Khot, Dor Minzer, and Muli Safra: On independent sets, 2-to-2 games,
and Grassmann graphs. In Proc. 49th STOC, pp. 576โ589. ACM Press, 2017.
[doi:10.1145/3055399.3055432, ECCC:TR16-124] 2
T HEORY OF C OMPUTING, Volume 19 (3), 2023, pp. 1โ56 54
E XPONENTIALLY S MALL S OUNDNESS FOR THE D IRECT P RODUCT Z- TEST
[15] Michael Mitzenmacher and Eli Upfal: Probability and Computing: Randomized Algorithms
and Probabilistic Analysis. Cambridge Univ. Press, 2005. [doi:10.1017/CBO9780511813603]
11
[16] Elchanan Mossel, Krzysztof Oleszkiewicz, and Arnab Sen: On reverse hypercontrac-
tivity. Geom. Funct. Anal. (GAFA), 23(3):1062โ1097, 2013. [doi:10.1007/s00039-013-0229-4,
arXiv:1108.1210] 8, 12
[17] Alessandro Panconesi and Aravind Srinivasan: Randomized distributed edge coloring
via an extension of the chernoff-hoeffding bounds. SIAM J. Comput., 26(2):350โ368, 1997.
[doi:10.1137/S0097539793250767] 12
[18] Ran Raz: A parallel repetition theorem. SIAM J. Comput., 27(3):763โ803, 1998. Preliminary
version in STOCโ95. [doi:10.1137/S0097539795280895] 2
[19] Ran Raz and Shmuel Safra: A sub-constant error-probability low-degree test, and a
sub-constant error-probability PCP characterization of NP. In Proc. 29th STOC, pp. 475โ484.
ACM Press, 1997. [doi:10.1145/258533.258641] 2
AUTHORS
Irit Dinur
Professor
Department of Applied Mathematics
and Computer Science
The Weizmann Institute of Science
Rehovot, Israel
irit dinur weizmann ac il
http://www.wisdom.weizmann.ac.il/~dinuri/
Inbal Livni Navon
Postdoc
Department of Computer Science
Stanford University
Stanford, CA, USA
inballn stanford edu
http://inballn.su.domains/
T HEORY OF C OMPUTING, Volume 19 (3), 2023, pp. 1โ56 55
I RIT D INUR AND I NBAL L IVNI NAVON
ABOUT THE AUTHORS
Irit Dinur is a professor at the Weizmann Institute of Science. She is interested
broadly in theoretical computer science and mathematics, and more specifically in
complexity theory, probabilistically checkable proofs, hardness of approximation,
and most recently in the growing area of high dimensional expansion. She has a
wife and three kids.
Inbal Livni Navon is a postdoc at Stanford University. She received her Ph. D.
in 2023 from the Weizmann Institute of Science where she was advised by
Irit Dinur. She is interested in Algorithmic fairness and in expander graphs
and their applications in different areas in theoretical computer science. She
is also interested in property testing, error correcting codes and hardness of
approximation.
T HEORY OF C OMPUTING, Volume 19 (3), 2023, pp. 1โ56 56