Title: On being incoherent without being very hard

Authors: Richard Beigel and Joan Feigenbaum

Abstract: Trakhtenbrot calls a set A autoreducible if A is Turing-reducible to A via an oracle Turing machine that never queries the oracle about the input string. Yao considers sets that are autoreducible via probabilistic, polynomial-time oracle Turing machines, and he calls such sets coherent. We continue the study of autoreducible sets, including those that are autoreducible via a family of polynomial-sized circuits, which we call weakly coherent. Sets that are not weakly coherent are called strongly incoherent. We show

As corollaries, we obtain new lower bounds on program checkability and random-self-reducibility. These results answer open questions posed by Yao and by Blum and Kannan.

Download Full Paper