DIMACS TR: 96-16
On Coherence, Random-Self-Reducibility, and Self-Correction
Authors: Joan Feigenbaum, Lance Fortnow, Sophie Laplante, Ashish Naik
ABSTRACT
We address two questions about self-reducibility -- the power
of adaptiveness in examiners that take advice and the relationship
between random-self-reducibility and self-correctability. We first
show that adaptive examiners are more powerful than nonadaptive
examiners, even if the nonadaptive ones are nonuniform. Blum et al.
[Blum, Luby and Rubinfeld, Journal of Computer and System
Sciences, 59:549--595, 1993] showed that every random-self-reducible
function is self-correctable. However, whether self-correctability
implies random-self-reducibility is unknown. We show that, under a
reasonable complexity hypothesis, there exists a self-correctable
function that is not random-self-reducible. For P-sampleable
distributions, however, we show that constructing a self-correctable
function that is not random-self-reducible is as hard as proving that
P is not equal to PP.
This work was presented in preliminary form at the IEEE Conference
on Computational Complexity, Philadelphia PA, May 1996.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-16.ps.gz
DIMACS Home Page