94 citations · 176 across the 26 of their papers we have counts for
7 papers · 1 filter
Proving the power of postselection
Abuzer Yakaryilmaz, A. C. Cem Say
It is a widely believed, though unproven, conjecture that the capability of postselection increases the language recognition power of both probabilistic and quantum polynomial-time…
Causes of Ineradicable Spurious Predictions in Qualitative Simulation
Ö. Yılmaz, A. C. C. Say
It was recently proved that a sound and complete qualitative simulator does not exist, that is, as long as the input-output vocabulary of the state-of-the-art QSIM algorithm is use…
Tight bounds for the space complexity of nonregular language recognition by real-time machines
Abuzer Yakaryilmaz, A. C. Cem Say
We examine the minimum amount of memory for real-time, as opposed to one-way, computation accepting nonregular languages. We consider deterministic, nondeterministic and alternatin…
Quantum counter automata
A. C. Cem Say, Abuzer Yakaryilmaz
The question of whether quantum real-time one-counter automata (rtQ1CAs) can outperform their probabilistic counterparts has been open for more than a decade. We provide an affirma…
Finite state verifiers with constant randomness
Cem Say, Abuzer Yakaryilmaz
We give a new characterization of as the class of languages whose members have certificates that can be verified with small error in polynomial time by finite state m…
Computation with narrow CTCs
A. C. Cem Say, Abuzer Yakaryilmaz
We examine some variants of computation with closed timelike curves (CTCs), where various restrictions are imposed on the memory of the computer, and the information carrying capac…
NP has log-space verifiers with fixed-size public quantum registers
Abuzer Yakaryilmaz, A. C. Cem Say
In classical Arthur-Merlin games, the class of languages whose membership proofs can be verified by Arthur using logarithmic space (AM(log-space)) coincides with the class P \cite{…