All reports by Author A. C. Cem Say:

__
TR16-147
| 19th September 2016
__

Ryan O'Donnell, A. C. Cem Say#### The weakness of CTC qubits and the power of approximate counting

Revisions: 1

__
TR14-159
| 27th November 2014
__

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

__
TR14-091
| 22nd July 2014
__

Ryan O'Donnell, A. C. Cem Say#### One time-travelling bit is as good as logarithmically many

Revisions: 1

__
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

Ryan O'Donnell, A. C. Cem Say

We present two results in structural complexity theory concerned with the following interrelated

topics: computation with postselection/restarting, closed timelike curves (CTCs), and

approximate counting. The first result is a new characterization of the lesser known complexity

class BPP_path in terms of more familiar concepts. Precisely, BPP_path is the class of ...
more >>>

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 >>>

Ryan O'Donnell, A. C. Cem Say

We consider computation in the presence of closed timelike curves (CTCs), as proposed by Deutsch. We focus on the case in which the CTCs carry classical bits (as opposed to qubits). Previously, Aaronson and Watrous showed that computation with polynomially many CTC bits is equivalent in power to PSPACE. On ... 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 >>>