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.