Showing cs.CCShow all
3 papers · 1 filter
cs.CC2018
Postselecting probabilistic finite state recognizers and verifiers
Maksims Dimitrijevs, Abuzer Yakaryılmaz
In this paper, we investigate the computational and verification power of bounded-error postselecting realtime probabilistic finite state automata (PostPFAs). We show that PostPFAs…
cs.CC2018
Probabilistic verification of all languages
Maksims Dimitrijevs, Abuzer Yakaryılmaz
We present three protocols for verifying all languages: (i) For any unary (binary) language, there is a log-space (linear-space) interactive proof system (IPS); (ii) for any langua…
cs.CC2017
Uncountable realtime probabilistic classes
Maksims Dimitrijevs, Abuzer Yakaryılmaz
We investigate the minimum cases for realtime probabilistic machines that can define uncountably many languages with bounded error. We show that logarithmic space is enough for rea…