45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04) Hierarchy Theorems for Probabilistic Polynomial Time Rome, Italy October 17-October 19 ISBN: 0-7695-2228-9
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/FOCS.2004.33
We show a hierarchy for probabilistic time with one bit of advice, specifically we show that for all real numbers 1 ≤ α < β, BPTIME(n^(α)/1 ⊊ BPTIME(n^(β)/1. This result builds on and improves an earlier hierarchy of Barak using 0(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^(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 probablistic algorithms for L take only slightly more time thane average-case algorithms.
Citation:
Lance Fortnow, Rahul Santhanam, "Hierarchy Theorems for Probabilistic Polynomial Time," focs, pp.316-324, 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), 2004 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb