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 #3 to TR17-148 | 26th December 2017 15:13

The Choice and Agreement Problems of a Random Function

RSS-Feed




Revision #3
Authors: Or Meir, Avishay Tal
Accepted on: 26th December 2017 15:13
Downloads: 122
Keywords: 


Abstract:

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}$).



Changes to previous version:

Added a proof of Corollary 5.


Revision #2 to TR17-148 | 18th December 2017 16:42

The Choice and Agreement Problems of a Random Function





Revision #2
Authors: Or Meir, Avishay Tal
Accepted on: 18th December 2017 16:42
Downloads: 131
Keywords: 


Abstract:

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}$).



Changes to previous version:

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


Revision #1 to TR17-148 | 7th October 2017 16:51

The Choice and Agreement Problems of a Random Function





Revision #1
Authors: Or Meir, Avishay Tal
Accepted on: 7th October 2017 16:51
Downloads: 133
Keywords: 


Abstract:

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}$).



Changes to previous version:

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


Paper:

TR17-148 | 6th October 2017 13:23

The Choice and Agreement Problems of a Random Function





TR17-148
Authors: Or Meir, Avishay Tal
Publication: 6th October 2017 13:44
Downloads: 274
Keywords: 


Abstract:

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}$).



ISSN 1433-8092 | Imprint