All reports by Author Abuzer Yakaryilmaz:

__
TR14-159
| 27th November 2014
__

A. C. Cem Say, Abuzer Yakaryilmaz#### Magic coins are useful for small-space quantum machines

__
TR14-136
| 17th October 2014
__

Viliam Geffert, Abuzer Yakaryilmaz#### Classical Automata on Promise Problems

__
TR14-016
| 16th January 2014
__

GĂ¶kalp Demirci, A. C. Cem Say, Abuzer Yakaryilmaz#### The Complexity of Debate Checking

__
TR13-004
| 11th November 2012
__

A. C. Cem Say, Abuzer Yakaryilmaz#### Finite state verifiers with constant randomness

__
TR12-130
| 3rd October 2012
__

Abuzer Yakaryilmaz#### Public-qubits versus private-coins

__
TR12-091
| 16th July 2012
__

Abuzer Yakaryilmaz#### One-counter verifiers for decidable languages

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 use logarithmic space, it is known that such ``magic coins'' give no additional computational power to constant-space versions of those machines. We show that adding a few quantum bits ... more >>>

Viliam Geffert, Abuzer Yakaryilmaz

Promise problems were mainly studied in quantum automata theory. Here we focus on state complexity of classical automata for promise problems. First, it was known that there is a family of unary promise problems solvable by quantum automata by using a single qubit, but the number of states required by ... more >>>

GĂ¶kalp Demirci, A. C. Cem Say, Abuzer Yakaryilmaz

We study probabilistic debate checking, where a silent resource-bounded verifier reads a dialogue about the membership of a given string in the language under consideration between a prover and a refuter. We consider debates of partial and zero information, where the prover is prevented from seeing some or all of ... more >>>

A. C. Cem Say, Abuzer Yakaryilmaz

We give a new characterization of NL as the class of languages whose members have certificates that can be verified with small error in polynomial time by finite state machines that use a constant number of random bits, as opposed to its conventional description in terms of deterministic logarithmic-space verifiers. ... more >>>

Abuzer Yakaryilmaz

We introduce a new public quantum interactive proof system, namely qAM, by augmenting the verifier with a fixed-size quantum register in Arthur-Merlin game. We focus on space-bounded verifiers, and compare our new public system with private-coin interactive proof (IP) system in the same space bounds. We show that qAM systems ... more >>>

Abuzer Yakaryilmaz

Condon and Lipton (FOCS 1989) showed that the class of languages having a space-bounded interactive proof system (IPS) is a proper subset of decidable languages, where the verifier is a probabilistic Turing machine. In this paper, we show that if we use architecturally restricted verifiers instead of restricting the working ... more >>>