2004 · 51 citations · 20 references
ComputingComputer ScienceAlgorithmsProbability TheoryTheory Of ComputationComputational ComplexityTime ComplexityBpp Complexity ClassComputational Complexity Of LanguagesHierarchyHierarchy TheoremsPolynomial Time ComplexityReal NumbersTime Hierarchy TheoremsWorst-case Complexity
We show a hierarchy for probabilistic time with one bit of advice, specifically we show that for all real numbers 1 /spl les/ /spl alpha/ /spl les/ /spl beta/, BPTIME(n/sup /spl alpha//)/l /spl sube/ BPTIME(n/sup /spl beta//)/l. This result builds on and improves an earlier hierarchy of Barak using O(log log n) bits of advice. We also show that for any constant d > 0, there is a language L computable on average in BPP but not on average in BPTIME (n/sup d/). We build on Barak's techniques by using a different translation argument and by a careful application of the fact that there is a PSPACE-complete problem L such that worst-case probabilistic algorithms for L take only slightly more time than average-case algorithms.
20
Micheál Jacob · Health Education Journal · 1989 · 3.1K citations · Full text
Algebraic methods for interactive proof systems
Carsten Lund, Lance Fortnow, Howard Karloff et al. · Journal of the ACM · 1992 · 702 citations · Full text
Adi Shamir · Journal of the ACM · 1992 · 657 citations · Full text
<i>P = BPP</i> if <i>E</i> requires exponential circuits
Russell Impagliazzo, Avi Wigderson · 1997 · 544 citations