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