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$.
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 >>>
We propose a new definition of the class of search problems that correspond to BPP.
Specifically, a problem in this class is specified by a polynomial-time approximable function $q:\{0,1\}^*\times\{0,1\}^*\to[0,1]$ that associates, with each possible solution $y$ to an instance $x$, a quality $q(x,y)$.
Intuitively, quality 1 corresponds to perfectly ...
more >>>
