DIMACS TR: 94-45

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

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


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