Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR04-093 | 9th November 2004 00:00

From logarithmic advice to single-bit advice

RSS-Feed




TR04-093
Authors: Oded Goldreich, Madhu Sudan, Luca Trevisan
Publication: 9th November 2004 11:06
Downloads: 1759
Keywords: 


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.



ISSN 1433-8092 | Imprint