Hardness Amplification for Real-Valued Functions

Li, Yunqi; Vasudevan, Prashant Nalini

doi:10.4230/LIPIcs.CCC.2025.2

Hardness Amplification for Real-Valued Functions

Yunqi Li

Department of Computer Science, National University of Singapore, Singapore Prashant Nalini Vasudevan

Department of Computer Science, National University of Singapore, Singapore

Abstract

Given an integer-valued function $f:\{0,1\}^{n}\rightarrow\{0,1,\dots,m-1\}$ that is mildly hard to compute on instances drawn from some distribution $D$ over $\{0,1\}^{n}$ , we show that the function $g(x_{1},\dots,x_{t})=f(x_{1})+\cdots+f(x_{t})$ is strongly hard to compute on instances $(x_{1},\dots,x_{t})$ drawn from the product distribution $D^{t}$ . We also show the same for the task of approximately computing real-valued functions $f:\{0,1\}^{n}\rightarrow[0,m)$ . Our theorems immediately imply hardness self-amplification for several natural problems including Max-Clique and Max-SAT, Approximate $\#$ SAT, Entropy Estimation, etc..

Keywords and phrases:

Average-case complexity, hardness amplification

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Computational complexity and cryptography

Funding:

Both authors are supported by the National Research Foundation, Singapore, under its NRF Fellowship programme, award No. NRF-NRFF14-2022-0010.

DOI:

10.4230/LIPIcs.CCC.2025.2

Event:

40th Computational Complexity Conference (CCC 2025)

Editors:

Srikanth Srinivasan

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Hardness amplification is the process of taking a computational problem $\Pi$ and a distribution $D$ of instances over which $\Pi$ is mildly hard, and constructing a problem $\Pi^{\prime}$ and distribution $D^{\prime}$ over which $\Pi^{\prime}$ is much harder. There has been extensive work in the past studying hardness amplification for various computational tasks such as computing Boolean functions [26, 17, 12, 19, 18, 5], inverting efficient functions [26, 11], distinguishing between distributions [9], deciding languages contained in complexity classes like $\mathsf{NP}$ [21, 15, 23, 14, 6], $\mathsf{EXP}$ [24], $\#\mathsf{P}$ [20, 8], or $\mathsf{P}$ [4, 13, 7], solving optimization problems [10], for specific interesting or structured problems [3, 16, 1], etc..

In this paper, we study hardness amplification for the task of evaluating integer- or real-valued functions. We first describe our setting and results, and then demonstrate various corollaries of our theorems that motivate studying such problems.

Evaluating Functions

In our first result, we consider functions $f:\{0,1\}^{n}\rightarrow\mathbb{Z}_{m}$ , where $\mathbb{Z}_{m}$ denotes the set of integers $\left\{0,1,\dots,m-1\right\}$ , and the computational task is to compute $f(x)$ given an input $x\in\{0,1\}^{n}$ . Here, we only use $\mathbb{Z}_{m}$ to denote set without involving any modulo operations. Suppose we are given such an $f$ and a distribution $D$ on $\{0,1\}^{n}$ over which computing $f$ is $(1-\delta)$ -hard – meaning that no small circuit can correctly compute $f(x)$ with probability greater than $(1-\delta)$ when $x$ is drawn from $D$ . Our objective is to construct a function $g$ and distribution $D^{\prime}$ such that computing $g$ is $\eta$ -hard over $D^{\prime}$ for some small $\eta$ . Further, we would like $g$ to have the same type as $f$ – to take bit-strings as input and produce integers from a bounded range as output.

For Boolean functions, Yao’s XOR Lemma [26] shows that such amplification can be achieved by having $g$ be the XOR of multiple instances of $f$ ; and similar results are also known if $g$ is the Recursive Majority-of-3 of such instances [21]. We show that in this case of integer-valued functions, having $g$ be the sum (over integers) of multiple instances of $f$ achieves the same. For $t\in\mathbb{N}$ , denote by $(\mathsf{SUM}_{t}\otimes f)$ the function that takes $t$ inputs $x_{1},\dots,x_{t}\in\{0,1\}^{n}$ , and outputs the sum $\sum_{i}f(x_{i})$ .

Theorem 1.1 (Simplification of Theorem 3.1).

Suppose a function $f:\{0,1\}^{n}\rightarrow\mathbb{Z}_{m}$ is $(1-\delta)$ -hard to compute over a distribution $D$ for circuits of size $s$ . Then, for $t\in\mathbb{N}$ , the function $(\mathsf{SUM}_{t}\otimes f)$ is $\left(\frac{2m}{\sqrt{t\delta}}\right)$ -hard to compute over the product distribution $D^{t}$ for circuits of size $\left(\frac{c^{\prime}m^{2}}{t^{2}\delta^{2}\log(t)}\right)\cdot s$ , as long as $t>\frac{cm^{2}}{\delta}$ , where $c$ and $c^{\prime}$ are some universal constants.

In a typical application of this theorem (see Section 1.1 for examples), one might take $\delta$ to be a small constant, $m$ to be some polynomially large value in $n$ , assume $(1-\delta)$ -hardness for $s$ being any arbitrary polynomial in $n$ , and set $t$ to be $\omega(m^{2})$ but still some polynomial in $n$ . The theorem would then imply that $(\mathsf{SUM}_{t}\otimes f)$ is $1/\mathrm{poly}(n)$ -hard for all polynomial-sized circuits.

To place the $O(m/\sqrt{t\delta})$ -hardness we obtain in context, observe that it is not possible to show that summation generically amplifies such a function to hardness less than $\Theta(1/\sqrt{t\delta})$ . Consider, for example, a hypothetical function that takes values in $\{0,1\}$ , is easy to compute on $(1-2\delta)$ fraction of inputs, and on the remaining $2\delta$ is optimally hard (so it is not possible to do better than random guessing). This function is $(1-\delta)$ -hard. Given $t$ random inputs from the hard distribution, the hardness comes only from about $\delta t$ of the inputs. And simply guessing randomly on each of these will yield the correct value for the sum of their outputs with probability $\Omega(1/\sqrt{t\delta})$ .

Approximating Functions

In our second result, we extend the above hardness amplification to the task of approximately evaluating bounded real-valued functions. Here we consider functions $f:\{0,1\}^{n}\rightarrow[0,m)$ , and the task is, for some approximation parameter $\epsilon\in\mathbb{R}^{+}$ , to compute some value in the range $(f(x)-\epsilon,f(x)+\epsilon)$ given input $x$ . We show that summation again amplifies hardness, though with slightly different dependence on the various parameters, and also now depending on the $\epsilon$ .

Theorem 1.2 (Simplification of Theorem 4.1).

Suppose a function $f:\{0,1\}^{n}\rightarrow[0,m)$ is $(1-\delta)$ -hard to $\epsilon$ -approximate over a distribution $D$ for circuits of size $s$ . Then, the function $(\mathsf{SUM}_{t}\otimes f)$ is $10\cdot\left(\frac{m}{\epsilon\sqrt{t\delta}}\right)^{1/2}$ -hard to $\epsilon$ -approximate over the product distribution $D^{t}$ for circuits of size $\left(\frac{c^{\prime}m}{\epsilon(t\delta)^{3/2}\log(t)}\right)\cdot s$ , as long as $t>\frac{cm^{2}}{\epsilon^{2}\delta}$ , where $c$ and $c^{\prime}$ are some universal constants.

Here too, in the applications we show, parameters are set as described for Theorem 1.1 earlier, with $\epsilon=\Theta(1)$ .

Paper Outline

In the rest of this section, we describe various corollaries of the above theorems (Section 1.1) and provide an overview of the proofs of these theorems (Section 1.2). In Section 2, we set up the definitions, conventions, and hardcore lemmas needed in the rest of the paper. In Sections 3 and 4, we state and prove more comprehensive versions of Theorems 1.1 and 1.2, respectively.

1.1 Corollaries

Functions mapping bit-strings to integers or real numbers, even within limited ranges, are quite general and capture a variety of natural problems whose complexity is of significant interest – essentially any problem $\Pi$ whose solution $\Pi(x)$ for an instance $x$ is a bounded integer or real number. For such problems, our results roughly say that computing the sum of solutions to $t$ instances is a much harder problem. Such a statement is not particularly meaningful in general, but things become much more interesting if the problem $\Pi$ also happens to admit an additively homomorphic self-reduction.

That is, suppose there is an efficient algorithm $R$ such that for any inputs $x_{1},\dots,x_{t}$ , we have $\Pi(R(x_{1},\dots,x_{t}))=\sum_{i}\Pi(x_{i})$ . In this case, the problem of computing the sum of solutions of $t$ instances can be reduced back to the solving the problem $\Pi$ itself on a single instance. Then, our results can be used to show that mild hardness of $\Pi$ implies strong hardness of $\Pi$ itself, possibly on a different distribution over instances (in what is sometimes referred to as hardness self-amplification). And this requirement is weak enough that many natural and important problems have such self-reductions. Below, we show three examples, each of which is qualitatively distinct from the others.

Optimization Problems

Various natural optimization problems can be cast in terms of computing a polynomially bounded integer-valued function of the input, and further be shown to possess simple additively homomorphic self-reductions. For example, consider the Max-Clique problem where, given (the adjacency matrix of) a graph $G$ , the task is to compute the size of its largest clique. Given graphs $G_{1},\dots,G_{t}$ , we can create a new graph consisting of one copy of each $G_{i}$ , with edges between every pair of vertices that are not from the same graph. The size of the maximum clique in this composite graph is simply the sum of the maximums in all the $G_{i}$ ’s.

Another example is the $\mathsf{MaxSAT}$ problem, where given a CNF formula $\phi$ , the task is to find the maximum number of clauses satisfied by any assignment to its variables. Given $t$ formulas $\phi_{1},\dots,\phi_{t}$ on disjoint sets of variables, the maximum number of clauses of the formula $(\phi_{1}\wedge\cdots\wedge\phi_{t})$ that can be satisfied is simply the sum of the maximums of all the $\phi_{i}$ ’s. Note that both of these problems also happen to be $\mathsf{NP}$ -hard. We get the following from Theorem 1.1, following the arguments above.

Corollary 1.3.

The following holds for any problem $\Pi\in\left\{\mathsf{MaxSAT},\mathsf{MaxClique}\right\}$ . If there is a family of distributions on which $\Pi$ is $0.9$ -hard, then there is a family of distributions on which $\Pi$ is $O(n^{-0.49})$ -hard (where $n$ is the instance size). Further, if the former family is efficiently sampleable, then so is the latter.

In these corollaries, we consider the asymptotic hardness of these problems rather than for a fixed input size, which is why we need to consider a family of distributions – one distribution for each value of the instance size parameter $n$ – rather than a single distribution. And by efficiently sampleable, we mean sampleable by a polynomial-sized family of circuits. Similarly, when we just say $\eta$ -hard, we mean $\eta$ -hard for families of circuits of size any polynomial in the instance size parameter $n$ . More detailed and careful statements of all the corollaries are presented in the full version, along with sketches of their proofs. These are all asymptotic statements, and so involve applying our theorems (which are stated for arbitrary input lengths and circuit sizes) for all members of families of functions and circuits.

Hardness amplification for optimization problems, including the above examples, was studied in [10]. However, they considered the task of actually finding the maximum clique, the maximally satisfying assignment, etc., and their results are incomparable to the corollary above.

Entropy Estimation

A natural problem (that has incidentally been of some significance in cryptography [25]) is that of estimating the Shannon entropy of a distribution given its sampling algorithm (say, as a circuit). Given a distribution over $\{0,1\}^{m}$ , its entropy is some real number in the range $[0,m]$ , and Shannon entropy is also conveniently additive: for any random variables $X$ and $Y$ , we have $H(X,Y)=H(X)+H(Y)$ . We cannot use Theorem 1.1 here because the entropy is not integer-valued, but we can use Theorem 1.2 to show hardness amplification for the task of approximately computing the entropy of a given distribution.

In this case, we can in fact go further. A related decision problem, called the Entropy Difference problem, is known to be complete for the complexity class $\mathsf{SZK}$ , which consists of problems that possess statistical zero-knowledge proofs [22]. In this problem, given sampling algorithms for two distributions $D_{0}$ and $D_{1}$ , and promised that their entropies are separated by a gap of at least $1$ , the task is to tell which distribution has larger entropy. If this problem is even mildly average-case hard over some distribution of instances $(D_{0},D_{1})$ , then the task of computing the entropy of distributions to within $\pm 1/2$ is mildly average-case hard for the distribution given by sampling $(D_{0},D_{1})$ as above and randomly outputting one of the two distributions. These observations, together with Theorem 1.2, give us the following.

Corollary 1.4.

If there is a problem in $\mathsf{SZK}$ that is $0.9$ -hard over some family of distributions, then there exists a family of distributions on which $O(1)$ -approximating Shannon entropy is $O(n^{-0.24})$ -hard. Further, if the former family of distributions is efficiently sampleable, then so is the latter.

Approximate Counting

Given as input the description of a Non-deterministic Turing Machine $M$ and an input $x$ for it, define $f(M,x)$ to be the number of accepting paths in the execution of $M$ given input $x$ . This function captures the defining problem of the complexity class $\#\mathsf{P}$ . The same can be done with the $\#\mathsf{P}$ -complete problem $\#\mathsf{SAT}$ , which is the problem of counting the number of satisfying assignments to a given Boolean formula.

In both these cases, however, the function can take exponentially many values in the instance size, and so trying to apply our theorems would not give meaningful bounds. However, if we instead consider the function $g(M,x)=\log_{2}(f(M,x))$ , this function is real-valued and lies in a polynomially bounded range (as long as the formula is guaranteed to be satisfiable). Further, additive $\pm\varepsilon$ approximations to $g$ are equivalent to multiplicative $2^{\pm\epsilon}$ approximations to $f$ . Theorem 1.2 now implies the following.

Corollary 1.5.

Suppose there is a family of distributions over satisfiable Boolean formulas on which multiplicatively approximating the number of satisfying assignments to within a factor of $2$ is $0.9$ -hard. Then there is a family of distributions on which the same task is $O(n^{-0.24})$ -hard (where $n$ is the instance size). Further, if the former is efficiently sampleable, then so is the latter.

1.2 Technical Overview

In this section, we give an overview of our analysis of the hardness amplification of summation. We focus on hardness amplification of evaluating integer-valued functions (Theorem 1.1).

Hardness of $\left\{0,1\right\}$ -valued functions

We will start by showing something even simpler – hardness amplification for functions that only take two different values. Our techniques here are inspired by ideas in the proof of existing hardness amplification theorems for problems in $\mathsf{NP}$ [21].

Suppose that there is a function $f:\{0,1\}^{n}\rightarrow\{0,1\}$ , and a corresponding distribution $H$ over $\{0,1\}^{n}$ , on which the function $f$ is strongly average-case hard; that is, there is some small $\gamma=1/\mathrm{poly}(n)$ such that for any circuit $C$ of size at most $s$ ,

\Pr_{x\leftarrow H}[C(x)=f(x)]<\frac{1}{2}(1+\gamma),

For simplicity, we assume that $f$ is balanced over $H$ . That is,

\Pr_{x\leftarrow H}[f(x)=0]=\Pr_{x\leftarrow H}[f(x)=1].

For some $t\in\mathbb{N}$ , consider the function $g:\{0,1\}^{tn}\rightarrow\mathbb{Z}_{t+1}$ , where $g(x_{1},\ldots,x_{t})=f(x_{1})+\cdots+f(x_{t})$ . In the following, we will show that the average-case hardness of $g$ improves polynomially in $t$ . Particularly, for any circuits of size at most approximately $s$ , we have:

\Pr_{x\leftarrow H^{t}}[C(x)=g(x)]<\frac{\binom{t}{\frac{t}{2}}}{2^{t}}\left(1% +\frac{t}{2}\cdot\gamma\right).

(1)

Before we show this, let us understand the best hardness we can hope to show. A simple algorithm for computing $g$ is to just always output the value that $g$ is most likely to take. Since $f$ is assumed to be balanced over $H$ , this value would be $\frac{t}{2}$ .

\Pr_{x\leftarrow H^{t}}\left[g(x)=\frac{t}{2}\right]=\frac{\binom{t}{\frac{t}{% 2}}}{2^{t}}\approx\Theta\left(\frac{1}{\sqrt{t}}\right).

If the function $f$ had been optimally $(1/2)$ -hard, then this would also be the best possible algorithm for $g$ . What we have is that $f$ is $(1+\gamma)/2$ -hard for some small $\gamma$ , indicating that $f$ is still almost optimally hard. We essentially show that in this case the above algorithm is still nearly the best possible algorithm $g$ .

We start by observing that the hardness of $f$ implies the indistinguishability of the distributions $H$ conditioned on different outputs – $H|_{f(x)=0}$ and $H|_{f(x)=1}$ . That is, for any circuit $C$ of size at most $s$ ,

\left|\Pr_{x\leftarrow H}[C(x)=1|f(x)=1]-\Pr_{x\leftarrow H}[C(x)=1|f(x)=0]% \right|<\gamma.

(2)

For function $g$ , consider the performance of any circuit $\hat{C}$ for computing $g$ . We claim that, for any $k\in\mathbb{Z}_{t}$ and any $v$ in the output range of $\hat{C}$ , the following holds:

\left|\Pr_{x\leftarrow H^{t}}[\hat{C}(x)=v|g(x)=k+1]-\Pr_{x\leftarrow H^{t}}[% \hat{C}(x)=v|g(x)=k]\right|<\gamma.

(3)

To prove it, assume

\left|\Pr_{x\leftarrow H^{t}}[\hat{C}(x)=v|g(x)=k+1]-\Pr_{x\leftarrow H^{t}}[% \hat{C}(x)=v|g(x)=k]\right|\geq\gamma.

(4)

The distribution $x\leftarrow H^{t}|_{g(x)=k}$ is equivalent to the distribution sampled as follows:

1.

Independently sample $x_{1},\ldots,x_{k}\leftarrow H|_{f(x)=1}$ , and $x_{k+1},\ldots,x_{t}\leftarrow H|_{f(x)=0}$ independently
2.

Sample a uniformly random permutation $\pi$ from all possible permutations over $t$ coordinates
3.

Output $\pi(x_{1},\ldots,x_{t})$

Using this observation and the linearity of expectation, (4) implies that there must exist a fixed $(x_{1},\ldots,x_{k},x_{k+2},\ldots,x_{t})$ and a permutation $\pi$ , such that

\left|\Pr_{{x\leftarrow H,\hat{x}\leftarrow\hat{H}(x)}}\left[\hat{C}(\hat{x})=% v|f(x)=1\right]-\Pr_{{x\leftarrow H,\hat{x}\leftarrow\hat{H}(x)}}\left[\hat{C}% (\hat{x})=v|f(x)=0\right]\right|\geq\gamma.

where $\hat{H}(x)$ denotes $\pi(x_{1},\ldots,x_{k},x,x_{k+2},\ldots x_{t})$ . Then, a circuit $C:\{0,1\}^{n}\rightarrow\{0,1\}$ can be constructed by taking $x_{1},\ldots,x_{k},x_{k+2},\ldots,x_{t}$ and permutation $\pi$ as non-uniform advice and working as follows: on the input $x\in\{0,1\}^{n}$ , outputs $1$ iff $\hat{C}(\pi(x_{1},\ldots,x,\ldots,x_{t}))$ outputs $v$ . The size of $C$ is approximately the size of $\hat{C}$ , and we have

\left|\Pr_{x\leftarrow H}\left[C(x)=1|f(x)=1\right]-\Pr_{x\leftarrow H}\left[C% (x)=1|f(x)=0\right]\right|\geq\gamma,

which contradicts the hardness of $f$ as captured by (2).

Based on (3) and a simple telescoping argument, we further obtain, for any $i,j\in\mathbb{Z}_{t+1}$ and any $v$ in the output range of $\hat{C}$ ,

\left|\Pr_{x\leftarrow H^{t}}[\hat{C}(x)=v|g(x)=i]-\Pr_{x\leftarrow H^{t}}[% \hat{C}(x)=v|g(x)=j]\right|<\left|i-j\right|\cdot\gamma.

(5)

We can now bound the probability that a circuit $\hat{C}$ can correctly compute the function $g$ as:

	$\displaystyle\Pr_{x\leftarrow H^{t}}[\hat{C}(x)=g(x)]$	$\displaystyle=\sum_{k=0}^{t}\Pr_{x\leftarrow H^{t}}[g(x)=k]\Pr_{x\leftarrow H^% {t}}[\hat{C}(x)=k\|g(x)=k]$
		$\displaystyle=\sum_{k=0}^{t}\frac{\binom{t}{k}}{2^{t}}\cdot\Pr_{x\leftarrow H^% {t}}[\hat{C}(x)=k\|g(x)=k]$
		$\displaystyle<\sum_{k=0}^{t}\frac{\binom{t}{k}}{2^{t}}\left(\Pr_{x\leftarrow H% ^{t}}\left[\hat{C}(x)=k\left\|g(x)=\frac{t}{2}\right.\right]+\left\|k-\frac{t}{2% }\right\|\cdot\gamma\right)$
		$\displaystyle\leq\frac{\binom{t}{\frac{t}{2}}}{2^{t}}\cdot\sum_{k=0}^{t}\Pr_{x% \leftarrow H^{t}}\left[\hat{C}(x)=k\left\|g(x)=\frac{t}{2}\right.\right]+\sum_{% k=0}^{t}\frac{\binom{t}{k}}{2^{t}}\left\|k-\frac{t}{2}\right\|\cdot\gamma$
		$\displaystyle\leq\frac{\binom{t}{\frac{t}{2}}}{2^{t}}\left(1+\frac{t}{2}\cdot% \gamma\right).$

where the second line follows from the fact that $f$ is balanced over $H$ , the third line follows from (5), the fourth line from the maximality of the central binomial co-efficient, the fifth line from computing the sum of the series there, and the last line from the fact that the events in the probability expressions are disjoint.

The above approach to bounding the probability of computing the sum of $t$ independent instances of a function whose value between two possible outputs is strongly hard to decide is at the core of the proofs of our results.

Reducing to two outputs

Since our amplification approach is based on the strong indistinguishability of distributions over the pre-image sets of two outputs, for any evaluation problem, we will identify such a pair of indistinguishable pre-image sets based on assumption that the evaluation problem is hard. For simplicity, we will take the distribution over which the problem is hard to be the uniform distribution over $\{0,1\}^{n}$ .

Consider a function $f:\{0,1\}^{n}\rightarrow\mathbb{Z}_{m}$ that is $(1-\delta)$ -hard for circuits of size $s$ . For every $a,b\in\mathbb{Z}_{m}$ , $a\neq b$ , we define a computation problem in which we only consider the correctness on inputs whose output belongs to $\{a,b\}$ . We formalize the above problem by defining the relations $R_{a,b}$ over $\{0,1\}^{n}\times\mathbb{Z}_{m}$ :

$\blacksquare$

If $f(x)\in\left\{a,b\right\}$ , then $(x,y)\in R_{a,b}$ if and only if $y=f(x)$ ;
$\blacksquare$

If $f(x)\not\in\left\{a,b\right\}$ , then $(x,y)\in R_{a,b}$ for every $y\in\mathbb{Z}_{m}$ .

For any $x\in\{0,1\}^{n}$ , denote by $R_{a,b}(x)$ the set of $y\in\mathbb{Z}_{m}$ such that $(x,y)\in R_{a,b}$ . We show that the hardness of $f$ implies that there must exist some $a\neq b\in\mathbb{Z}_{m}$ and some distribution over their pre-image sets for which it is hard to distinguish whether $f(x)$ is $a$ or $b$ . More precisely, we show that there exists a pair $(a,b)$ such that $R_{a,b}$ is ${(1-{\delta}/{\binom{m}{2}})}$ -hard for circuits of size $\frac{s}{m^{2}}$ .

Amplifying using hardcore sets

Pick a relation $R_{a,b}$ that has such hardness. As its hardness essentially comes from the hardness of deciding between two possible outputs $a$ and $b$ , we can extend existing proofs of the hardcore lemma for Boolean functions (e.g. that of [17]) to obtain a hardcore set¹¹1Actually, what we obtain are hardcore distributions, but we assume these are sets in this overview for simplicity. for $R_{a,b}$ . This is a set $H\subseteq\{0,1\}^{n}$ of density at least $\delta^{\prime}=\delta/{\binom{m}{2}}$ such that the relation $R_{a,b}$ is $(1+\gamma)/2$ -hard over random inputs from $H$ for circuits of size roughly $\gamma^{2}s/m^{2}$ . Further, we can ensure that all inputs $x\in H$ are such that $f(x)\in\left\{a,b\right\}$ , and with only a small loss, we can also ensure that this set is balanced between the outputs $a$ and $b$ .

The rest of the argument is quite standard. Given $t$ inputs $x_{1},\dots,x_{t}$ sampled uniformly at random from $\{0,1\}^{n}$ , with high probability roughly at least a $\delta^{\prime}$ fraction of these will fall in $H$ . Looking at just these $\delta^{\prime}t$ inputs, we are essentially back in the case discussed at the beginning of this overview – that of a function that has two possible outputs, with inputs being sampled from a hard distribution balanced between these outputs. Applying the amplification arguments there to this subset of inputs, we get from (1) that computing the sum of the $f(x_{i})$ ’s for the $x_{i}$ ’s that fall in $H$ is roughly $(1/\sqrt{\delta^{\prime}t}+\sqrt{\delta^{\prime}t}\gamma)$ -hard for circuits of size roughly $\gamma^{2}s/m^{2}$ . In order to compute the sum of all the $f(x_{i})$ ’s, the sum corresponding to the above $\delta^{\prime}t$ inputs needs to be computed. So this hardness carries over to computing $\mathsf{SUM}_{t}\otimes f$ as well. Setting $\gamma=1/\delta^{\prime}t$ now gives us Theorem 1.1.

2 Preliminaries

2.1 Notations

For $m\in\mathbb{N}$ , denote the set $\{0,\ldots,m-1\}$ by $\mathbb{Z}_{m}$ (note that this is just a set, not the ring of integers modulo $m$ ). For $v,\epsilon\in\mathbb{R}$ , we use $[v\pm\epsilon)$ to denote the interval $[v-\epsilon,v+\epsilon)$ and use round brackets for open intervals and square brackets for closed intervals.

For distributions $H, G$ over the same domain $\{0,1\}^{n}$ , for any integers $0\leq k\leq t$ , the symbol $\Pi_{t}(H^{k},G^{t-k})$ stands for the following distribution: sample $x_{1},\ldots,x_{k}$ from $H$ independently and sample $x_{k+1},\ldots,x_{t}$ from $G$ independently, sample a permutation $\pi$ over $t$ entries uniformly randomly, and output $\pi(x_{1},\ldots,x_{t})$ .

For $n,t\in\mathbb{N}$ and some alphabet $\Sigma,\Sigma^{\prime}$ , given functions $f:\{0,1\}^{n}\rightarrow\Sigma$ and $g:\Sigma^{t}\rightarrow\Sigma^{\prime}$ , denote the function that outputs $g(f(x_{1}),\ldots,f(x_{t}))$ over input $(x_{1},\ldots,x_{t})$ by $g\otimes f$ . For a relation $R\subseteq\mathcal{X}\times\mathcal{Y}$ , for any $x\in\mathcal{X}$ , we define $R(x)=\{y:y\in\mathcal{Y}\wedge(x,y)\in R\}$ .

We represent real numbers using strings. In each case, the range of relevant real numbers is some $[0,m)$ that will be clear from the context, and the string is to be interpreted as a fixed-point representation of numbers in that range. That is, for any $y\in[0,m)$ , $y$ is evaluated as $y_{1}\cdot 2^{\lceil\log{m}\rceil-1}+y_{2}\cdot 2^{\lceil\log{m}\rceil-2}+% \cdots+y_{\lceil\log m\rceil}\cdot 2^{0}+y_{\lceil\log m\rceil+1}\cdot 2^{-1}+\cdots$ , where $y_{i}\in\{0,1\}$ and $y$ is represented by $(y_{1},y_{2},\ldots)$ .

2.2 Average-Case Hardness

The average-case hardness of a problem is defined with respect to a distribution over its input domain. We start by formally defining the hardness of functions and relations.

Definition 2.1 (Hardness of Evaluating Functions).

For any $\delta\in(0,1)$ , $n,l,s\in\mathbb{N}$ , consider a function $f:\{0,1\}^{n}\rightarrow\Sigma$ , where $\Sigma$ is an output domain that can be encoded by $\{0,1\}^{l}$ and $l=\lceil\log|\Sigma|\rceil$ . For a distribution $D$ over $\{0,1\}^{n}$ , $f$ is called $\delta$ -hard on $D$ for circuits of size $s$ if, for any circuit $C:\{0,1\}^{n}\rightarrow\{0,1\}^{l}$ of size at most $s$ , we have

\Pr_{x\leftarrow D}[C(x)=f(x)]<\delta.

Definition 2.2 (Hardness of Satisfying Relations).

For any $\delta\in(0,1)$ , $n,l,s\in\mathbb{N}$ , consider a relation $R\subseteq\{0,1\}^{n}\times\Sigma$ , where $\Sigma$ is an output domain that can be encoded by $\{0,1\}^{l}$ and $l=\lceil\log|\Sigma|\rceil$ . For a distribution $D$ over $\{0,1\}^{n}$ , $R$ is called $\delta$ -hard on $D$ for circuits of size $s$ , if for any circuit $C:\{0,1\}^{n}\rightarrow\{0,1\}^{l}$ of size at most $s$ ,

\Pr_{x\leftarrow D}[C(x)\in R(x)]<\delta.

Definition 2.3.

For a function $f:\{0,1\}^{n}\rightarrow[0,m)$ , the approximation problem with distance $d$ is denoted by a relation $R^{d}_{f}\subseteq\{0,1\}^{n}\times\mathbb{R}$ , where

R_{f}^{d}=\left\{(x,y):\left|f(x)-y\right|<d\right\}.

Similarly, the closed approximation is defined by

\hat{R}_{f}^{d}=\left\{(x,y):\left|f(x)-y\right|\leq d\right\}.

Definition 2.4 (Hardness of Approximating Functions).

For any $\delta\in(0,1)$ , $\alpha,s\in\mathbb{N}$ and $m,\epsilon\in\mathbb{R}$ , consider a function $f:\{0,1\}^{n}\rightarrow[0,m)$ . For a distribution $D$ over $\{0,1\}^{n}$ , $f$ is called $\delta$ -hard to approximate on $D$ with accuracy $\alpha$ and distance $\epsilon$ for circuits of size $s$ , if the relation $R\subseteq\{0,1\}^{n}\times\{0,1\}^{\alpha}$ is $\delta$ -hard on $D$ for circuits of size $s$ , where

R=\{(x,y):|f(x)-y|<\epsilon\},

and real value $y$ is encoded by a binary of length $\alpha$ .

2.3 Hardcore Lemmas

Impagliazzo’s hardcore lemma [17] implies the existence of a strongly hard subset within an instance space where the Boolean function is only mildly hard on average. In this section, we first extend the hardcore lemma to a more general setting, for relations with a closure property under majority. Then, we will demonstrate how to transform a hard distribution into a balanced one, to facilitate our subsequent proofs of hardness amplification.

The following definition of density is utilized to measure the flatness of the hardcore distribution obtained, ensuring that it can be reintegrated into the original distribution [2, Chapter 19].

Definition 2.5 (Relative Density).

For $\delta\in(0,1]$ and distributions $X, Y$ on $\{0,1\}^{n}$ , $X$ is called $\delta$ -dense with respect to $Y$ , if for any $x\in\{0,1\}^{n}$ , we have

\Pr[X=x]\leq\frac{1}{\delta}\cdot\Pr[Y=x].

The closure property under majority is highly useful for identifying the hardcore distribution of functions or relations. Several prior studies have relied on this closure property to prove the existence of hardcore distribution [17, 19, 18, 5]. We begin by formally defining majority combiner.

Definition 2.6 (Majority Combiner).

For a relation $R\subseteq\{0,1\}^{n}\times\Sigma$ and $t\in\mathbb{N}$ , a circuit $M:\Sigma^{t}\rightarrow\Sigma$ is called a majority combiner for relation $R$ over $t$ coordinates, if for any $x\in\{0,1\}^{n}$ and any $y_{1},\ldots,y_{t}\in\Sigma$ , such that $|\{i:i\in\{1,\dots,t\}\wedge y_{i}\in R(x)\}|>t/2$ , we have $M(y_{1},\ldots,y_{t})\in R(x)$ .

The key idea behind Impagliazzo’s hardcore lemma is that, if for any distribution $H$ with certain density, there always exists a circuit of slightly smaller size that solves the problem with probability more than $\frac{1}{2}+\gamma$ , for some $\gamma\in(0,1)$ , then we can construct a larger circuit by taking the majority vote of multiple carefully chosen circuits, which can result in a high probability of agreement with function $f$ , leading to a contradiction.

Lemma 2.7 (Extended Hardcore Lemma).

For $n\in\mathbb{N}$ , consider a relation $R\subseteq\{0,1\}^{n}\times\{0,1\}^{m}$ ; define $G=\{x:\forall y\in\{0,1\}^{m},y\in R(x)\}$ . Consider any distribution $D$ over $\{0,1\}^{n}$ . Consider any $\delta\in(0,1)$ , $\gamma\in(0,1/2)$ , and large enough $s\in\mathbb{N}$ . Let $t=\lceil\frac{8\log(2/\gamma\delta)}{\gamma^{2}}\rceil$ be an integer. If there exists a majority combiner for relation $R$ over $t$ coordinates of size at most $s/2$ , and $R$ is $(1-\delta)$ -hard on $D$ for circuits of size $s$ , then there is a distribution $H$ over $\{0,1\}^{n}\setminus G$ which is $\delta$ -dense with respect to $D$ , such that $R$ is $(\frac{1}{2}+\gamma)$ -hard on $H$ for circuits of size $\frac{\gamma^{2}s}{16\log(2/\gamma\delta)}$ .

$\blacktriangleright$ Remark 2.8.

The proof of Lemma 2.7 follows [17, 2] via the Min-Max theorem with some subtle adjustments, which can be found in the full version of this work. The best-known parameter for the small circuit size in the lemma is $O(\frac{\gamma^{2}s}{\log(1/\delta)})$ , whereas the bound we present here is $O(\frac{\gamma^{2}s}{\log(2/\gamma\delta)})$ . In fact, the proof in [5], which uses a multiplicative weight update method, can be directly adapted to our extended setting. For simplicity, we provide a proof for a slightly weaker bound, which suffices for our purpose.

