Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Wolfgang Merkle:

TR02-056 | 19th September 2002
Todd Ebert, Wolfgang Merkle, Heribert Vollmer

On the Autoreducibility of Random Sequences

A binary sequence A=A(0)A(1).... is called i.o. Turing-autoreducible if A is reducible to itself via an oracle Turing machine that never queries its oracle at the current input, outputs either A(x) or a don't-know symbol on any given input x, and outputs A(x) for infinitely many x. If in addition ... more >>>

TR99-034 | 30th August 1999
Wolfgang Merkle

The global power of additional queries to p-random oracles.

We consider separations of reducibilities in the context of
resource-bounded measure theory. First, we show a result on
polynomial-time bounded reducibilities: for every p-random set R,
there is a set which is reducible to R with k+1 non-adaptive
queries, but is not reducible to any other p-random set with ... more >>>

ISSN 1433-8092 | Imprint