94 citations · 376 across the 55 of their papers we have counts for
30 papers · 1 filter
Quantum Logarithmic Space and Post-selection
François Le Gall, Harumichi Nishimura, Abuzer Yakaryılmaz
Post-selection, the power of discarding all runs of a computation in which an undesirable event occurs, is an influential concept introduced to the field of quantum complexity theo…
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…
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…
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…
Zero-Error Affine, Unitary, and Probabilistic OBDDs
Rishat Ibrahimov, Kamil Khadiev, Krisjanis Prusis +2
We introduce the affine OBDD model and show that zero-error affine OBDDs can be exponentially narrower than bounded-error unitary and probabilistic OBDDs on certain problems. Moreo…
Nondeterministic unitary OBDDs
Aida Gainutdinova, Abuzer Yakaryılmaz
We investigate the width complexity of nondeterministic unitary OBDDs (NUOBDDs). Firstly, we present a generic lower bound on their widths based on the size of strong 1-fooling set…