Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

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

Query Complexity in Errorless Hardness Amplification

RSS-Feed




Revision #2
Authors: Thomas Watson
Accepted on: 17th April 2014 20:45
Downloads: 737
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
Downloads: 2397
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
Downloads: 2777
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