94 citations · 176 across the 26 of their papers we have counts for
29 papers
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…
Read-once machines and the thermodynamic complexity of Maxwell's demons
Fırat Kıyak, A. C. Cem Say
The thermodynamical costs imposed by computational resource limitations like memory and time have been investigated before. We focus on a new computational limitation, namely, the…
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…
Homing Vector Automata
Özlem Salehi, A. C. Cem Say, Flavio D'Alessandro
We introduce homing vector automata, which are finite automata augmented by a vector that is multiplied at each step by a matrix determined by the current transition, and have to r…
Inkdots as advice for finite automata
Uğur Küçük, A. C. Cem Say, Abuzer Yakaryılmaz
We examine inkdots placed on the input string as a way of providing advice to finite automata, and establish the relations between this model and the previously studied models of a…
Homing Vector Automata
Özlem Salehi, A. C. Cem Say
We introduce homing vector automata, which are finite automata augmented by a vector that is multiplied at each step by a matrix determined by the current transition, and have to r…
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…
Alternating, private alternating, and quantum alternating realtime automata
Gökalp Demirci, Mika Hirvensalo, Klaus Reinhardt +2
We present new results on realtime alternating, private alternating, and quantum alternating automaton models. Firstly, we show that the emptiness problem for alternating one-count…
Quantum finite automata: A modern introduction
A. C. Cem Say, Abuzer Yakaryilmaz
We present five examples where quantum finite automata (QFAs) outperform their classical counterparts. This may be useful as a relatively simple technique to introduce quantum comp…
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…
Finite automata with advice tapes
Uğur Küçük, A. C. Cem Say, Abuzer Yakaryılmaz
We define a model of advised computation by finite automata where the advice is provided on a separate tape. We consider several variants of the model where the advice is determini…
Real-Time Vector Automata
Özlem Salehi, Abuzer Yakaryılmaz, A. C. Cem Say
We study the computational power of real-time finite automata that have been augmented with a vector of dimension k, and programmed to multiply this vector at each step by an appro…
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{…
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 .