Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Probabilistic polynomial-time:
TR04-056 | 1st July 2004
Vinodchandran Variyam

A note on the circuit complexity of PP

In this short note we show that for any integer k, there are
languages in the complexity class PP that do not have Boolean
circuits of size $n^k$.

more >>>

TR04-093 | 9th November 2004
Oded Goldreich, Madhu Sudan, Luca Trevisan

From logarithmic advice to single-bit advice

Building on Barak's work (Random'02),
Fortnow and Santhanam (FOCS'04) proved a time hierarchy
for probabilistic machines with one bit of advice.
Their argument is based on an implicit translation technique,
which allow to translate separation results for short (say logarithmic)
advice (as shown by Barak) into separations for ... more >>>

ISSN 1433-8092 | Imprint