On Random Self-reducible properties

Question

Permanent is random self-reducible. $\mathsf{SAT}$ is not random self-reducible since otherwise the polynomial hierarchy collapses to $\mathsf{\Sigma_3}$.

1) Is $k$-sum random self-reducible?

That is if $k$-sum can be computed in time $n^{O(k^b)}$ for some $0<b<1$ on $\frac{1}{2}+\epsilon$ of inputs where $n$ is the number of input integers, then can $k$-sum be computed time $n^{O(k^b)}$ for all inputs of $n$ input integers in a randomized sense?

The Patrascu-Williams paper http://people.csail.mit.edu/mip/papers/sat-lbs/paper.pdf talks about deterministic algorithms and does not imply hierarchy collapse but only tells that the ETH fails (somewhat mildly) when we have a deterministic $n^{O(k^b)}$ algorithm. We have a randomized setting here and even if we have such a random self-reducible condition satisfied, we may still not upset the big picture.

2)Likewise can the $\mathsf{NP=coNP}$ problem be random self reducible?

That is, if for an $\mathsf{NP}$ complete problem we have short certificates for $\frac{1}{2}+\epsilon$ of the $\mathsf{NO}$ instances, then we have short certificates for all $\mathsf{NO}$ instances in a randomized sense?

Update The results in http://research.microsoft.com/en-us/um/redmond/groups/theory/jehkim/a-yspapers/unsat.pdf seems to indicate the $\mathsf{NP}=\mathsf{coNP}$ issue is not random self-reducible.

Answer 1

I don't know the answer to Question (1)---I suspect there is no such reduction. But I have a couple of points to make.

A non-adaptive random self-reduction (to the uniform distribution) is a poly-time randomized algorithm $R$ which, given an arbitrary instance $x$ of length $n$ for the decision problem for $L$, produces a list $y^1, \ldots, y^{q(n)}$ of instances of some second length $\ell(n)$. We have the properties that

(i) each $y^i$ generated by $R$ is individually uniformly distributed, for any fixed input $x$ (although there may be complicated dependence between the $y^i$s, which in some way "encodes" $x$);

(ii) there is a second poly-time algorithm $R'$ which, given $y^1, \ldots, y^q$ along with their $L$-membership values $b^1, \ldots, b^q$ ($b_i = [y_i \in L]$), outputs the desired value $[x \in L]$.

Feigenbaum and Fortnow prove that if an $NP$-complete language has such a reduction then the Polynomial Hierarchy collapses. The argument applies to other target distributions, not just the uniform distribution.

Now my first point (regarding your Question (2)) is that their result directly gives evidence for the difficulty of showing a worst-case to average-case connection for proof systems certifying unsatisfiability of Boolean formulas. Because the most natural way you'd try to argue that random unsatisfiable formulas are hard to refute (assuming $NP \neq coNP$), is by exhibiting a random self-reduction as above. Now in the study of proof systems, it might be natural to allow the recovery algorithm $R'$ to be nondeterministic, for example; I believe the [FF] analysis techniques would still apply, but this would take verification after defining things carefully.

My second point is that non-adaptive random self-reductions as above are not the only way to establish average-case hardness of a language $L$ (assuming its worst-case hardness). There is also the more general notion of a self-correction reduction, which converts any mostly-correct algorithm for $L$ into a fully-correct algorithm, but which does not guarantee that its individual queries be distributed according to any particular distribution (they may depend heavily on the input $x$). Bogdanov and Trevisan proved that non-adaptive self-correctors for $NP$-complete languages would also collapse the Polynomial Hierarchy.
But it is completely open whether adaptive self-correctors exist for $NP$-complete languages. I believe the question of adaptive random self-reductions for SAT is also open. Even if all of these could be ruled out (under the assumption $PH$ does not collapse, say), there might conceivably still be some other, less constructive proof of a worst-case to average-case hardness connection for $NP$. Bogdanov-Trevisan give a good discussion of the issues here (see also their survey on average-case complexity).