Locally Random Reductions: Improvements and Applications

The notions of reducibility and self-reducibility have yielded valuable insights into many branches of complexity theory. In this paper, we formally define and develop the theory of locally random reductions, which are special cases of multi-oracle instance hiding schemes [1,3]. Informally, a (t,n)-locally random reduction maps a problem instance chi to a set of random problem instances y sub 1,...,y sub n, in such a way that the answers to y sub 1,...y sub n allow one to reconstruct the answer to chi. Furthermore for any i sub 1,...,i sub t, the induced distribution on yi sub 1,...,yi sub t typically depends only on the size of chi.