zbMATH — the first resource for mathematics

From logarithmic advice to single-bit advice. (English) Zbl 1343.68080
Goldreich, Oded (ed.), Studies in complexity and cryptography. Miscellanea on the interplay between randomness and computation. In collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, Tali Kaufman, Leonid Levin, Noam Nisan, Dana Ron, Madhu Sudan, Luca Trevisan, Salil Vadhan, Avi Wigderson, David Zuckerman. Berlin: Springer (ISBN 978-3-642-22669-4/pbk). Lecture Notes in Computer Science 6650, 109-113 (2011).
Summary: Building on B. Barak’s work [Lect. Notes Comput. Sci. 2483, 194–208 (2002; Zbl 1028.68058)], L. Fortnow and R. Santhanam [“Hierarchy theorems for probabilistic polynomial time”, in: Proceedings of the 45th annual IEEE symposium on foundations of computer science, FOCS 2004. Los Alamitos, CA: IEEE Computer Society. 316–324 (2004, doi:10.1109/FOCS.2004.33)] 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 a single-bit advice. In this note, we make this technique explicit, by introducing an adequate translation lemma.
For the entire collection see [Zbl 1220.68005].

68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
Full Text: DOI
[1] Barak, B.: A Probabilistic-Time Hierarchy Theorem for Slightly Non-uniform Algorithms. In: Rolim, J.D.P., Vadhan, S.P. (eds.) RANDOM 2002. LNCS, vol. 2483, pp. 194–208. Springer, Heidelberg (2002) · Zbl 1028.68058
[2] Fortnow, L., Santhanam, R.: Hierarchy theorems for probabilistic polynomial time. In: 45th FOCS, pp. 316–324 (2004)
[3] van Melkebeek, D., Pervyshev, K.: A Generic Time Hierarchy for Semantic Models with One Bit of Advice. Computational Complexity 16, 139–179 (2007) · Zbl 1173.68023
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.