94 citations · 176 across the 26 of their papers we have counts for
19 papers · 1 filter
Subexponential-Time Quantum Advantage beyond Double-Logarithmic Space
A. C. Cem Say
We prove that subexponential-time quantum Turing machines are superior to their classical counterparts within common space bounds in . For that purpose, we define i…
has polynomial-time finite-state verifiers
M. Utkan Gezer, A. C. Cem Say
Interactive proof systems whose verifiers are constant-space machines have interesting features that do not have counterparts in the better studied case where the verifiers operate…
Real-Time, Constant-Space, Constant-Randomness Verifiers
M. Utkan Gezer, Özdeniz Dolu, Nevzat Ersoy +1
We study the class of languages that have membership proofs which can be verified by real-time finite-state machines using only a constant number of random bits, regardless of the…
Energy Complexity of Regular Languages
Fırat Kıyak, A. C. Cem Say
Each step that results in a bit of information being ``forgotten'' by a computing device has an intrinsic energy cost. Although any Turing machine can be rewritten to be thermodyna…
Constant-Space, Constant-Randomness Verifiers with Arbitrarily Small Error
M. Utkan Gezer, A. C. Cem Say
We study the capabilities of probabilistic finite-state machines that act as verifiers for certificates of language membership for input strings, in the regime where the verifiers…
Magic coins are useful for small-space quantum machines
A. C. Cem Say, Abuzer Yakaryilmaz
Although polynomial-time probabilistic Turing machines can utilize uncomputable transition probabilities to recognize uncountably many languages with bounded error when allowed to…
Debates with small transparent quantum verifiers
Abuzer Yakaryilmaz, A. C. Cem Say, H. Gökalp Demirci
We study a model where two opposing provers debate over the membership status of a given string in a language, trying to convince a weak verifier whose coins are visible to all. We…
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…
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{…
Quantum computation with devices whose contents are never read
Abuzer Yakaryilmaz, Rusins Freivalds, A. C. Cem Say +1
In classical computation, a "write-only memory" (WOM) is little more than an oxymoron, and the addition of WOM to a (deterministic or probabilistic) classical computer brings no ad…
Quantum function computation using sublogarithmic space (abstract & poster)
A. C. Cem Say, Abuzer Yakaryilmaz
We prove that quantum Turing machines are strictly superior to probabilistic Turing machines in function computation for any space bound .
Unbounded-error quantum computation with small space bounds
Abuzer Yakaryilmaz, A. C. Cem Say
We prove the following facts about the language recognition power of quantum Turing machines (QTMs) in the unbounded error setting: QTMs are strictly more powerful than probabilist…
Succinctness of two-way probabilistic and quantum finite automata
Abuzer Yakaryilmaz, A. C. Cem Say
We prove that two-way probabilistic and quantum finite automata (2PFA's and 2QFA's) can be considerably more concise than both their one-way versions (1PFA's and 1QFA's), and two-w…
Languages recognized by nondeterministic quantum finite automata
Abuzer Yakaryilmaz, A. C. Cem Say
The nondeterministic quantum finite automaton (NQFA) is the only known case where a one-way quantum finite automaton (QFA) model has been shown to be strictly superior in terms of…
Language recognition by generalized quantum finite automata with unbounded error (abstract & poster)
Abuzer Yakaryilmaz, A. C. Cem Say
In this note, we generalize the results of arXiv:0901.2703v1 We show that all one-way quantum finite automaton (QFA) models that are at least as general as Kondacs-Watrous QFA's ar…