On the Power of Randomized Reductions and the Checkability of SAT
by Mohammad Mahmoody and David Xiao
Oded's comments
In my opinion, the main result is a proof that the class of problems
that are randomly Cook-reducible to SZK is contained in AM,
and I find the proof idea very inspiring.
It refers to a complete problem for SZK,
and the difficulty is that this complete problem
(which is in AM intersect coAM) is a promise problem.
That is, the difficulty in dealing with reductions
to promise problems is that the solver/oracle is not uniquely
determined by the problem in the reduction.
What they do is determine this solver/oracle in some specific way
(i.e., at random), and partition the non-promise of this problem
into "cells" and define corresponding decision problems (sets)
that are consistent with the original promise problem and contain
a subset of the cells but not others. Furthermore, for each instance,
and for all but few (say one...) of these decision problems,
membership/nonmembership of this instance wrt the said problem
can be proved in AM.
Indeed, the fact that this can be done relies on the
specifics of the promise problem (i.e., Entropy Difference).
Now, if the number of these decision problems can be madev larger than
the number of queries to the reduction, which is possible here,
then we are done by selecting a decision problem at random.
The original abstract
See ECCC posting.
Back to
list of Oded's choices.