loading...
Derandomization of Probabilistic Auxiliary Pushdown Automata Classes
Prague, Czech Republic July 16-July 20
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/CCC.2006.1621st Annual IEEE Conference on Compu ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
H. Venkateswaran, Georgia Institute of Technology, USA
We extend Nisan?s breakthrough derandomization result that BP_HL \subseteq SC^2 [11] to bounded error probabilistic complexity classes based on auxiliary pushdown automata. In particular, we show that any logarithmic space, polynomial time two-sided bounded-error probabilistic auxiliary pushdown automaton (the corresponding complexity class is denoted by BP_HLOGCFL) can be simulated by an SC^2 machine. This derandomization result improves a classical result by Cook [7] that LOGDCFL \sybseteq SC^2 since LOGDCFL is contained in BP_HLOGCFL. We also present a simple circuit-based proof that BP_HLOGCFL is in NC^2.
Citation:
H. Venkateswaran, "Derandomization of Probabilistic Auxiliary Pushdown Automata Classes," ccc, pp.355-370, 21st Annual IEEE Conference on Computational Complexity (CCC'06), 2006
Usage of this product signifies your acceptance of the Terms of Use.