Moser, Philippe (2002) ZPP is Hard Unless RP is Small. Electronic Colloquium on Computational Complexity (15). ISSN 1433-8092

Preview

Download (207kB) | Preview

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 p-measure 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 p-measure 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 co-nondeterministic 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:	https://eccc.weizmann.ac.il/static/collo...
Use Licence:	This item is available under a Creative Commons Attribution Non Commercial Share Alike Licence (CC BY-NC-SA). Details of this licence are available here

Repository Staff Only(login required)

Item control page

Downloads

Origin of downloads