2.4 Balancing Hardcore Distributions

Definition 2.9 (Balanced Distribution).

For a domain $\Sigma$ , given a distribution $X$ on $\{0,1\}^{n}$ and $y_{0},y_{1}\in\Sigma$ , a relation $R\subseteq\{0,1\}^{n}\times\Sigma$ is called balanced on $X$ around $\{y_{0},y_{1}\}$ , if

\Pr_{x\leftarrow X}\left[y_{0}\in R(x)\right]=\Pr_{x\leftarrow X}\left[y_{1}% \in R(x)\right]=\frac{1}{2}\text{ and }\Pr_{x\leftarrow X}\left[y_{0}\in R(x)% \wedge y_{1}\in R(x)\right]=0.

Adapting the approach in [21], we derive the following lemma, which will be useful in our later arguments. We refer the reader to the full version of this paper for the proof.

Lemma 2.10 (Balanced Hardcore).

For $\gamma\in(0,\frac{1}{2})$ , $\delta\in(0,1)$ and $s\in\mathbb{N}$ , for a relation $R\subseteq\{0,1\}^{n}\times\Sigma$ and distributions $H, D$ over $\{0,1\}^{n}$ , suppose that there exist $a,b\in\Sigma$ , $a\neq b$ , such that

(1)

For any $x\in\mathsf{Supp}(H)$ , there is exactly one of the following holds: $a\in R(x)$ or $b\in R(x)$ .
(2)

Letting $D_{a}$ denote the distribution $x\leftarrow D|_{a\in R(x)\wedge b\not\in R(x)}$ and $D_{b}$ denote the distribution $x\leftarrow D|_{b\in R(x)\wedge a\not\in R(x)}$ ; $D_{a},D_{b}$ has $\delta$ -density with respect to $D$ .

If $H$ is a $\delta$ -dense distribution with respect to $D$ and $R$ is $\frac{1}{2}(1+\gamma)$ -hard on $H$ for circuits of size $s$ , then there is a distribution $H^{\prime}$ with density $\delta$ with respect to $D$ , on which $R$ is balanced around $\{a,b\}$ and $(\frac{1}{2}+\gamma)$ -hard for circuits of size $s$ .

3 Evaluating Integer-Valued Functions

We now present our hardness amplification result for evaluating integer-valued functions. Given a function $f$ , which is somewhat hard to evaluate on average, it is feasible to show that the function $\mathsf{SUM}_{t}\otimes f$ possesses a strong average-case hardness, where $\mathsf{SUM}_{t}$ represents the summation function over $t$ coordinates. We state our main theorem below.

Theorem 3.1.

For $\delta\in(0,1)$ , $m,s,t\in\mathbb{N}$ and a distribution $D$ over $\{0,1\}^{n}$ , for any large enough $s$ , consider a function $f:\{0,1\}^{n}\rightarrow\mathbb{Z}_{m}$ that is $(1-\delta)$ -hard on $D$ for circuits of size $s$ , define a function $g:(\{0,1\}^{n})^{t}\rightarrow\mathbb{Z}_{t\cdot m}$ as follows:

g(x_{1},\ldots,x_{t})=\sum_{i=1}^{t}f(x_{i}).

Then, for $\gamma\in(0,1)$ , for large enough $s$ , $g$ is $\eta$ -hard on $D^{t}$ for circuits of size $s^{\prime}$ , where

	$\displaystyle\eta$	$\displaystyle=e^{-\mu/4}+\frac{\binom{\mu}{\lfloor\frac{\mu}{2}\rfloor}}{2^{{% \mu}}}\left(1+\lceil\frac{\mu}{2}\rceil\gamma\right),\mu=\lceil\frac{t\delta}{% m(m-1)}\rceil,$
	$\displaystyle s^{\prime}$	$\displaystyle=\frac{\gamma^{2}s}{512m^{2}\log(4m^{2}/\gamma\delta)}.$

For sufficiently small $\gamma$ , the dominant term of $\eta$ is ${\binom{\mu}{{\mu}/2}}/{2^{\mu}}=\Theta({1}/{\sqrt{\mu}})$ . Taking $t$ large enough enables us to establish hardness amplification. To prove it, we will first construct the hardcore distribution for the function $f$ , show that summation effectively amplify the hardness on this hard distribution and then generalize the result to the original distribution.

Intuitively, the hardcore distribution of any Boolean-valued function is straightforward, as the output is restricted to either yes or no. However, for integer-valued functions, the structure of a hard set is inherently more complicated. We characterize the hardcore of integer-valued functions by defining a set of new problems, simply considering two values in the output domain and an input value is only considered relevant if its corresponding output matches one of those. We show that there is a pair of values such that the resulting problem is hard. Then, we extract a hardcore from this hard problem, which possesses a good structure corresponding to the original function.

Lemma 3.2.

For $\delta\in(0,1)$ , $m,s\in\mathbb{N}$ and a distribution $D$ over $\{0,1\}^{n}$ , consider a function $f:\{0,1\}^{n}\rightarrow\mathbb{Z}_{m}$ . For any $a,b\in\mathbb{Z}_{m}$ and $a\neq b$ , define the relation $R_{a,b}\subseteq\{0,1\}^{n}\times\{0,1\}^{\lceil\log m\rceil}$ as follows:

$\blacksquare$

If $f(x)\in\{a,b\}$ , then $(x,y)\in R_{a,b}$ if and only if $y=f(x)$ ;
$\blacksquare$

If $f(x)\not\in\{a,b\}$ , then $(x,y)\in R_{a,b}$ for any $y\in\{0,1\}^{\lceil\log m\rceil}$ .

For $s\gg m^{2}\log m$ , if $f$ is $(1-\delta)$ -hard on $D$ for circuits of size $s$ , there exists a pair of $a,b\in\mathbb{Z}_{m},a\neq b$ , such that $R_{a,b}$ is $(1-\frac{2\delta}{m(m-1)})$ -hard on $D$ for circuits of size $\frac{s}{m^{2}}$ .

This lemma suggests that if the function $f$ is hard to evaluate on average, then there must exist output values $a, b$ , such that distinguishing their pre-images is also hard on average. We defer the proof to Section 3.1, and our hardcore construction is shown below.

Lemma 3.3 (Hardcore for Integer-Valued Functions).

For $\delta,\gamma\in(0,1)$ , $m,s\in\mathbb{N}$ and a distribution $D$ , consider a function $f:\{0,1\}^{n}\rightarrow\mathbb{Z}_{m}$ , which is $(1-\delta)$ -hard on $D$ for circuits of size $s$ . If $s$ is sufficient large, there exist $a,b\in\mathbb{Z}_{m},a\neq b$ and a $\frac{2\delta}{m(m-1)}$ -dense distribution $H$ (with respect to $D$ ), on which $f$ is balanced around $\{a,b\}$ and $\frac{1}{2}(1+\gamma)$ -hard for circuits of size $\frac{\gamma^{2}s}{256m^{2}\log(4m^{2}/\gamma\delta)}$ .

Proof.

Suppose $f:\{0,1\}^{n}\rightarrow\mathbb{Z}_{m}$ is $(1-\delta)$ -hard on $D$ for circuits of size $s$ , by Lemma 3.2, if $s\gg m^{2}\log m$ , there exists a pair of $a,b\in\mathbb{N},a\neq b$ , such that $R_{a,b}$ is $(1-\frac{2\delta}{m(m-1)})$ -hard on $D$ for circuits of size $\frac{s}{m^{2}}$ . This hardness implies that $\Pr_{x\leftarrow D}[f(x)=a]>\frac{2\delta}{m(m-1)}$ , then the distribution $D|_{f(x)=a}$ is $\frac{2\delta}{m(m-1)}$ -dense with respect to $D$ (and the same holds for $b$ ).

For relation $R_{a,b}$ , the majority gate is a natural choice for the combiner. For some $\gamma\in(0,1)$ , let $t=\frac{128\log(4m^{2}/\gamma\delta)}{\gamma^{2}}$ be an integer, if the size of majority-of- $t$ circuits is less than $\frac{s}{2m^{2}}$ , by Lemma 2.7, there is a $\frac{2\delta}{{m}(m-1)}$ -dense hardcore distribution $H^{\prime}$ (with respect to $D$ ) over $\{x:f(x)\in\{a,b\}\}\subseteq\{0,1\}^{n}$ , on which $R_{a,b}$ is $(\frac{1}{2}+\frac{\gamma}{4})$ -hard for circuits of size $\frac{\gamma^{2}s}{256m^{2}\log(4m^{2}/\gamma\delta)}$ . By Lemma 2.10, we can construct a distribution $H$ with density $\frac{2\delta}{m(m-1)}$ (with respect to $D$ ), on which $f$ is balanced around $\{a,b\}$ and $\frac{1}{2}(1+\gamma)$ -hard for circuits of size $\frac{\gamma^{2}s}{256m^{2}\log(4m^{2}/\gamma\delta)}$ . $\hfill\blacktriangleleft$

We believe that this hardcore distribution exhibits a desirable structure, given that the hardness of evaluating function $f$ on it can be captured by indistinguishability. In the following, we consider the inputs sampled from the hardcore distribution. It is a natural way to amplify the average-case hardness of function $f$ , by constructing the function $\mathsf{SUM}_{t}\otimes f$ . If $f$ is hard on distribution $H$ on which there are two possible outputs, then the best algorithm with restricted running time would not perform significantly better than random guessing. Consequently, the almost optimal way for guessing the value of $\mathsf{SUM}_{t}\otimes f$ on $H^{t}$ is output the one with the highest probability of occurring.

Lemma 3.4.

For $\gamma\in(0,1)$ , $m,s,t\in\mathbb{N}$ and $a,b\in\mathbb{Z}_{m}$ , consider a hardcore distribution $H\subseteq\{0,1\}^{n}$ , on which function $f:\{0,1\}^{n}\rightarrow\mathbb{Z}_{m}$ is balanced around $\{a,b\}$ and $\frac{1}{2}(1+\gamma)$ -hard for circuits of size $s$ . Define the function $g:(\{0,1\}^{n})^{t}\rightarrow\mathbb{Z}_{t\cdot m}$ as follows:

g(x_{1},\ldots,x_{t})=\sum_{i=1}^{t}f(x_{i}).

For $k\in\mathbb{N},0<k\leq t$ and any other distribution $G$ over $(\{0,1\}^{n})^{t-k}$ , for sufficient large $s$ , specifically $s\gg\log(t\cdot m)$ , the function $g$ is $\eta$ -hard on $\Pi_{t}(H^{k},G)$ for circuits of size $\frac{s}{2}$ , where

\eta=\frac{\binom{k}{\lfloor\frac{k}{2}\rfloor}}{2^{k}}\left(1+\lceil\frac{k}{% 2}\rceil\gamma\right).

This lemma demonstrates that summation can effectively amplify the hardness over the hardcore distribution, for which the proof will be presented in Section 3.2. However, the hardcore lemma only ensures the existence of a hard distribution without guaranteeing efficient sampling. Therefore, to derive a more meaningful hardness result, we will eventually focus on the hardness on the original distribution.

One direct approach is to embed this distribution into the original one with some probability mass parameterized by its relative density. When sampling instances from the original distribution a sufficient number of times, the number of instances sampled from the hard one will concentrate around the expected value. Based on this observation, we proceed to prove our main theorem.

Theorem 3.1. [Restated, see original statement.]

For $\delta\in(0,1)$ , $m,s,t\in\mathbb{N}$ and a distribution $D$ over $\{0,1\}^{n}$ , for any large enough $s$ , consider a function $f:\{0,1\}^{n}\rightarrow\mathbb{Z}_{m}$ that is $(1-\delta)$ -hard on $D$ for circuits of size $s$ , define a function $g:(\{0,1\}^{n})^{t}\rightarrow\mathbb{Z}_{t\cdot m}$ as follows:

g(x_{1},\ldots,x_{t})=\sum_{i=1}^{t}f(x_{i}).

Then, for $\gamma\in(0,1)$ , for large enough $s$ , $g$ is $\eta$ -hard on $D^{t}$ for circuits of size $s^{\prime}$ , where

	$\displaystyle\eta$	$\displaystyle=e^{-\mu/4}+\frac{\binom{\mu}{\lfloor\frac{\mu}{2}\rfloor}}{2^{{% \mu}}}\left(1+\lceil\frac{\mu}{2}\rceil\gamma\right),\mu=\lceil\frac{t\delta}{% m(m-1)}\rceil,$
	$\displaystyle s^{\prime}$	$\displaystyle=\frac{\gamma^{2}s}{512m^{2}\log(4m^{2}/\gamma\delta)}.$

Proof.

Theorem 3.1 For a function $f:\{0,1\}^{n}\rightarrow\mathbb{Z}_{m}$ , which is $(1-\delta)$ -hard on $D$ for circuits of size $s$ , by Lemma 3.3, there exists $a,b\in\mathbb{Z}_{m},a\neq b$ and a $\frac{2\delta}{m(m-1)}$ -dense distribution $H$ with respect to $D$ , such that $f$ is balanced around $\{a,b\}$ and $\frac{1}{2}(1+\gamma)$ -hard on $H$ for circuits of size $\hat{s}=\frac{\gamma^{2}s}{256m^{2}\log(4m^{2}/\gamma\delta)}$ .

$H$ has density $\hat{\delta}=\frac{2\delta}{m(m-1)}$ , then there exists a distribution $G$ over $\{0,1\}^{n}$ , such that $D=\hat{\delta}H+(1-\hat{\delta})G$ . For $t\in\mathbb{N}$ , we have

D^{t}=\sum_{k=0}^{t}\binom{t}{k}\hat{\delta}^{k}(1-\hat{\delta})^{t-k}\cdot\Pi% _{t}(H^{k},G^{t-k}).

Therefore, for any large enough $s\in\mathbb{N}$ , and any circuit $C$ of size $s^{\prime}=\frac{\hat{s}}{2}$ , by Lemma 3.4,

	$\displaystyle\Pr_{x\leftarrow D^{t}}[C(x)=g(x)]$
	$\displaystyle=\sum_{k=0}^{t}\binom{t}{k}\cdot\hat{\delta}^{k}(1-\hat{\delta})^% {t-k}\cdot\Pr_{x\leftarrow\Pi_{t}(H^{k},G^{t-k})}[C(x)=g(x)]$
	$\displaystyle\leq\sum_{k=0}^{\mu-1}\binom{t}{k}\cdot\hat{\delta}^{k}(1-\hat{% \delta})^{t-k}+\sum_{k=\mu}^{t}\binom{t}{k}\cdot\hat{\delta}^{k}(1-\hat{\delta% })^{t-k}\cdot\frac{\binom{\mu}{\lfloor\frac{\mu}{2}\rfloor}}{2^{\mu}}\left(1+% \lceil\frac{\mu}{2}\rceil\gamma\right)$
	$\displaystyle<\sum_{k=0}^{\mu-1}\binom{t}{k}\cdot\hat{\delta}^{k}(1-\hat{% \delta})^{t-k}+\frac{\binom{\mu}{\lfloor\frac{\mu}{2}\rfloor}}{2^{\mu}}\left(1% +\lceil\frac{\mu}{2}\rceil\gamma\right)$
	$\displaystyle<e^{-\mu/4}+\frac{\binom{\mu}{\lfloor\frac{\mu}{2}\rfloor}}{2^{{% \mu}}}\left(1+\lceil\frac{\mu}{2}\rceil\gamma\right),$

where $\mu=\lceil\frac{t\hat{\delta}}{2}\rceil$ . The last inequality is obtained by Chernoff bound, where the first term is equivalent to the probability that a binomial distribution with parameter $(n,\hat{\delta})$ samples a value less than $\mu$ . $\hfill\blacktriangleleft$

3.1 Proof of Lemma 3.2

Lemma 3.2. [Restated, see original statement.]

For $\delta\in(0,1)$ , $m,s\in\mathbb{N}$ and a distribution $D$ over $\{0,1\}^{n}$ , consider a function $f:\{0,1\}^{n}\rightarrow\mathbb{Z}_{m}$ . For any $a,b\in\mathbb{Z}_{m}$ and $a\neq b$ , define the relation $R_{a,b}\subseteq\{0,1\}^{n}\times\{0,1\}^{\lceil\log m\rceil}$ as follows:

$\blacksquare$

If $f(x)\in\{a,b\}$ , then $(x,y)\in R_{a,b}$ if and only if $y=f(x)$ ;
$\blacksquare$

If $f(x)\not\in\{a,b\}$ , then $(x,y)\in R_{a,b}$ for any $y\in\{0,1\}^{\lceil\log m\rceil}$ .

For $s\gg m^{2}\log m$ , if $f$ is $(1-\delta)$ -hard on $D$ for circuits of size $s$ , there exists a pair of $a,b\in\mathbb{Z}_{m},a\neq b$ , such that $R_{a,b}$ is $(1-\frac{2\delta}{m(m-1)})$ -hard on $D$ for circuits of size $\frac{s}{m^{2}}$ .

Proof.

