Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR05-042 | 6th May 2005 00:00

Linear Advice for Randomized Logarithmic Space

RSS-Feed




Revision #1
Authors: Lance Fortnow, Adam Klivans
Accepted on: 6th May 2005 00:00
Downloads: 1229
Keywords: 


Abstract:

We show that RL is contained in L/O(n), i.e., any language computable in randomized logarithmic space can be computed in deterministic logarithmic space with a linear amount of non-uniform advice. To prove our result we show how to take an ultra-low space walk on the Gabber-Galil expander graph due to Gutfreund and Viola.


Paper:

TR05-042 | 15th April 2005 00:00

Linear Advice for Randomized Logarithmic Space





TR05-042
Authors: Lance Fortnow, Adam Klivans
Publication: 15th April 2005 14:38
Downloads: 1265
Keywords: 


Abstract:

We show that RL is contained in L/O(n), i.e., any language computable
in randomized logarithmic space can be computed in deterministic
logarithmic space with a linear amount of non-uniform advice. To
prove our result we show how to take an ultra-low space walk on
the Gabber-Galil expander graph.



ISSN 1433-8092 | Imprint