Moser, Philippe
(2002)
ZPP is Hard Unless RP is Small.
Electronic Colloquium on Computational Complexity (15).
ISSN 14338092
Abstract
We use Lutz's resource bounded measure theory to prove that, either RP is
small, or ZPP is hard. More precisely, we prove that if RP has not pmeasure zero, then
EXP equals ZPP on infinitely many input lengths, i.e. there are infinitely many input lengths on which ZPP is hard. Second we prove that if NP has not pmeasure zero, then derandomization of AM is possible on infinitely many input length, i.e. there are infinitely many input lengths such that NP = AM. Finally we prove easiness versus randomness tradeoffs for classes in the polynomial time hierarchy.
We show that it appears to every strong adversary that either,
every Ʃᴾᵢ algorithm can be simulated infinitely often by a subexponential
conondeterministic time algorithm, having oracle access to Ʃᴾᵢ 2 , or BP Ʃᴾᵢ = Ʃᴾᵢ .
Item Type: 
Article

Keywords: 
derandomization; ZPP; RP; 
Academic Unit: 
Faculty of Science and Engineering > Computer Science 
Item ID: 
8248 
Depositing User: 
Philippe Moser

Date Deposited: 
29 May 2017 14:33 
Journal or Publication Title: 
Electronic Colloquium on Computational Complexity 
Publisher: 
Weizmann Institute of Science 
Refereed: 
No 
URI: 

Repository Staff Only(login required)

Item control page 
Downloads per month over past year