Assume that, for any $a,b\in\mathbb{Z}_{m}$ , $a<b$ , there is a circuit $C_{a,b}:\{0,1\}^{n}\rightarrow\{0,1\}^{\lceil\log m\rceil}$ of size $\frac{s}{m^{2}}$ , such that

\Pr_{x\leftarrow D}[C_{a,b}(x)\in R_{a,b}(x)]\geq 1-\frac{2\delta}{m(m-1)}.

Let $C_{b,a}=C_{a,b}$ . Then, we can construct a circuit $C$ as follows:

1.

Input: $x\in\{0,1\}^{n}$
2.
For $i\in\{0,1,\ldots,m-1\}$ :
- $\blacksquare$
  
  If for every $j\neq i$ , $C_{i,j}(x)=i$ holds, return $i$ .
3.

Return $\bot$ .

During the process, $C$ compares each output of $C_{i,j}(x)$ with $i$ , which means there are $\Theta(m^{2})$ comparison of $\Theta(\log m)$ bits, so the circuit complexity of $C$ is at most $\binom{m}{2}\cdot\frac{s}{m^{2}}+c\cdot m^{2}\log m$ , where $c$ is a constant. If $s\gg m^{2}\log m$ , the size of $C$ is at most $s$ .

By taking the union bound, we have

\Pr_{x\leftarrow D}\left[\exists(a,b),a<b:C_{a,b}(x)\not\in R_{a,b}(x)\right]% \leq\sum_{\begin{subarray}{c}a<b\end{subarray}}\Pr_{x\leftarrow D}[C_{a,b}(x)% \not\in R_{a,b}(x)]\leq\delta.

For any input $x$ , there exists at most one $i$ , such that for every $j\neq i$ , $C_{i,j}(x)$ outputs $i$ . If not, we have $C_{i,j}(x)=i=j$ , which leads to a contradiction.

If every $C_{a,b}(x)$ outputs a correct value in $R_{a,b}(x)$ , there exists a unique $i=f(x)$ , such that $C_{i,j}(x)\in R_{i,j}(x)$ for every $j\neq i$ , then $C$ computes $f(x)$ correctly.

\Pr_{x\leftarrow D}[C(x)=f(x)]\geq\Pr_{x\leftarrow D}\left[\forall(a,b),a<b:C_% {a,b}(x)\in R_{a,b}(x)\right]\geq 1-\delta,

which contradicts the fact that $f$ is $(1-\delta)$ -hard for circuits of size $s$ . $\hfill\blacktriangleleft$

3.2 Proof of Lemma 3.4

Lemma 3.4. [Restated, see original statement.]

For $\gamma\in(0,1)$ , $m,s,t\in\mathbb{N}$ and $a,b\in\mathbb{Z}_{m}$ , consider a hardcore distribution $H\subseteq\{0,1\}^{n}$ , on which function $f:\{0,1\}^{n}\rightarrow\mathbb{Z}_{m}$ is balanced around $\{a,b\}$ and $\frac{1}{2}(1+\gamma)$ -hard for circuits of size $s$ . Define the function $g:(\{0,1\}^{n})^{t}\rightarrow\mathbb{Z}_{t\cdot m}$ as follows:

g(x_{1},\ldots,x_{t})=\sum_{i=1}^{t}f(x_{i}).

For $k\in\mathbb{N},0<k\leq t$ and any other distribution $G$ over $(\{0,1\}^{n})^{t-k}$ , for sufficient large $s$ , specifically $s\gg\log(t\cdot m)$ , the function $g$ is $\eta$ -hard on $\Pi_{t}(H^{k},G)$ for circuits of size $\frac{s}{2}$ , where

\eta=\frac{\binom{k}{\lfloor\frac{k}{2}\rfloor}}{2^{k}}\left(1+\lceil\frac{k}{% 2}\rceil\gamma\right).

Proof.

Consider a hardcore distribution $H$ and a function $f:\{0,1\}^{n}\rightarrow\mathbb{Z}_{m}$ , such that $f$ is balanced around $\{a,b\}$ and $\frac{1}{2}(1+\gamma)$ -hard on $H$ for circuits of size $s$ . Let $H_{a}$ denote the distribution $x\leftarrow H|_{f(x)=a}$ and $H_{b}$ denote $x\leftarrow H|_{f(x)=b}$ , we have $H=\frac{1}{2}H_{a}+\frac{1}{2}H_{b}$ . For any $i,k\in\mathbb{N}$ , denote $\Pi(H_{a}^{i},H_{b}^{k-i})$ by $H_{i}^{k}$ Then, consider any $\hat{x}=(\hat{x}_{1},\ldots,\hat{x}_{t-k})\in(\{0,1\}^{n})^{t-k}$ and a permutation $\pi$ of $t$ entries, we claim the following fact.

Claim 3.5.

If $s\gg\log(t\cdot m)$ , for any circuit $C:(\{0,1\}^{n})^{t}\rightarrow\{0,1\}^{\lceil\log tm\rceil}$ of size at most $\frac{s}{2}$ and any $i\in\mathbb{Z}_{k}$ , $v\in\mathbb{Z}_{t\cdot m}$ , we have

\left|\Pr_{\bar{x}\leftarrow H^{k}}\left[C(\pi(\bar{x},\hat{x}))=v|\bar{x}\in H% _{i+1}^{k}\right]-\Pr_{\bar{x}\leftarrow H^{k}}\left[C(\pi(\bar{x},\hat{x}))=v% |\bar{x}\in H_{i}^{k}\right]\right|<\gamma.

By Claim 3.5 (which is proven below), combined with triangle inequality, for any $i,j\in\mathbb{Z}_{k}$ ,

\Pr_{\bar{x}\leftarrow H^{k}}\left[C(\pi(\bar{x},\hat{x}))=v|\bar{x}\in H_{i}^% {k}\right]<\Pr_{\bar{x}\leftarrow H^{k}}\left[C(\pi(\bar{x},\hat{x}))=v|\bar{x% }\in H_{j}^{k}\right]+\left|i-j\right|\gamma.

Let $\Delta=\sum_{i=1}^{t-k}f(\hat{x}_{i})$ . For any circuit $C:(\{0,1\}^{n})^{t}\rightarrow\{0,1\}^{\lceil\log tm\rceil}$ of size at most $\frac{s}{2}$ ,

	$\displaystyle\Pr_{\bar{x}\leftarrow H^{k}}\left[C(\pi(\bar{x},\hat{x}))=g(\pi(% \bar{x},\hat{x}))\right]$
	$\displaystyle=\sum_{i=0}^{k}\Pr_{\bar{x}\leftarrow H^{k}}\left[\bar{x}\in H_{i% }^{k}\right]\Pr_{\bar{x}\leftarrow H^{k}}\left[C(\pi(\bar{x},\hat{x}))=g(\bar{% x},\hat{x})\left\|\bar{x}\in H_{i}^{k}\right.\right]$
	$\displaystyle=\sum_{i=0}^{k}\Pr_{\bar{x}\leftarrow H^{k}}\left[\bar{x}\in H_{i% }^{k}\right]\Pr_{\bar{x}\leftarrow H^{k}}\left[C(\pi(\bar{x},\hat{x}))=ai+b(k-% i)+\Delta\left\|\bar{x}\in H_{i}^{k}\right.\right]$
	$\displaystyle<\frac{1}{2^{k}}\sum_{i=0}^{k}\binom{k}{i}\left(\Pr_{\bar{x}% \leftarrow H^{k}}\left[C(\pi(\bar{x},\hat{x}))=ai+b(k-i)+\Delta\left\|\bar{x}% \in H_{\lfloor\frac{k}{2}\rfloor}^{k}\right.\right]+\left\|i-\lfloor\frac{k}{2}% \rfloor\right\|\gamma\right)$
	$\displaystyle\leq\frac{1}{2^{k}}\left(\binom{k}{\lfloor\frac{k}{2}\rfloor}\sum% _{i=0}^{k}\Pr_{\bar{x}\leftarrow H^{k}}\left[C(\pi(\bar{x},\hat{x}))=ai+b(k-i)% +\Delta\left\|\bar{x}\in H_{\lfloor\frac{k}{2}\rfloor}^{k}\right.\right]+\lceil% \frac{k}{2}\rceil\gamma\cdot\binom{k}{\lfloor\frac{k}{2}\rfloor}\right)$
	$\displaystyle\leq\frac{\binom{k}{\lfloor\frac{k}{2}\rfloor}}{2^{k}}\left(1+% \lceil\frac{k}{2}\rceil\gamma\right).$

Hence, for any distribution $G$ over $\left(\{0,1\}^{n}\right)^{t-k}$ ,

\displaystyle\Pr_{\bar{x}\leftarrow\Pi(H^{k},G)}\left[C(\bar{x})=g(\bar{x})% \right]\leq\frac{\binom{k}{\lfloor\frac{k}{2}\rfloor}}{2^{k}}\left(1+\lceil% \frac{k}{2}\rceil\gamma\right).

$\hfill\blacktriangleleft$

3.2.1 Proof of Claim 3.5

Claim 3.5. [Restated, see original statement.]

If $s\gg\log(t\cdot m)$ , for any circuit $C:(\{0,1\}^{n})^{t}\rightarrow\{0,1\}^{\lceil\log tm\rceil}$ of size at most $\frac{s}{2}$ and any $i\in\mathbb{Z}_{k}$ , $v\in\mathbb{Z}_{t\cdot m}$ , we have

\left|\Pr_{\bar{x}\leftarrow H^{k}}\left[C(\pi(\bar{x},\hat{x}))=v|\bar{x}\in H% _{i+1}^{k}\right]-\Pr_{\bar{x}\leftarrow H^{k}}\left[C(\pi(\bar{x},\hat{x}))=v% |\bar{x}\in H_{i}^{k}\right]\right|<\gamma.

Proof.

Without loss of generality, suppose there exists a circuit $C:(\{0,1\}^{n})^{t}\rightarrow\{0,1\}^{\lceil\log tm\rceil}$ of size at most $\frac{s}{2}$ and $i\in\mathbb{Z}_{k}$ , $k\in\mathbb{Z}_{t\cdot m}$ , such that

\left|\Pr_{\bar{x}\leftarrow H^{k}}\left[C(\pi(\bar{x},\hat{x}))=v|\bar{x}\in H% _{i+1}^{k}\right]-\Pr_{\bar{x}\leftarrow H^{k}}\left[C(\pi(\bar{x},\hat{x}))=v% |\bar{x}\in H_{i}^{k}\right]\right|\geq\gamma.

Then, there must exists a tuple $(x_{1},x_{2},\ldots,x_{k-1})$ and a permutation $\pi_{k}$ of $k$ entries, such that

