loading...
On Derandomizing Probabilistic Sublinear-Time Algorithms
San Diego, California June 13-March 16
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/CCC.2007.19Twenty-Second Annual IEEE Conference ...
 This Article 
 
Buy PURCHASE ARTICLE: $19
PDF
HTML
Buy IEEE Xplore Subscribers
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
ASCII Text
x 
 
Marius Zimand, "On Derandomizing Probabilistic Sublinear-Time Algorithms," Computational Complexity, Annual IEEE Conference on, pp. 1-9, Twenty-Second Annual IEEE Conference on Computational Complexity (CCC'07), 2007.
 
 
BibTex
x
 
@article{ 10.1109/CCC.2007.19,
author = {Marius Zimand},
title = {On Derandomizing Probabilistic Sublinear-Time Algorithms},
journal ={Computational Complexity, Annual IEEE Conference on},
volume = {0},
year = {2007},
issn = {1093-0159},
pages = {1-9},
doi = {http://doi.ieeecomputersociety.org/10.1109/CCC.2007.19},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Computational Complexity, Annual IEEE Conference on
TI - On Derandomizing Probabilistic Sublinear-Time Algorithms
SN - 1093-0159
SP1
EP9
A1 - Marius Zimand,
PY - 2007
KW - null
VL - 0
JA - Computational Complexity, Annual IEEE Conference on
ER -
 
Marius Zimand, Towson University, USA
There exists a positive constant \alpha \le 1 such that for any function T(n) \leqslant n^{\alpha} and for any problem L \in BPTIME(T(n)), there exists a deterministic algorithm running in poly(T(n)) time which decides L, except for at most a 2^{-\Omega (T(n) log T(n)) fraction of inputs of length n.
Citation:
Marius Zimand, "On Derandomizing Probabilistic Sublinear-Time Algorithms," ccc, pp.1-9, Twenty-Second Annual IEEE Conference on Computational Complexity (CCC'07), 2007
Usage of this product signifies your acceptance of the Terms of Use.