Revision #3 Authors: Or Meir, Avishay Tal

Accepted on: 26th December 2017 15:13

Downloads: 707

Keywords:

The direct-sum question is a classical question that asks whether

performing a task on $m$ independent inputs is $m$ times harder

than performing it on a single input. In order to study this question,

Beimel et. al (Computational Complexity 23(1), 2014) introduced the following related problems:

* The choice problem: Given $m$ distinct instances, choose

one of them and solve it.

* The agreement problem: Given $m$ distinct instances, output

a solution that is correct for at least one of them.

It is easy to see that these problems are no harder than performing

the original task on a single instance, and it is natural to ask whether

it is strictly easier or not. In particular, proving that the choice

problem is not easier is necessary for proving a direct-sum theorem,

and is also related to the KRW composition conjecture (Computational Complexity 5, 3/4, 1995).

In this note, we observe that in a variety of computational models,

if $f$ is a random function then with high probability its corresponding

choice and agreement problem are not asymptotically easier than computing $f$

on a single instance (as long as $m$ is noticeably smaller than $2^{n}$).

Added a proof of Corollary 5.

Revision #2 Authors: Or Meir, Avishay Tal

Accepted on: 18th December 2017 16:42

Downloads: 615

Keywords:

The direct-sum question is a classical question that asks whether

performing a task on $m$ independent inputs is $m$ times harder

than performing it on a single input. In order to study this question,

Beimel et. al (Computational Complexity 23(1), 2014) introduced the following related problems:

* The choice problem: Given $m$ distinct instances, choose

one of them and solve it.

* The agreement problem: Given $m$ distinct instances, output

a solution that is correct for at least one of them.

It is easy to see that these problems are no harder than performing

the original task on a single instance, and it is natural to ask whether

it is strictly easier or not. In particular, proving that the choice

problem is not easier is necessary for proving a direct-sum theorem,

and is also related to the KRW composition conjecture (Computational Complexity 5, 3/4, 1995).

In this note, we observe that in a variety of computational models,

if $f$ is a random function then with high probability its corresponding

choice and agreement problem are not much easier than computing $f$

on a single instance (as long as $m$ is noticeably smaller than $2^{n}$).

Corrected an error in the statement of Theorem 4, and changed Corollary 5 to account for the change.

Revision #1 Authors: Or Meir, Avishay Tal

Accepted on: 7th October 2017 16:51

Downloads: 524

Keywords:

The direct-sum question is a classical question that asks whether

performing a task on $m$ independent inputs is $m$ times harder

than performing it on a single input. In order to study this question,

Beimel et. al (Computational Complexity 23(1), 2014) introduced the following related problems:

* The choice problem: Given $m$ distinct instances, choose

one of them and solve it.

* The agreement problem: Given $m$ distinct instances, output

a solution that is correct for at least one of them.

It is easy to see that these problems are no harder than performing

the original task on a single instance, and it is natural to ask whether

it is strictly easier or not. In particular, proving that the choice

problem is not easier is necessary for proving a direct-sum theorem,

and is also related to the KRW composition conjecture (Computational Complexity 5, 3/4, 1995).

In this note, we observe that in a variety of computational models,

if $f$ is a random function then with high probability its corresponding

choice and agreement problem are not asymptotically easier than computing $f$

on a single instance (as long as $m$ is noticeably smaller than $2^{n}$).

Added references to [JKS10] and to [CDKLM17].

performing a task on $m$ independent inputs is $m$ times harder

than performing it on a single input. In order to study this question,

Beimel et. al (Computational Complexity 23(1), 2014) introduced the following related problems:

* The choice problem: Given $m$ distinct instances, choose

one of them and solve it.

a solution that is correct for at least one of them.

the original task on a single instance, and it is natural to ask whether

it is strictly easier or not. In particular, proving that the choice

problem is not easier is necessary for proving a direct-sum theorem,

and is also related to the KRW composition conjecture (Computational Complexity 5, 3/4, 1995).

In this note, we observe that in a variety of computational models,

if $f$ is a random function then with high probability its corresponding

choice and agreement problem are not asymptotically easier than computing $f$

on a single instance (as long as $m$ is noticeably smaller than $2^{n}$).