Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #2 to TR10-126 | 17th April 2014 20:45

#### Query Complexity in Errorless Hardness Amplification

Revision #2
Authors: Thomas Watson
Accepted on: 17th April 2014 20:45
Keywords:

Abstract:

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.

Revision #1 to TR10-126 | 6th December 2010 04:37

#### Query Complexity in Errorless Hardness Amplification

Revision #1
Authors: Thomas Watson
Accepted on: 6th December 2010 04:37
Keywords:

Abstract:

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.

### Paper:

TR10-126 | 12th August 2010 08:02

#### Query Complexity in Errorless Hardness Amplification

TR10-126
Authors: Thomas Watson
Publication: 13th August 2010 15:07
Keywords:

Abstract:

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.

ISSN 1433-8092 | Imprint