Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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

TR14-159 | 27th November 2014
A. C. Cem Say, Abuzer Yakaryilmaz

Magic coins are useful for small-space quantum machines

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

TR14-091 | 22nd July 2014
Ryan O'Donnell, A. C. Cem Say

One time-travelling bit is as good as logarithmically many

Revisions: 1

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

TR14-016 | 16th January 2014
Gökalp Demirci, A. C. Cem Say, Abuzer Yakaryilmaz

The Complexity of Debate Checking

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

TR13-004 | 11th November 2012
A. C. Cem Say, Abuzer Yakaryilmaz

Finite state verifiers with constant randomness

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

ISSN 1433-8092 | Imprint