University of Tartu - ©2011 Rafik Chaabouni - Last update: 05.05.2013 19:20
Date: 06/05/2013 at 15:00 (not 15:15)
Location: J. Liivi 2, room 202 (second floor)
Speaker: Abuzer Yakaryilmaz
Title: Finite state verifiers with constant randomness
This talk is based on:
A. C. Cem Say and Abuzer Yakaryilmaz, "Finite state verifiers with constant randomness", CoRR, Vol. abs/1102.2719, 2011.
Abstract:
We give a new characterization of NL as the class of languages whose members have certificates that can be verified with small error in polynomial time by finite state machines that use a constant number of random bits, as opposed to its conventional description in terms of deterministic logarithmic-space verifiers. It turns out that allowing two-way interaction with the prover does not change the class of verifiable languages, and that no polynomially bounded amount of randomness is useful for constant-memory computers when used as language recognizers, or public-coin verifiers. A corollary of our main result is that the class of outcome problems corresponding to O(log(n))-space bounded games of incomplete information where the universal player is allowed a constant number of moves equals NL.