An errorless circuit for a boolean function is one that outputs the correct answer or ``don't know'' on each input (and never outputs the wrong answer). The goal of errorless hardness amplification is to show that if $f$ has no size $s$ errorless circuit that outputs ``don't know'' on at most a $\delta$ fraction of inputs, then some $f'$ related to $f$ has no size $s'$ errorless circuit that outputs ``don't know'' on at most a $1-\epsilon$ fraction of inputs. Thus the hardness is ``amplified'' from $\delta$ to $1-\epsilon$. Unfortunately, this amplification comes at the cost of a loss in circuit size. This is because such results are proven by reductions which show that any size $s'$ errorless circuit for $f'$ that outputs ``don't know'' on at most a $1-\epsilon$ fraction of inputs could be used to construct a size $s$ errorless circuit for $f$ that outputs ``don't know'' on at most a $\delta$ fraction of inputs. If the reduction makes $q$ queries to the hypothesized errorless circuit for $f'$, then plugging in a size $s'$ circuit yields a circuit of size $\geq qs'$, and thus we must have $s'\leq s/q$. Hence it is desirable to keep the query complexity to a minimum.

The first results on errorless hardness amplification were obtained by Bogdanov and Safra. They achieved query complexity $O\big((\frac{1}{\delta}\log\frac{1}{\epsilon})^2\cdot\frac{1}{\epsilon}\log\frac{1}{\delta}\big)$ when $f'$ is the XOR of several independent copies of $f$. We improve the query complexity (and hence the loss in circuit size) to $O\big(\frac{1}{\epsilon}\log\frac{1}{\delta}\big)$, which is optimal up to constant factors for nonadaptive black-box errorless hardness amplification.

Bogdanov and Safra also proved a result that allows for errorless hardness amplification within $\NP$. They achieved query complexity $O\big(k^3\cdot\frac{1}{\epsilon^2}\log\frac{1}{\delta}\big)$ when $f'$ consists of any monotone function applied to the outputs of $k$ independent copies of $f$, provided the monotone function satisfies a certain combinatorial property parameterized by $\delta$ and $\epsilon$. We improve the query complexity to $O\big(\frac{k}{t}\cdot\frac{1}{\epsilon}\log\frac{1}{\delta}\big)$, where $t\geq 1$ is a certain parameter of the monotone function.

As a side result, we prove a lower bound on the advice complexity of black-box reductions for errorless hardness amplification.

An errorless circuit for a boolean function is one that outputs the correct answer or ``don't know'' on each input (and never outputs the wrong answer). The goal of errorless hardness amplification is to show that if $f$ has no size $s$ errorless circuit that outputs ``don't know'' on at most a $\delta$ fraction of inputs, then some $f'$ related to $f$ has no size $s'$ errorless circuit that outputs ``don't know'' on at most a $1-\epsilon$ fraction of inputs. Thus the hardness is ``amplified'' from $\delta$ to $1-\epsilon$. Unfortunately, this amplification comes at the cost of a loss in circuit size. This is because such results are proven by reductions which show that any size $s'$ errorless circuit for $f'$ that outputs ``don't know'' on at most a $1-\epsilon$ fraction of inputs could be used to construct a size $s$ errorless circuit for $f$ that outputs ``don't know'' on at most a $\delta$ fraction of inputs. If the reduction makes $q$ queries to the hypothesized errorless circuit for $f'$, then plugging in a size $s'$ circuit yields a circuit of size $\geq qs'$, and thus we must have $s'\leq s/q$. Hence it is desirable to keep the query complexity to a minimum.

The first results on errorless hardness amplification were obtained by Bogdanov and Safra. They achieved query complexity $O\big((\frac{1}{\delta}\log\frac{1}{\epsilon})^2\cdot\frac{1}{\epsilon}\log\frac{1}{\delta}\big)$ when $f'$ is the XOR of several independent copies of $f$. We improve the query complexity (and hence the loss in circuit size) to $O\big(\frac{1}{\epsilon}\log\frac{1}{\delta}\big)$, which is optimal up to constant factors for nonadaptive black-box errorless hardness amplification.

Bogdanov and Safra also proved a result that allows for errorless hardness amplification within $\NP$. They achieved query complexity $O\big(k^3\cdot\frac{1}{\epsilon^2}\log\frac{1}{\delta}\big)$ when $f'$ consists of any monotone function applied to the outputs of $k$ independent copies of $f$, provided the monotone function satisfies a certain combinatorial property parameterized by $\delta$ and $\epsilon$. We improve the query complexity to $O\big(\frac{k}{t}\cdot\frac{1}{\epsilon}\log\frac{1}{\delta}\big)$, where $t\geq 1$ is a certain parameter of the monotone function.

As a side result, we prove a lower bound on the advice complexity of black-box reductions for errorless hardness amplification.

An errorless circuit for a boolean function is one that outputs the correct answer or ``don't know'' on each input (and never outputs the wrong answer). The goal of errorless hardness amplification is to show that if $f$ has no size $s$ errorless circuit that outputs ``don't know'' on at most a $\delta$ fraction of inputs, then some $f'$ related to $f$ has no size $s'$ errorless circuit that outputs ``don't know'' on at most a $1-\epsilon$ fraction of inputs. Thus the hardness is ``amplified'' from $\delta$ to $1-\epsilon$. Unfortunately, this amplification comes at the cost of a loss in circuit size. This is because such results are proven by reductions which show that any size $s'$ errorless circuit for $f'$ that outputs ``don't know'' on at most a $1-\epsilon$ fraction of inputs could be used to construct a size $s$ errorless circuit for $f$ that outputs ``don't know'' on at most a $\delta$ fraction of inputs. If the reduction makes $q$ queries to the hypothesized errorless circuit for $f'$, then plugging in a size $s'$ circuit yields a circuit of size $\geq qs'$, and thus we must have $s'\leq s/q$. Hence it is desirable to keep the query complexity to a minimum.

The first results on errorless hardness amplification were obtained by Bogdanov and Safra. They achieved query complexity $O\big((\frac{1}{\delta}\log\frac{1}{\epsilon})^2\cdot\frac{1}{\epsilon}\log\frac{1}{\delta}\big)$ when $f'$ is the XOR of several independent copies of $f$. We improve the query complexity (and hence the loss in circuit size) to $O\big(\frac{1}{\epsilon}\log\frac{1}{\delta}\big)$, which is optimal up to constant factors for nonadaptive black-box errorless hardness amplification.

Bogdanov and Safra also proved a result that allows for errorless hardness amplification within $\NP$. They achieved query complexity $O\big(k^3\cdot\frac{1}{\epsilon^2}\log\frac{1}{\delta}\big)$ when $f'$ consists of any monotone function applied to the outputs of $k$ independent copies of $f$, provided the monotone function satisfies a certain combinatorial property parameterized by $\delta$ and $\epsilon$. We improve the query complexity to $O\big(\frac{k}{t}\cdot\frac{1}{\epsilon}\log\frac{1}{\delta}\big)$, where $t\geq 1$ is a certain parameter of the monotone function.

As a side result, we prove a lower bound on the advice complexity of black-box reductions for errorless hardness amplification.