\left|\Pr_{x\leftarrow H}\left[C(\pi(\bar{H}(x),\hat{x}))=v|x\in H_{a}\right]-% \Pr_{x\leftarrow H}\left[C(\pi(\bar{H}(x))=v|x\in H_{b}\right]\right|\geq\gamma,

where $\bar{H}(x)$ denotes $\pi_{k}(x,x_{1},\dots,x_{k-1})$ .

Construct a circuit $C^{\prime}$ , implementing $C$ by taking an input of length $n$ , along with fixed $\pi,\hat{x}$ and $\pi_{k},(x_{1},\ldots,x_{k-1}),v$ as the non-uniform advice, outputs $a$ if and only if $C$ outputs $v$ and outputs $b$ otherwise. Then,

\left|\Pr_{x\leftarrow H}[C^{\prime}(x)=a|x\in H_{a}]-\Pr_{x\leftarrow H}[C^{% \prime}(x)=b|x\in H_{b}]\right|\geq\gamma.

Therefore, the probability that $C^{\prime}$ correctly compute $f$ is

\Pr_{x\leftarrow H}[C^{\prime}(x)=f(x)]=\frac{1}{2}\Pr[C^{\prime}(x)=a|x\in H_% {a}]+\frac{1}{2}\Pr[C^{\prime}(x)=b|x\in H_{b}]\geq\frac{1}{2}(1+\gamma),

which contradict to $f$ is $\frac{1}{2}(1+\gamma)$ -hard on $H$ . $\hfill\blacktriangleleft$

4 Approximating Real-Valued Functions

In this section, we extend our results to real-valued functions. To avoid any precision loss introduced by encoding, we assume that for any open interval of length $\frac{\epsilon}{2}$ , there is a value that can be encoded by $\{0,1\}^{\alpha}$ in the interval. Therefore, for any approximation considered below, we always assume $\alpha>\log(m/\epsilon)+4$ .

Theorem 4.1.

For $\delta\in(0,1)$ , $m,\epsilon\in\mathbb{R}$ , $\alpha,s,t\in\mathbb{N}$ , $\alpha>\log(m/\epsilon)+4$ and a distribution $D$ over $\{0,1\}^{n}$ , consider a function $f:\{0,1\}^{n}\rightarrow[0,m)$ that is $(1-\delta)$ -hard to approximate on $D$ with accuracy $\alpha$ and distance $\epsilon$ , for circuits of size $s$ . For any large enough $t$ , define a function $g:\left(\{0,1\}^{n}\right)^{t}\rightarrow[0,t\cdot m)$ as follows:

g(x_{1},\ldots,x_{t})=\sum_{i=1}^{t}f(x_{i}).

Then, for $\gamma\in(0,1)$ , for any large enough $s$ , $g$ is $\eta$ -hard to approximate on $D^{t}$ with accuracy $\alpha^{\prime}$ and distance $\epsilon$ , $\alpha^{\prime}>\log(t\cdot m/\epsilon)+4$ , for circuits of size $s^{\prime}$ , where

	$\displaystyle\eta$	$\displaystyle=e^{-\mu/4}+\frac{\binom{\mu}{\frac{\mu}{2}}}{2^{\mu}}\left(6+% \frac{\mu}{2}\gamma\right),\mu=\frac{\epsilon}{m}\sqrt{2t\delta},$
	$\displaystyle s^{\prime}$	$\displaystyle=\frac{\gamma^{2}\epsilon}{256m\sqrt{2t\delta}\log(8tm^{2}/% \epsilon^{2}\gamma^{2}\delta)}\cdot s.$

When $\gamma$ is small enough, $\eta$ will be dominated by ${\binom{\mu}{{\mu/2}}}/{2^{\mu}}=\Theta(1/{\sqrt{\mu}})$ . For large enough $t$ , we can effectively obtain a function with strong average-case hardness to approximate by taking the summation of multiple copies of $f$ .

Lemma 4.2.

For $\delta\in(0,1)$ , $m,\epsilon\in\mathbb{R}$ , $\alpha,s\in\mathbb{N}$ , $\alpha>\log(m/\epsilon)+4$ and a distribution $D$ over $\{0,1\}^{n}$ , consider a real-valued function $f:\{0,1\}^{n}\rightarrow[0,m)$ . For any $l\in\mathbb{N}$ , let $d=\frac{\epsilon}{l}$ , which denotes the radius of the partitioned intervals. For any $a,b\in\{d,3d,\ldots,(2\lceil\frac{m}{2d}\rceil-1)d\},a\neq b$ , define the relation $R_{a,b}\subseteq\{0,1\}^{n}\times\{0,1\}^{\alpha}$ as follows:

$\blacksquare$

If $f(x)\in\left[a\pm d\right)$ or $f(x)\in\left[b\pm d\right)$ , then $(x,y)\in R_{a,b}$ if and only if $y\in(f(x)\pm\epsilon)$ ;
$\blacksquare$

If $f(x)\not\in\left[a\pm d\right)$ and $f(x)\not\in\left[b\pm d\right)$ , then $(x,y)\in R_{a,b}$ for any $y\in\{0,1\}^{\alpha}$ .

For any integer $l>1$ , for large enough $s$ , if $f$ is $(1-\delta)$ -hard to approximate on $D$ with accuracy $\alpha$ and distance $\epsilon$ for circuits of size $s$ , there exist $a,b\in\{d,3d,\ldots,(2\lceil\frac{m}{2d}\rceil-1)d\}$ , $b-a>(\frac{3}{2}l-2)d$ , such that $R_{a,b}$ is $(1-\frac{4d^{2}\delta}{m^{2}})$ -hard on $D$ , for circuits of size $\frac{d^{2}s}{m^{2}}$ .

The proof is deferred to Section 4.1. Following the approach used in the integer case, we proceed with the construction of the hardcore distribution. This hard distribution maintains a good structure, on which $f$ will be balanced and mapped to $[a\pm d)$ or $[b\pm d)$ , for some fixed $a, b$ , which implies the closed approximation of $f$ with distance $d$ is balanced on $H$ around $\left\{a,b\right\}$ .

Lemma 4.3 (Hardcore for Real-Valued Functions).

For $\delta,\gamma\in(0,1)$ , $m,\epsilon\in\mathbb{R}$ , $\alpha,s\in\mathbb{N}$ , $\alpha>\log(m/\epsilon)+4$ and a distribution $D$ over $\{0,1\}^{n}$ , consider a function $f:\{0,1\}^{n}\rightarrow[0,m)$ , which is $(1-\delta)$ -hard to approximate $D$ with accuracy $\alpha$ and distance $\epsilon$ for circuits of size $s$ . For any integer $l\geq 3$ , let $d=\frac{\epsilon}{l}$ , there exist $a,b\in\{d,3d,\ldots,(2\lceil\frac{m}{2d}\rceil-1)d\}$ , $b-a>(\frac{3}{2}l-2)d$ , and a $\frac{4d^{2}\delta}{m^{2}}$ -dense distribution $H$ (with respect to $D$ ), on which the closed approximation of $f$ with distance $d$ is balanced around $\{a,b\}$ and the approximation of $f$ with accuracy $\alpha$ and distance $\epsilon$ is $\frac{1}{2}(1+\gamma)$ -hard for circuits of size $\frac{\gamma^{2}d^{2}s}{256m^{2}\log(2m^{2}/d^{2}\gamma\delta)}$ .

Proof.

Suppose $f:\{0,1\}^{n}\rightarrow[0,m)$ is $(1-\delta)$ -hard on $D$ for circuits of size $s$ , by Lemma 4.2, for integer $l>1$ , $d=\frac{\epsilon}{l}$ , if $s$ is sufficiently large, there exist $a,b\in\{d,3d,\ldots,(2\lceil\frac{m}{2d}\rceil-1)d\}$ , $b-a>(\frac{3}{2}l-2)d$ , such that $R_{a,b}$ (as defined in Lemma 4.2) is $(1-\frac{4d^{2}\delta}{m^{2}})$ -hard on $D$ for circuits of size $\frac{d^{2}s}{m^{2}}$ .

For $R_{a,b}$ , the majority combiner can be constructed by taking the middle point. By Lemma 2.7, when $s$ is large enough, we have a $\frac{4d^{2}\delta}{m^{2}}$ -dense distribution $H^{\prime}$ (with respect to $D$ ) over $\{x:f(x)\in[a\pm d)\cup[b\pm d)\}\subseteq\{0,1\}^{n}$ , on which $R_{a,b}$ is $(\frac{1}{2}+\frac{\gamma}{4})$ -hard for circuits of size $\hat{s}=\frac{\gamma^{2}d^{2}s}{256m^{2}\log(2m^{2}/d^{2}\gamma\delta)}$ , as well as the approximation of $f$ with accuracy $\alpha$ and distance $\epsilon$ is hard on $H^{\prime}$ . If $l\geq 3$ , then $b-a>2d$ , the intervals $[a\pm d]$ and $[b\pm d]$ are disjoint. Then, by Lemma 2.10, we can construct a distribution $H$ with density $\frac{4d^{2}\delta}{m^{2}}$ , on which the closed approximation of $f$ with distance $d$ is balanced around $\{a,b\}$ and the approximation of $f$ with accuracy $\alpha$ and distance $\epsilon$ is $\frac{1}{2}(1+\gamma)$ -hard for circuits of size $\hat{s}$ . $\hfill\blacktriangleleft$

Analogously, we prove that summation suffices to achieve amplification.

Lemma 4.4.

For $\gamma\in(0,1)$ , $m,\epsilon\in\mathbb{R}$ and $\alpha,s,t\in\mathbb{N}$ , $\alpha>\log(m/\epsilon)+4$ , for large enough $l\in\mathbb{N}$ , let $d=\frac{\epsilon}{l}$ , consider a hardcore distribution $H\subseteq\{0,1\}^{n}$ and $a,b\in\{d,3d,\ldots,(2\lceil\frac{m}{2d}\rceil-1)d\}$ , $b-a>(\frac{3}{2}l-2)d$ , on which the closed approximation of function $f:\{0,1\}^{n}\rightarrow[0,m)$ with distance $d$ is balanced around $\{a,b\}$ and $f$ is $\frac{1}{2}(1+\gamma)$ -hard to approximate with accuracy $\alpha$ and distance $\epsilon$ for circuits of size $s$ . For any integer $t$ , define a function $g:(\{0,1\}^{n})^{t}\rightarrow[0,t\cdot m)$ as follows:

g(x_{1},\ldots,x_{t})=\sum_{i=1}^{t}f(x_{i}).

For $k\in\mathbb{N},0<k\leq t$ and any other distribution $G$ over $\left(\{0,1\}^{n}\right)^{t-k}$ , for any large enough $s$ , function $g$ is $\eta$ -hard to approximate with accuracy $\alpha^{\prime}$ and distance $\epsilon$ on $\Pi_{t}(H^{k},G)$ for circuits of size $\frac{s}{2}$ , where $\alpha^{\prime}>\log(t\cdot m/\epsilon)+4$ and

\eta=\frac{\binom{k}{\frac{k}{2}}}{2^{k}}\left(\frac{3\sqrt{k}}{l}+3+\frac{k}{% 2}\gamma\right).

We postpone the proof to Section 4.2 and now present the proof for Theorem 4.1.

Theorem 4.1. [Restated, see original statement.]

For $\delta\in(0,1)$ , $m,\epsilon\in\mathbb{R}$ , $\alpha,s,t\in\mathbb{N}$ , $\alpha>\log(m/\epsilon)+4$ and a distribution $D$ over $\{0,1\}^{n}$ , consider a function $f:\{0,1\}^{n}\rightarrow[0,m)$ that is $(1-\delta)$ -hard to approximate on $D$ with accuracy $\alpha$ and distance $\epsilon$ , for circuits of size $s$ . For any large enough $t$ , define a function $g:\left(\{0,1\}^{n}\right)^{t}\rightarrow[0,t\cdot m)$ as follows:

g(x_{1},\ldots,x_{t})=\sum_{i=1}^{t}f(x_{i}).

Then, for $\gamma\in(0,1)$ , for any large enough $s$ , $g$ is $\eta$ -hard to approximate on $D^{t}$ with accuracy $\alpha^{\prime}$ and distance $\epsilon$ , $\alpha^{\prime}>\log(t\cdot m/\epsilon)+4$ , for circuits of size $s^{\prime}$ , where

	$\displaystyle\eta$	$\displaystyle=e^{-\mu/4}+\frac{\binom{\mu}{\frac{\mu}{2}}}{2^{\mu}}\left(6+% \frac{\mu}{2}\gamma\right),\mu=\frac{\epsilon}{m}\sqrt{2t\delta},$
	$\displaystyle s^{\prime}$	$\displaystyle=\frac{\gamma^{2}\epsilon}{256m\sqrt{2t\delta}\log(8tm^{2}/% \epsilon^{2}\gamma^{2}\delta)}\cdot s.$

Proof.

For $\alpha>\log(m/\epsilon)+4$ and a function $f:\{0,1\}\rightarrow[0,m)$ , which is $(1-\delta)$ -hard for circuits of size $s$ , by Lemma 4.3, for $l\in\mathbb{N}$ , let $d=\frac{\epsilon}{l}$ , there exist $a,b\in\{d,3d,\ldots,(2\lceil\frac{m}{2d}\rceil-1)d\}$ , $b-a>\left(\frac{3}{2}l-2\right)d$ , and a $\frac{4d^{2}\delta}{m^{2}}$ -dense distribution $H$ with respect to $D$ , such that the closed approximation of $f$ with distance $d$ is balanced around $\{a,b\}$ and that $f$ is $\frac{1}{2}(1+\gamma)$ -hard to approximate with accuracy $\alpha$ and distance $\epsilon$ on $H$ for circuits of size $\hat{s}=\frac{\gamma^{2}d^{2}s}{256m^{2}\log(2m^{2}/d^{2}\gamma\delta)}$ .

Since $H$ has relative density $\hat{\delta}=\frac{4d^{2}\delta}{m^{2}}$ , there exists a distribution $G$ over $\{0,1\}^{n}$ , such that $D=\hat{\delta}H+(1-\hat{\delta})G$ . For $t\in\mathbb{N}$ , we have

D^{t}=\sum_{k=0}^{t}\binom{t}{k}\cdot\hat{\delta}^{k}(1-\hat{\delta})^{t-k}% \cdot\Pi_{t}(H^{k},G^{t-k}).

Therefore, for any large enough $s,t\in\mathbb{N}$ , for any circuit of size $s^{\prime}=\frac{\hat{s}}{2}$ , by Lemma 4.4, we have

	$\displaystyle\Pr_{x\leftarrow D^{t}}[C(x)=g(x)]$	$\displaystyle=\sum_{k=0}^{t}\binom{t}{k}\cdot\hat{\delta}^{k}(1-\hat{\delta})^% {t-k}\cdot\Pr_{x\leftarrow\Pi_{t}(H^{k},G^{t-k})}[C(x)=g(x)]$
		$\displaystyle<\sum_{k=0}^{\mu}\binom{t}{k}\cdot\hat{\delta}^{k}(1-\hat{\delta}% )^{t-k}+\frac{\binom{\mu}{\frac{\mu}{2}}}{2^{\mu}}\left(\frac{3\sqrt{\mu}}{l}+% 3+\frac{\mu}{2}\gamma\right)$
		$\displaystyle\leq e^{-\mu/4}+\frac{\binom{\mu}{\frac{\mu}{2}}}{2^{\mu}}\left(% \frac{3\sqrt{\mu}}{l}+3+\frac{\mu}{2}\gamma\right),$

where $\mu=\frac{t\hat{\delta}}{2}=\frac{2td^{2}\delta}{m^{2}}$ . Let $l=\sqrt{\mu}$ , we have

\sqrt{\mu}=\sqrt{\frac{2td^{2}\delta}{m^{2}}}=\sqrt{\frac{2t\epsilon^{2}\delta% }{l^{2}m^{2}}}=\frac{\epsilon}{lm}\sqrt{2t\delta}=l.

Then, $l=\sqrt{\frac{\epsilon}{m}\sqrt{2t\delta}}$ ,

\mu=\frac{\epsilon}{m}\sqrt{2t\delta},s^{\prime}=\frac{\gamma^{2}\epsilon}{256% m\sqrt{2t\delta}\log(8tm^{2}/\epsilon^{2}\gamma^{2}\delta)}\cdot s.\

$\hfill\blacktriangleleft$

4.1 Proof of Lemma 4.2

Lemma 4.2. [Restated, see original statement.]

For $\delta\in(0,1)$ , $m,\epsilon\in\mathbb{R}$ , $\alpha,s\in\mathbb{N}$ , $\alpha>\log(m/\epsilon)+4$ and a distribution $D$ over $\{0,1\}^{n}$ , consider a real-valued function $f:\{0,1\}^{n}\rightarrow[0,m)$ . For any $l\in\mathbb{N}$ , let $d=\frac{\epsilon}{l}$ , which denotes the radius of the partitioned intervals. For any $a,b\in\{d,3d,\ldots,(2\lceil\frac{m}{2d}\rceil-1)d\},a\neq b$ , define the relation $R_{a,b}\subseteq\{0,1\}^{n}\times\{0,1\}^{\alpha}$ as follows:

$\blacksquare$

If $f(x)\in\left[a\pm d\right)$ or $f(x)\in\left[b\pm d\right)$ , then $(x,y)\in R_{a,b}$ if and only if $y\in(f(x)\pm\epsilon)$ ;
$\blacksquare$

If $f(x)\not\in\left[a\pm d\right)$ and $f(x)\not\in\left[b\pm d\right)$ , then $(x,y)\in R_{a,b}$ for any $y\in\{0,1\}^{\alpha}$ .

For any integer $l>1$ , for large enough $s$ , if $f$ is $(1-\delta)$ -hard to approximate on $D$ with accuracy $\alpha$ and distance $\epsilon$ for circuits of size $s$ , there exist $a,b\in\{d,3d,\ldots,(2\lceil\frac{m}{2d}\rceil-1)d\}$ , $b-a>(\frac{3}{2}l-2)d$ , such that $R_{a,b}$ is $(1-\frac{4d^{2}\delta}{m^{2}})$ -hard on $D$ , for circuits of size $\frac{d^{2}s}{m^{2}}$ .

Proof.

Suppose that for any $a,b\in\{d,3d,\ldots,(2\lceil\frac{m}{2d}\rceil-1)d\}$ , $a<b$ , there is a circuit $C_{a,b}:\{0,1\}^{n}\rightarrow\{0,1\}^{\alpha}$ of size $\frac{d^{2}s}{m^{2}}$ , such that

\Pr_{x\leftarrow D}[C_{a,b}(x)\in R_{a,b}(x)]\geq 1-\frac{4d^{2}\delta}{m^{2}}.

For simplicity, let $C_{b,a}=C_{a,b}$ . Taking a combination of circuits $C_{a,b}$ , construct a new circuit $C:\{0,1\}^{n}\rightarrow\{0,1\}^{\alpha}$ as follows:

1.
On input $x$ , for any $i\in\{d,3d,\ldots,(2\lceil\frac{m}{2d}\rceil-1)d\}$ in ascending order:
- $\blacksquare$
  
  Compute $C_{i,j}(x)$ ;
- $\blacksquare$
  
  if $C_{i,j}(x)$ outputs a value in $(i\pm(\epsilon+d))$ for every $j\neq i$ , return $\max_{j\neq i}(C_{i,j}(x))$ , which is the maximum value among all the outputs given by $C_{i,j}(x)$ .
2.

Return $\bot$ if no such $i$ exists.

If $s$ is large enough, specifically $s\gg(\frac{m}{d})^{2}\cdot\alpha$ , the size of $C$ is approximately $\binom{\lceil\frac{m}{2d}\rceil}{2}\cdot\frac{d^{2}s}{m^{2}}\leq s$ . The performance of the circuit $C$ is stated as follows.

Claim 4.5.

For any $x\in\{0,1\}^{n}$ , if $C_{a,b}(x)\in R_{a,b}(x)$ for every distinct $a, b$ , $C(x)\in(f(x)\pm\epsilon)$ .

By Claim 4.5, we have

\Pr_{x\leftarrow D}[C(x)\in(f(x)\pm\epsilon)]\geq\Pr_{x\leftarrow D}\left[% \forall(a,b),a<b:C_{a,b}(x)\in R_{a,b}(x)\right]\geq 1-\binom{\lceil\frac{m}{2% d}\rceil}{2}\cdot\frac{4d^{2}\delta}{m^{2}}\geq 1-\delta.

The second inequality is obtained by taking the union bound. It contradicts the fact that $f$ is $(1-\delta)$ -hard to approximate with accuracy $\alpha$ and distance $\epsilon$ .

In the following, we will prove that the relation $R_{a,b}$ ( $a<b$ ) is potentially hard only if $b-a>(\frac{3}{2}l-2)d$ . Assume the distance of two centers $b-a\leq(\frac{3}{2}l-2)d$ , construct a circuit $C_{a,b}$ which outputs a value in $\left(b-\left(\epsilon-d\right),a+\left(\epsilon-d\right)\right)$ , regardless of inputs. Since the interval length is

a-b+2\left(\epsilon-d\right)\geq-\left(\frac{3}{2}l-2\right)d+2\left(\epsilon-% d\right)\geq\frac{\epsilon}{2},

there exists a value in this interval that can be encoded in $\{0,1\}^{\alpha}$ .

Consider any input $x$ , if $f(x)\in[a\pm d)$ , $f(x)-\epsilon<a+d-\epsilon<b-(\epsilon-d)<a+(\epsilon-d)<f(x)+\epsilon$ ; if $f(x)\in[b\pm d)$ , $f(x)-\epsilon<b-(\epsilon-d)<a+(\epsilon-d)<b-d+\epsilon\leq f(x)+\epsilon$ ; otherwise, any output is in $R_{a,b}(x)$ . Then, the output is guaranteed to have $C_{a,b}(x)\in R_{a,b}(x)$ .

Therefore, there exist $a,b\in\{d,3d,\ldots,(2\lceil\frac{m}{2d}\rceil-1)d\}$ , $b-a>(\frac{3}{2}l-2)d$ , such that $R_{a,b}$ is $(1-\frac{4d^{2}\delta}{m^{2}})$ -hard for circuits of size $\frac{d^{2}s}{m^{2}}$ . $\hfill\blacktriangleleft$

4.1.1 Proof of Claim 4.5

Claim 4.5. [Restated, see original statement.]

For any $x\in\{0,1\}^{n}$ , if $C_{a,b}(x)\in R_{a,b}(x)$ for every distinct $a, b$ , $C(x)\in(f(x)\pm\epsilon)$ .

Proof.

We partition the output space into multiple intervals with length $2d$ and define a set relation $R_{a,b}$ . For each relation, we focus on the inputs whose outputs by $f$ lie in the corresponding intervals $[a\pm d)$ or $[b\pm d)$ . Recall the process of algorithm $C$ : for $i\in\{d,3d,\ldots,(2\lceil\frac{m}{2d}\rceil-1)d\}$ in ascending order, if for every $j\neq i$ , $C_{i,j}(x)\in(i\pm(\epsilon+d))$ holds, then $C$ stops and outputs $\max_{j\neq i}(C_{i,j}(x))$ .

Suppose that the algorithm returns when $i=\hat{i}$ , then $f(x)\geq\hat{i}-d$ . If $f(x)<\hat{i}-d$ , there exists $\tilde{i}<\hat{i}$ , such that $f(x)\in[\tilde{i}\pm d)$ , since we assume the correctness of every $C_{a,b}$ , then $C$ should stop when $i=\tilde{i}$ , which results in a contradiction.

If $f(x)\in[\hat{i}\pm d)$ , $C_{i,j}(x)\in(f(x)\pm\epsilon)$ for every $j\neq i$ , then $C(x)\in(f(x)\pm\epsilon)$ . If $f(x)\geq\hat{i}+d$ , suppose $\tilde{i}>\hat{i}$ and $f(x)\in[\tilde{i}\pm d)$ , then $C_{\hat{i},\tilde{i}}(x)\in(f(x)\pm\epsilon)$ .

f(x)-\epsilon<C_{\hat{i},\tilde{i}}(x)\leq C(x)<\hat{i}+d+\epsilon\leq f(x)+% \epsilon.\

$\hfill\vartriangleleft$

4.2 Proof of Lemma 4.4

Lemma 4.4. [Restated, see original statement.]

For $\gamma\in(0,1)$ , $m,\epsilon\in\mathbb{R}$ and $\alpha,s,t\in\mathbb{N}$ , $\alpha>\log(m/\epsilon)+4$ , for large enough $l\in\mathbb{N}$ , let $d=\frac{\epsilon}{l}$ , consider a hardcore distribution $H\subseteq\{0,1\}^{n}$ and $a,b\in\{d,3d,\ldots,(2\lceil\frac{m}{2d}\rceil-1)d\}$ , $b-a>(\frac{3}{2}l-2)d$ , on which the closed approximation of function $f:\{0,1\}^{n}\rightarrow[0,m)$ with distance $d$ is balanced around $\{a,b\}$ and $f$ is $\frac{1}{2}(1+\gamma)$ -hard to approximate with accuracy $\alpha$ and distance $\epsilon$ for circuits of size $s$ . For any integer $t$ , define a function $g:(\{0,1\}^{n})^{t}\rightarrow[0,t\cdot m)$ as follows:

g(x_{1},\ldots,x_{t})=\sum_{i=1}^{t}f(x_{i}).

For $k\in\mathbb{N},0<k\leq t$ and any other distribution $G$ over $\left(\{0,1\}^{n}\right)^{t-k}$ , for any large enough $s$ , function $g$ is $\eta$ -hard to approximate with accuracy $\alpha^{\prime}$ and distance $\epsilon$ on $\Pi_{t}(H^{k},G)$ for circuits of size $\frac{s}{2}$ , where $\alpha^{\prime}>\log(t\cdot m/\epsilon)+4$ and

\eta=\frac{\binom{k}{\frac{k}{2}}}{2^{k}}\left(\frac{3\sqrt{k}}{l}+3+\frac{k}{% 2}\gamma\right).

Proof.

For an integer $l$ , let $d=\frac{\epsilon}{l}$ , consider a hardcore distribution $H\subseteq\{0,1\}^{n}$ and $a,b\in\left\{d,3d,\ldots,(2\lceil\frac{m}{2d}\rceil-1)d\right\}$ , $b-a>\left(\frac{3}{2}l-2\right)d$ , such that, the closed approximation of function $f:\{0,1\}^{n}\rightarrow[0,m)$ with distance $d$ is balanced around $\{a,b\}$ on $H$ . Denote distribution $x\leftarrow H|_{f(x)\in(a\pm d)}$ by $H_{a}$ and distribution $x\leftarrow H|_{f(x)\in(b\pm d)}$ by $H_{b}$ . Since $f$ is balanced around $\left\{a,b\right\}$ on distribution $H$ , $H=\frac{1}{2}H_{a}+\frac{1}{2}H_{b}$ . The hardness of approximating function $f$ implies the indistinguishability of this two distribution $H_{a}$ and $H_{b}$ .

For $t\in\mathbb{N}$ , let $H_{i}^{t}=\Pi_{t}(H_{a}^{i},H_{b}^{t-i})$ . Then, consider any fixed $\hat{x}=(\hat{x}_{1},\ldots,\hat{x}_{t-k})\in\left(\{0,1\}^{n}\right)^{t-k}$ and any permutation $\pi$ of $t$ coordinates, we have the following fact.

Claim 4.6.

For $s,\alpha^{\prime}\in\mathbb{N}$ , such that $s\gg\alpha^{\prime}$ and $(t\cdot m,\alpha^{\prime},\epsilon)$ is valid, for any circuit $C:(\{0,1\}^{n})^{t}\rightarrow\{0,1\}^{\alpha^{\prime}}$ of size at most $\frac{s}{2}$ , for any $i,j\in\mathbb{N}_{k+1}$ , such that $\left|i-j\right|=1$ and any $v,\epsilon^{\prime}\in[0,t\cdot m),\epsilon^{\prime}\geq\epsilon$ , we have

	$\displaystyle\Pr_{\begin{subarray}{c}\bar{x}\leftarrow H^{k}\\ \bar{x}^{\prime}\leftarrow\pi(\bar{x},\hat{x})\end{subarray}}\left[C(\bar{x}^{% \prime})\in(g_{t}(\bar{x}^{\prime})+v\pm\epsilon^{\prime})\left\|\bar{x}\in H_{% j}^{t}\right.\right]-$
	$\displaystyle\Pr_{\begin{subarray}{c}\bar{x}\leftarrow H^{k}\\ \bar{x}^{\prime}\leftarrow\pi(\bar{x},\hat{x})\end{subarray}}\left[C(\bar{x}^{% \prime})\in(g_{t}(\bar{x}^{\prime})+v+v^{\prime}\pm(\epsilon^{\prime}+2d))% \left\|\bar{x}\in H_{i}^{t}\right.\right]<\gamma$

where $v^{\prime}=(j-i)(a-b)$ .

Let $\Delta=\sum_{i=1}^{t-k}f(\hat{x}_{i})$ . For any large even $t$ , for any circuit $C:(\{0,1\}^{n})^{t}\rightarrow\{0,1\}^{\alpha^{\prime}}$ of size at most $\frac{s}{2}$ , the following holds,

		$\displaystyle\Pr_{\begin{subarray}{c}\bar{x}\leftarrow H^{k}\\ \bar{x}^{\prime}\leftarrow\pi(\bar{x},\hat{x})\end{subarray}}\left[C(\bar{x}^{% \prime})\in(g_{t}(\bar{x}^{\prime})\pm\epsilon)\right]$
		$\displaystyle=\sum_{i=0}^{k}\Pr_{\begin{subarray}{c}\bar{x}\leftarrow H^{k}\\ \bar{x}^{\prime}\leftarrow\pi(\bar{x},\hat{x})\end{subarray}}\left[\bar{x}\in H% _{i}^{k}\right]\cdot\Pr_{\begin{subarray}{c}\bar{x}\leftarrow H^{k}\\ \bar{x}^{\prime}\leftarrow\pi(\bar{x},\hat{x})\end{subarray}}\left[C(\bar{x}^{% \prime})\in(g_{t}(\bar{x}^{\prime})\pm\epsilon)\left\|\bar{x}\in H_{i}^{k}% \right.\right]$
		$\displaystyle=\frac{1}{2^{k}}\sum_{i=0}^{k}\binom{k}{i}\Pr_{\begin{subarray}{c% }\bar{x}\leftarrow H^{k}\\ \bar{x}^{\prime}\leftarrow\pi(\bar{x},\hat{x})\end{subarray}}\left[C(\bar{x}^{% \prime})\in(g_{k}(\bar{x})+\Delta\pm\epsilon)\left\|\bar{x}\in H_{i}^{k}\right.\right]$
		$\displaystyle=\frac{1}{2^{k}}\sum_{i=-\frac{k}{2}}^{\frac{k}{2}}\binom{k}{% \frac{k}{2}+i}\Pr_{\begin{subarray}{c}\bar{x}\leftarrow H^{k}\\ \bar{x}^{\prime}\leftarrow\pi(\bar{x},\hat{x})\end{subarray}}\left[C(\bar{x}^{% \prime})\in(g_{k}(\bar{x})+\Delta\pm\epsilon)\left\|\bar{x}\in H_{\frac{k}{2}+i% }^{k}\right.\right]$
		$\displaystyle<\frac{1}{2^{k}}\sum_{i=-\frac{k}{2}}^{\frac{k}{2}}\binom{k}{% \frac{k}{2}+i}\Pr_{\begin{subarray}{c}\bar{x}\leftarrow H^{k}\\ \bar{x}^{\prime}\leftarrow\pi(\bar{x},\hat{x})\end{subarray}}\left[C(\bar{x}^{% \prime})\in(g_{k}(\bar{x})+i(a-b)+\Delta\pm(\epsilon+2d\left\|i\right\|))\left\|% \bar{x}\in H_{\frac{k}{2}}^{k}\right.\right]$		(6)
		$\displaystyle+\frac{1}{2^{k}}\sum_{i=-\frac{k}{2}}^{\frac{k}{2}}\binom{k}{% \frac{k}{2}+i}\cdot\left\|i\right\|\gamma$
		$\displaystyle\leq\frac{\binom{k}{\frac{k}{2}}}{2^{k}}\left(\frac{3\sqrt{k}}{l}% +3+\frac{k}{2}\gamma\right).$

The inequality (4.2) is obtained by using Claim 4.6, we use the probability with a same condition $\bar{x}\in H_{\frac{k}{2}}^{k}$ to give an upper bound for the original term. The last inequality follows Claim 4.7. Therefore, for any distribution $G$ over $\left(\{0,1\}^{n}\right)^{t-k}$ , we have

\displaystyle\Pr_{\bar{x}\leftarrow\Pi_{t}(H^{k},G)}[C(\bar{x})\in(g_{t}(\bar{% x})\pm\epsilon)]\leq\frac{\binom{k}{\frac{k}{2}}}{2^{k}}\left(\frac{3\sqrt{k}}% {l}+3+\frac{k}{2}\gamma\right).

$\hfill\blacktriangleleft$

Claim 4.7.

For large enough $l\in\mathbb{N}$ , for any circuit $C$ , the following value is upper-bounded by $\binom{k}{\frac{k}{2}}(\frac{3\sqrt{k}}{l}+3)$ :

\sum_{i=-\frac{k}{2}}^{\frac{k}{2}}\binom{k}{\frac{k}{2}+i}\Pr_{\begin{% subarray}{c}\bar{x}\leftarrow H^{k}\\ \bar{x}^{\prime}\leftarrow\pi(\bar{x},\hat{x})\end{subarray}}\left[C(\bar{x}^{% \prime})\in(g_{k}(\bar{x})+i(a-b)+\Delta\pm(\epsilon+2d\left|i\right|))\left|% \bar{x}\in H^{k}_{\frac{k}{2}}\right.\right],

where $b-a>\left(\frac{3}{2}l-2\right)d$ and $\epsilon=l\cdot d$ .

Proof.

Recall that $\epsilon$ denotes the tolerance of the approximation error, and for some integer $l\in\mathbb{N}$ , we let $d=\frac{\epsilon}{l}$ . Since $a, b$ are the multiples of $d$ , let $b-a=l_{1}\cdot d$ , for some positive integer $l_{1}$ . By our assumption, $b-a>\left(\frac{3}{2}l-2\right)d$ , thus $l_{1}>\frac{3}{2}l-2$ .

For simplicity, for any integer $i_{1},i_{2}$ , let

P(i_{1},i_{2})=\Pr_{\begin{subarray}{c}\bar{x}\leftarrow H^{k}\\ \bar{x}^{\prime}\leftarrow\pi(\bar{x},\hat{x})\end{subarray}}\left[C(\bar{x}^{% \prime})\in[g_{k}(\bar{x})+\Delta+i_{1}d,g_{k}(\bar{x})+\Delta+i_{2}d)\left|% \bar{x}\in H^{k}_{\frac{k}{2}}\right.\right].

It is clear that $P(i_{1},i_{2})+P(i_{2},i_{3})=P(i_{1},i_{3})$ for $i_{1}<i_{2}<i_{3}$ . Note that $\binom{k}{\frac{k}{2}+i}=\binom{k}{\frac{k}{2}-i}$ , the value can be upper bounded by

		$\displaystyle\sum_{i=-\frac{k}{2}}^{\frac{k}{2}}\binom{k}{\frac{k}{2}+i}\cdot P% (i\cdot l_{1}-l-2\left\|i\right\|,i\cdot l_{1}+l+2\left\|i\right\|)$
	$\displaystyle=$	$\displaystyle\sum_{i=-\frac{k}{2}}^{\frac{k}{2}}\binom{k}{\frac{k}{2}+i}\sum_{% j=i\cdot l_{1}-l-2\left\|i\right\|}^{i\cdot l_{1}+l+2\left\|i\right\|-1}P(j,j+1)$

where summation is justified by the basic property of probability. To calculate the above, we collect the sum of coefficients corresponding to each $P(j,j+1)$ . For each $j$ , the term should be

\displaystyle\sum_{i=i_{f}(j)}^{i_{c}(j)}\binom{k}{\frac{k}{2}+i}P(j,j+1),

(7)

for some functions $i_{f},i_{c}$ . Let $S(j)=\sum_{i=i_{f}(j)}^{i_{c}(j)}\binom{k}{\frac{k}{2}+i}$ denote the coefficient of $P(j,j+1)$ . Since the summation of all possible $P(j,j+1)$ is at most $1$ , by the definition of probability, it is feasible to give an upper bound for the entire summation by computing the upper bound for $S(j)$ . For any $i\in[i_{f}(j),i_{c}(j)]$ , $i$ should satisfy:

\displaystyle i\cdot l_{1}-l-2\left|i\right|\leq j\leq i\cdot l_{1}+l+2\left|i% \right|-1\text{ and }-\frac{k}{2}\leq i\leq\frac{k}{2}.

It is clear that $S(j)=S(-j-1)$ , since for any $i\in[i_{f}(j),i_{c}(j)]$ ,

		$\displaystyle i\cdot l_{1}-l-2\left\|i\right\|\leq j\leq i\cdot l_{1}+l+2\left\|i% \right\|-1$
	$\displaystyle\Leftrightarrow$	$\displaystyle-i\cdot l_{1}-l-2\left\|i\right\|\leq-j-1\leq-i\cdot l_{1}+l+2\left% \|i\right\|-1.$

Then, $-i\in[i_{f}(-j-1),i_{c}(-j-1)]$ , we derive $S(j)=S(-j-1)$ .

Recall that $l_{1}>\frac{3}{2}l-2$ , assume $l>6$ , $l_{1}-l>1$ . When $j\geq 0$ , we necessarily have $i\cdot l_{1}+l+2\left|i\right|\geq 1$ . If there exists a negative $i$ satisfies the inequality, then $i(l_{1}-2)+l\leq-(l_{1}-2)+l<1$ , which leads to a contradiction. Therefore,

i\cdot l_{1}-l-2i\leq j\leq i\cdot l_{1}+l+2i-1,

which is equivalent to

i_{f}(j)=\lceil\frac{j-l+1}{l_{1}+2}\rceil\leq i\leq\lfloor\frac{j+l}{l_{1}-2}% \rfloor=i_{c}(j).

Therefore, we can give an upper bound for $S(j)$ ,

	$\displaystyle S(j)$	$\displaystyle=\sum_{i=i_{f}(j)}^{i_{c}(j)}\binom{k}{\frac{k}{2}+i}\leq\left(% \frac{j+l}{l_{1}-2}-\frac{j-l+1}{l_{1}+2}+1\right)\binom{k}{\frac{k}{2}+i_{f}(% j)}$
		$\displaystyle\leq\left(\frac{4j}{(l_{1}-2)(l_{1}+2)}+3\right)\binom{k}{\frac{k% }{2}+i_{f}(j)}.$

On the other hand, $j$ can be upper bounded in terms of $i_{f}(j)$ , that is

\frac{j-l+1}{l_{1}+2}<i_{f}(j)+1\Rightarrow j<(i_{f}(j)+1)(l_{1}+2)+l-1<(i_{f}% (j)+2)(l_{1}+2).

Then, plug in $i_{f}(j)$ ,

S(j)\leq\left(\frac{4j}{(l_{1}-2)(l_{1}+2)}+3\right)\binom{k}{\frac{k}{2}+i_{f% }(j)}<\left(\frac{4(i_{f}(j)+2)}{l_{1}-2}+3\right)\binom{k}{\frac{k}{2}+i_{f}(% j)}.

In the following, for $0\leq i\leq\frac{k}{2}$ , we denote

T(i)=\frac{i+2}{l_{1}-2}\binom{k}{\frac{k}{2}+i}.

(8)

Since the maximum value of $S(j)$ is at most the maximum value of $4T(i)+3\binom{k}{\frac{k}{2}}$ , then

\max_{j}S(j)=\max_{j\geq 0}S(j)\leq 4\cdot\max_{i}T(i)+3\binom{k}{\frac{k}{2}}.

The first equality holds because $S(j)=S(-j-1)$ . To find the maximum value of $T(i)$ , we compare each pairs of adjacent terms in the sequence: $T(i+1)>T(i)$ if and only if $i<\frac{\sqrt{k+5}-3}{2}$ . We have

\max_{i}T(i)<\frac{\lfloor\frac{\sqrt{k+5}-3}{2}\rfloor+2}{l_{1}-2}\binom{k}{% \frac{k}{2}}.

Therefore, for $k\geq 12$ ,

\max_{j}S(j)<4\cdot\frac{\lfloor\frac{\sqrt{k+5}-3}{2}\rfloor+2}{l_{1}-2}% \binom{k}{\frac{k}{2}}+3\binom{k}{\frac{k}{2}}<3\left(\frac{\sqrt{k}}{l}+1% \right)\binom{k}{\frac{k}{2}}.\

$\hfill\vartriangleleft$

4.2.1 Proof of Claim 4.6

Claim 4.6. [Restated, see original statement.]

For $s,\alpha^{\prime}\in\mathbb{N}$ , such that $s\gg\alpha^{\prime}$ and $(t\cdot m,\alpha^{\prime},\epsilon)$ is valid, for any circuit $C:(\{0,1\}^{n})^{t}\rightarrow\{0,1\}^{\alpha^{\prime}}$ of size at most $\frac{s}{2}$ , for any $i,j\in\mathbb{N}_{k+1}$ , such that $\left|i-j\right|=1$ and any $v,\epsilon^{\prime}\in[0,t\cdot m),\epsilon^{\prime}\geq\epsilon$ , we have

	$\displaystyle\Pr_{\begin{subarray}{c}\bar{x}\leftarrow H^{k}\\ \bar{x}^{\prime}\leftarrow\pi(\bar{x},\hat{x})\end{subarray}}\left[C(\bar{x}^{% \prime})\in(g_{t}(\bar{x}^{\prime})+v\pm\epsilon^{\prime})\left\|\bar{x}\in H_{% j}^{t}\right.\right]-$
	$\displaystyle\Pr_{\begin{subarray}{c}\bar{x}\leftarrow H^{k}\\ \bar{x}^{\prime}\leftarrow\pi(\bar{x},\hat{x})\end{subarray}}\left[C(\bar{x}^{% \prime})\in(g_{t}(\bar{x}^{\prime})+v+v^{\prime}\pm(\epsilon^{\prime}+2d))% \left\|\bar{x}\in H_{i}^{t}\right.\right]<\gamma$

where $v^{\prime}=(j-i)(a-b)$ .

Proof.

Without loss of generality, suppose $i\in\mathbb{N}_{t}$ and $j=i+1$ . Suppose that there is a circuit $C$ of size at most $\frac{s}{2}$ and $v,\epsilon^{\prime}\in[0,t\cdot m)$ , $\epsilon^{\prime}\geq\epsilon$ , the inequality above does not hold. Then, there must exist a tuple $(x_{1},\ldots,x_{k-1})$ and a permutation $\pi_{k}$ of $k$ entries, such that,

		$\displaystyle\Pr_{\begin{subarray}{c}x\leftarrow H\\ \bar{x}\leftarrow\pi_{k}(x_{1},\ldots,x_{k-1},x)\\ \bar{x}^{\prime}\leftarrow\pi(\bar{x},\hat{x})\end{subarray}}\left[C(\bar{x}^{% \prime})\in(g_{t}(\bar{x}^{\prime})+v\pm\epsilon^{\prime})\left\|x\in H_{a}% \right.\right]$
	$\displaystyle-$	$\displaystyle\Pr_{\begin{subarray}{c}x\leftarrow H\\ \bar{x}\leftarrow\pi_{k}(x_{1},\ldots,x_{k-1},x)\\ \bar{x}^{\prime}\leftarrow\pi(\bar{x},\hat{x})\end{subarray}}\left[C(\bar{x}^{% \prime})\in(g_{t}(\bar{x}^{\prime})+v+v^{\prime}\pm(\epsilon^{\prime}+2d))% \left\|x\in H_{b}\right.\right]\geq\gamma.$

In fact, $g_{t}(\bar{x}^{\prime})=f(x)+g_{k-1}(x_{1},\ldots,x_{t-1})+g_{t-k}(\hat{x})$ , let $\Delta=g(\bar{x}^{\prime})-f(x)$ , which is a fixed value independent of $x$ . Recall that $\epsilon$ is the tolerance of approximation error and $d$ is the radius of the intervals around $a$ and $b$ , while letting $d=\frac{\epsilon}{l}$ for some large enough integer $l$ . Define a circuit $C^{\prime}:\{0,1\}^{n}\rightarrow\{0,1\}^{\alpha}$ as follows:

1.

Input: $x\in\{0,1\}^{n}$ .
2.

Compute $y\leftarrow C(\pi(x,\hat{x}))$ .
3.

If $y\in[a+\Delta+v\pm(\epsilon^{\prime}+d))$ , output a value in $(a\pm\frac{\epsilon}{4})$ .
4.

Otherwise, output a value in $(b\pm\frac{\epsilon}{4})$ .

If $s$ is large enough, the size of $C^{\prime}$ is less than $s$ . In the following, we will show that the circuit $C^{\prime}$ can approximate function $f$ with a good probability, then result in a contradiction.

For any $x\in H_{a}$ , which means $f(x)\in[a\pm d)$ , if $C(\bar{x}^{\prime})$ output a value $y$ in $(g_{t}(\bar{x}^{\prime})+v\pm\epsilon^{\prime})$ which is equivalent to $(f(x)+\Delta+v\pm\epsilon^{\prime})$ , we necessarily have $y\in[a+\Delta+v\pm(\epsilon^{\prime}+d))$ . For any value $z\in\left(a\pm\frac{\epsilon}{4}\right)$ , $\left|f(x)-z\right|\leq\frac{\epsilon}{4}+d\leq\epsilon$ , then

\Pr_{x\leftarrow H}[C^{\prime}(x)\in(f(x)\pm\epsilon)\left|x\in H_{a}\right.]% \geq\Pr_{\begin{subarray}{c}x\leftarrow H\\ \bar{x}\leftarrow\pi_{k}(x_{1},\ldots,x_{k-1},x)\\ \bar{x}^{\prime}\leftarrow\pi(\bar{x},\hat{x})\end{subarray}}\left[C(\bar{x}^{% \prime})\in(g_{t}(\bar{x}^{\prime})+v\pm\epsilon^{\prime})\left|x\in H_{a}% \right.\right].

On the other hand, for any $x\in H_{b}$ , $f(x)\in[b\pm d)$ , if $C(\bar{x}^{\prime})$ output a value $y$ , such that $y\not\in(g_{t}(\bar{x}^{\prime})+v+v^{\prime}\pm(\epsilon^{\prime}+2d))$ , which is equivalent to $(f(x)+\Delta+v+(a-b)\pm(\epsilon^{\prime}+2d))$ . The interval above covers the interval $[a+\Delta+v\pm(\epsilon^{\prime}+d))$ , since

	$\displaystyle a+\Delta+v+\epsilon^{\prime}+d\leq f(x)+\Delta+v+(a-b)+\epsilon^% {\prime}+2d$
	$\displaystyle a+\Delta+v-\epsilon^{\prime}-d>f(x)+\Delta+v+(a-b)-\epsilon^{% \prime}-2d.$

The circuit $C^{\prime}$ will output a value in $(b\pm\frac{\epsilon}{4})$ . Therefore, the probability that $C^{\prime}$ can successfully approximate function $f$ on $H$ is

	$\displaystyle\Pr_{x\leftarrow H}[C^{\prime}(x)\in(f(x)\pm\epsilon)]$
	$\displaystyle=\frac{1}{2}\Pr_{x\leftarrow H}[C^{\prime}(x)\in(f(x)\pm\epsilon)% \|x\in H_{a}]+\frac{1}{2}\Pr_{x\leftarrow H}[C^{\prime}(x)\in(f(x)\pm\epsilon)\|% x\in H_{b}]$
	$\displaystyle\geq\frac{1}{2}\Pr_{\begin{subarray}{c}x\leftarrow H\\ \bar{x}\leftarrow\pi_{k}(x_{1},\ldots,x_{k-1},x)\\ \bar{x}^{\prime}\leftarrow\pi(\bar{x},\hat{x})\end{subarray}}\left[C(\bar{x}^{% \prime})\in(g_{t}(\bar{x}^{\prime})+v\pm\epsilon^{\prime})\left\|x\in H_{a}% \right.\right]$
	$\displaystyle+\frac{1}{2}\Pr_{\begin{subarray}{c}x\leftarrow H\\ \bar{x}\leftarrow\pi_{k}(x_{1},\ldots,x_{k-1},x)\\ \bar{x}^{\prime}\leftarrow\pi(\bar{x},\hat{x})\end{subarray}}\left[C(\bar{x}^{% \prime})\not\in(g_{t}(\bar{x}^{\prime})+v+v^{\prime}\pm(\epsilon^{\prime}+2d))% \left\|x\in H_{b}\right.\right].$
	$\displaystyle\geq\frac{1}{2}(1+\gamma),$

which contradict to $f$ is $\frac{1}{2}(1+\gamma)$ -hard on $H$ . $\hfill\vartriangleleft$

References

[1] Shweta Agrawal, Sagnik Saha, Nikolaj I. Schwartzbach, Akhil Vanukuri, and Prashant Nalini Vasudevan. k-sum in the sparse regime: Complexity and applications. In Leonid Reyzin and Douglas Stebila, editors, Advances in Cryptology - CRYPTO 2024 - 44th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2024, Proceedings, Part II, volume 14921 of Lecture Notes in Computer Science, pages 315–351. Springer, 2024. doi:10.1007/978-3-031-68379-4_10.
[2] Sanjeev Arora and Boaz Barak. Computational Complexity - A Modern Approach. Cambridge University Press, 2009. URL: http://www.cambridge.org/catalogue/catalogue.asp?isbn=9780521424264.
[3] Vahid R. Asadi, Alexander Golovnev, Tom Gur, and Igor Shinkar. Worst-case to average-case reductions via additive combinatorics. In Stefano Leonardi and Anupam Gupta, editors, STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022, pages 1566–1574. ACM, 2022. doi:10.1145/3519935.3520041.
[4] Marshall Ball, Alon Rosen, Manuel Sabin, and Prashant Nalini Vasudevan. Average-case fine-grained hardness. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 483–496. ACM, 2017. doi:10.1145/3055399.3055466.
[5] Boaz Barak, Moritz Hardt, and Satyen Kale. The uniform hardcore lemma via approximate bregman projections. In Claire Mathieu, editor, Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, New York, NY, USA, January 4-6, 2009, pages 1193–1200. SIAM, 2009. doi:10.1137/1.9781611973068.129.
[6] Andrej Bogdanov and Luca Trevisan. On worst-case to average-case reductions for NP problems. SIAM J. Comput., 36(4):1119–1159, 2006. doi:10.1137/S0097539705446974.
[7] Enric Boix-Adserà, Matthew S. Brennan, and Guy Bresler. The average-case complexity of counting cliques in erdős-rényi hypergraphs. In David Zuckerman, editor, 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 1256–1280. IEEE Computer Society, 2019. doi:10.1109/FOCS.2019.00078.
[8] Jin-yi Cai, Aduri Pavan, and D. Sivakumar. On the hardness of permanent. In Christoph Meinel and Sophie Tison, editors, STACS 99, 16th Annual Symposium on Theoretical Aspects of Computer Science, Trier, Germany, March 4-6, 1999, Proceedings, volume 1563 of Lecture Notes in Computer Science, pages 90–99. Springer, 1999. doi:10.1007/3-540-49116-3_8.
[9] Nathan Geier. A tight computational indistinguishability bound for product distributions. In Eike Kiltz and Vinod Vaikuntanathan, editors, Theory of Cryptography - 20th International Conference, TCC 2022, Chicago, IL, USA, November 7-10, 2022, Proceedings, Part II, volume 13748 of Lecture Notes in Computer Science, pages 333–347. Springer, 2022. doi:10.1007/978-3-031-22365-5_12.
[10] Elazar Goldenberg and Karthik C. S. Hardness amplification of optimization problems. In Thomas Vidick, editor, 11th Innovations in Theoretical Computer Science Conference, ITCS 2020, January 12-14, 2020, Seattle, Washington, USA, volume 151 of LIPIcs, pages 1:1–1:13. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020. doi:10.4230/LIPICS.ITCS.2020.1.
[11] Oded Goldreich, Russell Impagliazzo, Leonid A. Levin, Ramarathnam Venkatesan, and David Zuckerman. Security preserving amplification of hardness. In 31st Annual Symposium on Foundations of Computer Science, St. Louis, Missouri, USA, October 22-24, 1990, Volume I, pages 318–326. IEEE Computer Society, 1990. doi:10.1109/FSCS.1990.89550.
[12] Oded Goldreich, Noam Nisan, and Avi Wigderson. On yao’s xor-lemma. In Oded Goldreich, editor, Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation - In Collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, Tali Kaufman, Leonid Levin, Noam Nisan, Dana Ron, Madhu Sudan, Luca Trevisan, Salil Vadhan, Avi Wigderson, David Zuckerman, volume 6650 of Lecture Notes in Computer Science, pages 273–301. Springer, 2011. doi:10.1007/978-3-642-22670-0_23.
[13] Oded Goldreich and Guy N. Rothblum. Counting t-cliques: Worst-case to average-case reductions and direct interactive proof systems. In Mikkel Thorup, editor, 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 77–88. IEEE Computer Society, 2018. doi:10.1109/FOCS.2018.00017.
[14] Parikshit Gopalan and Venkatesan Guruswami. Hardness amplification within NP against deterministic algorithms. J. Comput. Syst. Sci., 77(1):107–121, 2011. doi:10.1016/J.JCSS.2010.06.008.
[15] Alexander Healy, Salil P. Vadhan, and Emanuele Viola. Using nondeterminism to amplify hardness. SIAM J. Comput., 35(4):903–931, 2006. doi:10.1137/S0097539705447281.
[16] Shuichi Hirahara and Nobutaka Shimizu. Hardness self-amplification: Simplified, optimized, and unified. In Barna Saha and Rocco A. Servedio, editors, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023, pages 70–83. ACM, 2023. doi:10.1145/3564246.3585189.
[17] Russell Impagliazzo. Hard-core distributions for somewhat hard problems. In 36th Annual Symposium on Foundations of Computer Science, Milwaukee, Wisconsin, USA, 23-25 October 1995, pages 538–545. IEEE Computer Society, 1995. doi:10.1109/SFCS.1995.492584.
[18] Satyen Kale. Boosting and hard-core set constructions: a simplified approach. Electron. Colloquium Comput. Complex., TR07-131, 2007. URL: https://eccc.weizmann.ac.il/eccc-reports/2007/TR07-131/index.html.
[19] Adam R. Klivans and Rocco A. Servedio. Boosting and hard-core set construction. Mach. Learn., 51(3):217–238, 2003. doi:10.1023/A:1022949332276.
[20] Richard J. Lipton. New directions in testing. In Joan Feigenbaum and Michael Merritt, editors, Distributed Computing And Cryptography, Proceedings of a DIMACS Workshop, Princeton, New Jersey, USA, October 4-6, 1989, volume 2 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 191–202. DIMACS/AMS, 1989. doi:10.1090/DIMACS/002/13.
[21] Ryan O’Donnell. Hardness amplification within ${}_{\mbox{np}}$ . J. Comput. Syst. Sci., 69(1):68–94, 2004. doi:10.1016/J.JCSS.2004.01.001.
[22] Amit Sahai and Salil P. Vadhan. A complete problem for statistical zero knowledge. J. ACM, 50(2):196–249, 2003. doi:10.1145/636865.636868.
[23] Luca Trevisan. On uniform amplification of hardness in NP. In Harold N. Gabow and Ronald Fagin, editors, Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22-24, 2005, pages 31–38. ACM, 2005. doi:10.1145/1060590.1060595.
[24] Luca Trevisan and Salil P. Vadhan. Pseudorandomness and average-case complexity via uniform reductions. Comput. Complex., 16(4):331–364, 2007. doi:10.1007/S00037-007-0233-X.
[25] Salil Pravin Vadhan. A Study of Statistical Zero-Knowledge Proofs. PhD thesis, Harvard University, USA, 1999. AAI0801528.
[26] Andrew Chi-Chih Yao. Theory and applications of trapdoor functions (extended abstract). In 23rd Annual Symposium on Foundations of Computer Science, Chicago, Illinois, USA, 3-5 November 1982, pages 80–91. IEEE Computer Society, 1982. doi:10.1109/SFCS.1982.45.

[bib.bib1] [1] Shweta Agrawal, Sagnik Saha, Nikolaj I. Schwartzbach, Akhil Vanukuri, and Prashant Nalini Vasudevan. k-sum in the sparse regime: Complexity and applications. In Leonid Reyzin and Douglas Stebila, editors, Advances in Cryptology - CRYPTO 2024 - 44th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2024, Proceedings, Part II, volume 14921 of Lecture Notes in Computer Science, pages 315–351. Springer, 2024. doi:10.1007/978-3-031-68379-4_10.

[bib.bib2] [2] Sanjeev Arora and Boaz Barak. Computational Complexity - A Modern Approach. Cambridge University Press, 2009. URL: http://www.cambridge.org/catalogue/catalogue.asp?isbn=9780521424264.

[bib.bib3] [3] Vahid R. Asadi, Alexander Golovnev, Tom Gur, and Igor Shinkar. Worst-case to average-case reductions via additive combinatorics. In Stefano Leonardi and Anupam Gupta, editors, STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022, pages 1566–1574. ACM, 2022. doi:10.1145/3519935.3520041.

[bib.bib4] [4] Marshall Ball, Alon Rosen, Manuel Sabin, and Prashant Nalini Vasudevan. Average-case fine-grained hardness. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 483–496. ACM, 2017. doi:10.1145/3055399.3055466.

[bib.bib5] [5] Boaz Barak, Moritz Hardt, and Satyen Kale. The uniform hardcore lemma via approximate bregman projections. In Claire Mathieu, editor, Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, New York, NY, USA, January 4-6, 2009, pages 1193–1200. SIAM, 2009. doi:10.1137/1.9781611973068.129.

[bib.bib6] [6] Andrej Bogdanov and Luca Trevisan. On worst-case to average-case reductions for NP problems. SIAM J. Comput., 36(4):1119–1159, 2006. doi:10.1137/S0097539705446974.

[bib.bib7] [7] Enric Boix-Adserà, Matthew S. Brennan, and Guy Bresler. The average-case complexity of counting cliques in erdős-rényi hypergraphs. In David Zuckerman, editor, 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 1256–1280. IEEE Computer Society, 2019. doi:10.1109/FOCS.2019.00078.

[bib.bib8] [8] Jin-yi Cai, Aduri Pavan, and D. Sivakumar. On the hardness of permanent. In Christoph Meinel and Sophie Tison, editors, STACS 99, 16th Annual Symposium on Theoretical Aspects of Computer Science, Trier, Germany, March 4-6, 1999, Proceedings, volume 1563 of Lecture Notes in Computer Science, pages 90–99. Springer, 1999. doi:10.1007/3-540-49116-3_8.

[bib.bib9] [9] Nathan Geier. A tight computational indistinguishability bound for product distributions. In Eike Kiltz and Vinod Vaikuntanathan, editors, Theory of Cryptography - 20th International Conference, TCC 2022, Chicago, IL, USA, November 7-10, 2022, Proceedings, Part II, volume 13748 of Lecture Notes in Computer Science, pages 333–347. Springer, 2022. doi:10.1007/978-3-031-22365-5_12.

[bib.bib10] [10] Elazar Goldenberg and Karthik C. S. Hardness amplification of optimization problems. In Thomas Vidick, editor, 11th Innovations in Theoretical Computer Science Conference, ITCS 2020, January 12-14, 2020, Seattle, Washington, USA, volume 151 of LIPIcs, pages 1:1–1:13. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020. doi:10.4230/LIPICS.ITCS.2020.1.

[bib.bib11] [11] Oded Goldreich, Russell Impagliazzo, Leonid A. Levin, Ramarathnam Venkatesan, and David Zuckerman. Security preserving amplification of hardness. In 31st Annual Symposium on Foundations of Computer Science, St. Louis, Missouri, USA, October 22-24, 1990, Volume I, pages 318–326. IEEE Computer Society, 1990. doi:10.1109/FSCS.1990.89550.

[bib.bib12] [12] Oded Goldreich, Noam Nisan, and Avi Wigderson. On yao’s xor-lemma. In Oded Goldreich, editor, Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation - In Collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, Tali Kaufman, Leonid Levin, Noam Nisan, Dana Ron, Madhu Sudan, Luca Trevisan, Salil Vadhan, Avi Wigderson, David Zuckerman, volume 6650 of Lecture Notes in Computer Science, pages 273–301. Springer, 2011. doi:10.1007/978-3-642-22670-0_23.

[bib.bib13] [13] Oded Goldreich and Guy N. Rothblum. Counting t-cliques: Worst-case to average-case reductions and direct interactive proof systems. In Mikkel Thorup, editor, 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 77–88. IEEE Computer Society, 2018. doi:10.1109/FOCS.2018.00017.

[bib.bib14] [14] Parikshit Gopalan and Venkatesan Guruswami. Hardness amplification within NP against deterministic algorithms. J. Comput. Syst. Sci., 77(1):107–121, 2011. doi:10.1016/J.JCSS.2010.06.008.

[bib.bib15] [15] Alexander Healy, Salil P. Vadhan, and Emanuele Viola. Using nondeterminism to amplify hardness. SIAM J. Comput., 35(4):903–931, 2006. doi:10.1137/S0097539705447281.

[bib.bib16] [16] Shuichi Hirahara and Nobutaka Shimizu. Hardness self-amplification: Simplified, optimized, and unified. In Barna Saha and Rocco A. Servedio, editors, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023, pages 70–83. ACM, 2023. doi:10.1145/3564246.3585189.

[bib.bib17] [17] Russell Impagliazzo. Hard-core distributions for somewhat hard problems. In 36th Annual Symposium on Foundations of Computer Science, Milwaukee, Wisconsin, USA, 23-25 October 1995, pages 538–545. IEEE Computer Society, 1995. doi:10.1109/SFCS.1995.492584.

[bib.bib18] [18] Satyen Kale. Boosting and hard-core set constructions: a simplified approach. Electron. Colloquium Comput. Complex., TR07-131, 2007. URL: https://eccc.weizmann.ac.il/eccc-reports/2007/TR07-131/index.html.

[bib.bib19] [19] Adam R. Klivans and Rocco A. Servedio. Boosting and hard-core set construction. Mach. Learn., 51(3):217–238, 2003. doi:10.1023/A:1022949332276.

[bib.bib20] [20] Richard J. Lipton. New directions in testing. In Joan Feigenbaum and Michael Merritt, editors, Distributed Computing And Cryptography, Proceedings of a DIMACS Workshop, Princeton, New Jersey, USA, October 4-6, 1989, volume 2 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 191–202. DIMACS/AMS, 1989. doi:10.1090/DIMACS/002/13.

[bib.bib21] [21] Ryan O’Donnell. Hardness amplification within ${}_{\mbox{np}}$ . J. Comput. Syst. Sci., 69(1):68–94, 2004. doi:10.1016/J.JCSS.2004.01.001.

[bib.bib22] [22] Amit Sahai and Salil P. Vadhan. A complete problem for statistical zero knowledge. J. ACM, 50(2):196–249, 2003. doi:10.1145/636865.636868.

[bib.bib23] [23] Luca Trevisan. On uniform amplification of hardness in NP. In Harold N. Gabow and Ronald Fagin, editors, Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22-24, 2005, pages 31–38. ACM, 2005. doi:10.1145/1060590.1060595.

[bib.bib24] [24] Luca Trevisan and Salil P. Vadhan. Pseudorandomness and average-case complexity via uniform reductions. Comput. Complex., 16(4):331–364, 2007. doi:10.1007/S00037-007-0233-X.

[bib.bib25] [25] Salil Pravin Vadhan. A Study of Statistical Zero-Knowledge Proofs. PhD thesis, Harvard University, USA, 1999. AAI0801528.

[bib.bib26] [26] Andrew Chi-Chih Yao. Theory and applications of trapdoor functions (extended abstract). In 23rd Annual Symposium on Foundations of Computer Science, Chicago, Illinois, USA, 3-5 November 1982, pages 80–91. IEEE Computer Society, 1982. doi:10.1109/SFCS.1982.45.

	$\displaystyle\Pr_{x\leftarrow H^{t}}[\hat{C}(x)=g(x)]$	$\displaystyle=\sum_{k=0}^{t}\Pr_{x\leftarrow H^{t}}[g(x)=k]\Pr_{x\leftarrow H^% {t}}[\hat{C}(x)=k\|g(x)=k]$
		$\displaystyle=\sum_{k=0}^{t}\frac{\binom{t}{k}}{2^{t}}\cdot\Pr_{x\leftarrow H^% {t}}[\hat{C}(x)=k\|g(x)=k]$
		$\displaystyle<\sum_{k=0}^{t}\frac{\binom{t}{k}}{2^{t}}\left(\Pr_{x\leftarrow H% ^{t}}\left[\hat{C}(x)=k\left\|g(x)=\frac{t}{2}\right.\right]+\left\|k-\frac{t}{2% }\right\|\cdot\gamma\right)$
		$\displaystyle\leq\frac{\binom{t}{\frac{t}{2}}}{2^{t}}\cdot\sum_{k=0}^{t}\Pr_{x% \leftarrow H^{t}}\left[\hat{C}(x)=k\left\|g(x)=\frac{t}{2}\right.\right]+\sum_{% k=0}^{t}\frac{\binom{t}{k}}{2^{t}}\left\|k-\frac{t}{2}\right\|\cdot\gamma$
		$\displaystyle\leq\frac{\binom{t}{\frac{t}{2}}}{2^{t}}\left(1+\frac{t}{2}\cdot% \gamma\right).$

	$\displaystyle\Pr_{\bar{x}\leftarrow H^{k}}\left[C(\pi(\bar{x},\hat{x}))=g(\pi(% \bar{x},\hat{x}))\right]$
	$\displaystyle=\sum_{i=0}^{k}\Pr_{\bar{x}\leftarrow H^{k}}\left[\bar{x}\in H_{i% }^{k}\right]\Pr_{\bar{x}\leftarrow H^{k}}\left[C(\pi(\bar{x},\hat{x}))=g(\bar{% x},\hat{x})\left\|\bar{x}\in H_{i}^{k}\right.\right]$
	$\displaystyle=\sum_{i=0}^{k}\Pr_{\bar{x}\leftarrow H^{k}}\left[\bar{x}\in H_{i% }^{k}\right]\Pr_{\bar{x}\leftarrow H^{k}}\left[C(\pi(\bar{x},\hat{x}))=ai+b(k-% i)+\Delta\left\|\bar{x}\in H_{i}^{k}\right.\right]$
	$\displaystyle<\frac{1}{2^{k}}\sum_{i=0}^{k}\binom{k}{i}\left(\Pr_{\bar{x}% \leftarrow H^{k}}\left[C(\pi(\bar{x},\hat{x}))=ai+b(k-i)+\Delta\left\|\bar{x}% \in H_{\lfloor\frac{k}{2}\rfloor}^{k}\right.\right]+\left\|i-\lfloor\frac{k}{2}% \rfloor\right\|\gamma\right)$
	$\displaystyle\leq\frac{1}{2^{k}}\left(\binom{k}{\lfloor\frac{k}{2}\rfloor}\sum% _{i=0}^{k}\Pr_{\bar{x}\leftarrow H^{k}}\left[C(\pi(\bar{x},\hat{x}))=ai+b(k-i)% +\Delta\left\|\bar{x}\in H_{\lfloor\frac{k}{2}\rfloor}^{k}\right.\right]+\lceil% \frac{k}{2}\rceil\gamma\cdot\binom{k}{\lfloor\frac{k}{2}\rfloor}\right)$
	$\displaystyle\leq\frac{\binom{k}{\lfloor\frac{k}{2}\rfloor}}{2^{k}}\left(1+% \lceil\frac{k}{2}\rceil\gamma\right).$

		$\displaystyle\Pr_{\begin{subarray}{c}\bar{x}\leftarrow H^{k}\\ \bar{x}^{\prime}\leftarrow\pi(\bar{x},\hat{x})\end{subarray}}\left[C(\bar{x}^{% \prime})\in(g_{t}(\bar{x}^{\prime})\pm\epsilon)\right]$
		$\displaystyle=\sum_{i=0}^{k}\Pr_{\begin{subarray}{c}\bar{x}\leftarrow H^{k}\\ \bar{x}^{\prime}\leftarrow\pi(\bar{x},\hat{x})\end{subarray}}\left[\bar{x}\in H% _{i}^{k}\right]\cdot\Pr_{\begin{subarray}{c}\bar{x}\leftarrow H^{k}\\ \bar{x}^{\prime}\leftarrow\pi(\bar{x},\hat{x})\end{subarray}}\left[C(\bar{x}^{% \prime})\in(g_{t}(\bar{x}^{\prime})\pm\epsilon)\left\|\bar{x}\in H_{i}^{k}% \right.\right]$
		$\displaystyle=\frac{1}{2^{k}}\sum_{i=0}^{k}\binom{k}{i}\Pr_{\begin{subarray}{c% }\bar{x}\leftarrow H^{k}\\ \bar{x}^{\prime}\leftarrow\pi(\bar{x},\hat{x})\end{subarray}}\left[C(\bar{x}^{% \prime})\in(g_{k}(\bar{x})+\Delta\pm\epsilon)\left\|\bar{x}\in H_{i}^{k}\right.\right]$
		$\displaystyle=\frac{1}{2^{k}}\sum_{i=-\frac{k}{2}}^{\frac{k}{2}}\binom{k}{% \frac{k}{2}+i}\Pr_{\begin{subarray}{c}\bar{x}\leftarrow H^{k}\\ \bar{x}^{\prime}\leftarrow\pi(\bar{x},\hat{x})\end{subarray}}\left[C(\bar{x}^{% \prime})\in(g_{k}(\bar{x})+\Delta\pm\epsilon)\left\|\bar{x}\in H_{\frac{k}{2}+i% }^{k}\right.\right]$
		$\displaystyle<\frac{1}{2^{k}}\sum_{i=-\frac{k}{2}}^{\frac{k}{2}}\binom{k}{% \frac{k}{2}+i}\Pr_{\begin{subarray}{c}\bar{x}\leftarrow H^{k}\\ \bar{x}^{\prime}\leftarrow\pi(\bar{x},\hat{x})\end{subarray}}\left[C(\bar{x}^{% \prime})\in(g_{k}(\bar{x})+i(a-b)+\Delta\pm(\epsilon+2d\left\|i\right\|))\left\|% \bar{x}\in H_{\frac{k}{2}}^{k}\right.\right]$		(6)
		$\displaystyle+\frac{1}{2^{k}}\sum_{i=-\frac{k}{2}}^{\frac{k}{2}}\binom{k}{% \frac{k}{2}+i}\cdot\left\|i\right\|\gamma$
		$\displaystyle\leq\frac{\binom{k}{\frac{k}{2}}}{2^{k}}\left(\frac{3\sqrt{k}}{l}% +3+\frac{k}{2}\gamma\right).$

	$\displaystyle\Pr_{x\leftarrow H}[C^{\prime}(x)\in(f(x)\pm\epsilon)]$
	$\displaystyle=\frac{1}{2}\Pr_{x\leftarrow H}[C^{\prime}(x)\in(f(x)\pm\epsilon)% \|x\in H_{a}]+\frac{1}{2}\Pr_{x\leftarrow H}[C^{\prime}(x)\in(f(x)\pm\epsilon)\|% x\in H_{b}]$
	$\displaystyle\geq\frac{1}{2}\Pr_{\begin{subarray}{c}x\leftarrow H\\ \bar{x}\leftarrow\pi_{k}(x_{1},\ldots,x_{k-1},x)\\ \bar{x}^{\prime}\leftarrow\pi(\bar{x},\hat{x})\end{subarray}}\left[C(\bar{x}^{% \prime})\in(g_{t}(\bar{x}^{\prime})+v\pm\epsilon^{\prime})\left\|x\in H_{a}% \right.\right]$
	$\displaystyle+\frac{1}{2}\Pr_{\begin{subarray}{c}x\leftarrow H\\ \bar{x}\leftarrow\pi_{k}(x_{1},\ldots,x_{k-1},x)\\ \bar{x}^{\prime}\leftarrow\pi(\bar{x},\hat{x})\end{subarray}}\left[C(\bar{x}^{% \prime})\not\in(g_{t}(\bar{x}^{\prime})+v+v^{\prime}\pm(\epsilon^{\prime}+2d))% \left\|x\in H_{b}\right.\right].$
	$\displaystyle\geq\frac{1}{2}(1+\gamma),$

Hardness Amplification for Real-Valued Functions

Abstract

Keywords and phrases:

Copyright and License:

2012 ACM Subject Classification:

Funding:

Related Version:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Evaluating Functions

Theorem 1.1 (Simplification of Theorem 3.1).

Approximating Functions

Theorem 1.2 (Simplification of Theorem 4.1).

Paper Outline

1.1 Corollaries

Optimization Problems

Corollary 1.3.

Entropy Estimation

Corollary 1.4.

Approximate Counting

Corollary 1.5.

1.2 Technical Overview

Hardness of {𝟎,𝟏}-valued functions

Reducing to two outputs

Amplifying using hardcore sets

2 Preliminaries

2.1 Notations

2.2 Average-Case Hardness

Definition 2.1 (Hardness of Evaluating Functions).

Definition 2.2 (Hardness of Satisfying Relations).

Definition 2.3.

Definition 2.4 (Hardness of Approximating Functions).

2.3 Hardcore Lemmas

Definition 2.5 (Relative Density).

Definition 2.6 (Majority Combiner).

Lemma 2.7 (Extended Hardcore Lemma).

▶ Remark 2.8.

2.4 Balancing Hardcore Distributions

Definition 2.9 (Balanced Distribution).

Lemma 2.10 (Balanced Hardcore).

3 Evaluating Integer-Valued Functions

Theorem 3.1.

Lemma 3.2.

Lemma 3.3 (Hardcore for Integer-Valued Functions).

Proof.

Lemma 3.4.

Theorem 3.1. [Restated, see original statement.]

Proof.

3.1 Proof of Lemma 3.2

Lemma 3.2. [Restated, see original statement.]

Proof.

3.2 Proof of Lemma 3.4

Lemma 3.4. [Restated, see original statement.]

Proof.

Claim 3.5.

3.2.1 Proof of Claim 3.5

Claim 3.5. [Restated, see original statement.]

Proof.

4 Approximating Real-Valued Functions

Theorem 4.1.

Lemma 4.2.

Lemma 4.3 (Hardcore for Real-Valued Functions).

Proof.

Lemma 4.4.

Theorem 4.1. [Restated, see original statement.]

Proof.

4.1 Proof of Lemma 4.2

Lemma 4.2. [Restated, see original statement.]

Proof.

Claim 4.5.

4.1.1 Proof of Claim 4.5

Claim 4.5. [Restated, see original statement.]

Proof.

4.2 Proof of Lemma 4.4

Lemma 4.4. [Restated, see original statement.]

Proof.

Claim 4.6.

Hardness of $\left\{0,1\right\}$ -valued functions

$\blacktriangleright$ Remark 2.8.