21 citations · 21 across the 7 of their papers we have counts for
Showing 2018Show all
2 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…