## DIMACS TR: 94-45

## Two Remarks on Self-Correctability versus Random-Self-Reducibility

### Authors: Joan Feigenbaum, Lance Fortnow, Ashish V. Naik

**
ABSTRACT
**

We examine the relationship between two types of probabilistic
self-reductions that play crucial roles in the theory of interactive
proof systems, program-checking, and program-testing: "self-correctors"
and "random-self-reductions." It is well known [Blum et al., JCSS, 47
(1993), 549-595] that if a function is random-self-reducible, then it is also
self-correctable; furthermore, all known self-correctors use some form
of random-self-reducibility. However, whether self-correctability implies
random-self-reducibility, i.e., whether the two properties are equivalent,
remains an important open question.
We show that:

i. If UEEEXP is not contained in REEEXP, then there exists a function that
is nonadaptively self-correctable but not nonadaptively random-self-reducible.

ii. If #P is contained in FP, then every function that is nonadaptively
self-correctable with respect to a P-sampleable ensemble is also
nonadaptively random-self-reducible.

Paper available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-45.ps

DIMACS Home Page