Maciej Liskiewicz, RĂ¼diger Reischuk

This paper tries to fully characterize the properties and relationships

of space classes defined by Turing machines that use less than

logarithmic space - may they be deterministic,

nondeterministic or alternating (DTM, NTM or ATM).

We provide several examples of specific languages ...
more >>>

Oded Goldreich, Tom Gur, Ron Rothblum

Proofs of proximity are probabilistic proof systems in which the verifier only queries a sub-linear number of input bits, and soundness only means that, with high probability, the input is close to an accepting input. In their minimal form, called Merlin-Arthur proofs of proximity (MAP), the verifier receives, in addition ... more >>>