Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Randomized Computation:
TR95-021 | 20th April 1995
Marek Karpinski, Rutger Verbeek

On Randomized Versus Deterministic Computation

In contrast to deterministic or nondeterministic computation, it is
a fundamental open problem in randomized computation how to separate
different randomized time classes (at this point we do not even know
how to separate linear randomized time from ${\mathcal O}(n^{\log n})$
randomized time) or how to ... more >>>

TR12-099 | 5th August 2012
Nikos Leonardos

An improved lower bound for the randomized decision tree complexity of recursive majority

Revisions: 1

We prove that the randomized decision tree complexity of the recursive majority-of-three is $\Omega(2.6^d)$, where $d$ is the depth of the recursion. The proof is by a bottom up induction, which is same in spirit as the one in the proof of Saks and Wigderson in their FOCS 1986 paper ... 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-100 | 4th August 2014
Salman Beigi, Omid Etesami, Amin Gohari

The Value of Help Bits in Randomized and Average-Case Complexity

"Help bits" are some limited trusted information about an instance or instances of a computational problem that may reduce the computational complexity of solving that instance or instances. In this paper, we study the value of help bits in the settings of randomized and average-case complexity.

Amir, Beigel, and Gasarch ... more >>>

ISSN 1433-8092 | Imprint