From logarithmic advice to single-bit advice
Webpage for a paper by Goldreich, Sudan and Trevisan
Abstract
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 a single-bit advice.
In this note, we make this technique explicit,
by introducing an adequate translation lemma.
Material available on-line
Back to
either Oded Goldreich's homepage.
or general list of papers.