Authors: Bertram-Kretzberg, Claudia
Lefmann, Hanno
Title: MOD_p-tests, Almost Independence and Small Probability Spaces
Language (ISO): en
Abstract: In this paper, we consider approximations of probability distributions over ZZ n p . We present an approach to estimate the quality of approximations of probability distributions towards the construction of small probability spaces. These are used to derandomize algorithms. In contrast to results by Even, Goldreich, Luby, Nisan and Velickovich [EGLNV], our methods are simple, and for reasonably small p, we get smaller sample spaces. Our considerations are motivated by a problem which was mentioned in recent work of Azar, Motwani and Naor [AMN], namely, how to construct in time polynomial in n a good approximation to the joint probability distribution of the random variables X1;X2; : : :;Xn where each Xi has values in f0; 1g and satises Xi = 0 with probability q and Xi = 1 with probability 1
URI: http://hdl.handle.net/2003/5312
http://dx.doi.org/10.17877/DE290R-5635
Issue Date: 1998-11-06
Provenance: Universität Dortmund
Appears in Collections:Sonderforschungsbereich (SFB) 531

Files in This Item:
File Description SizeFormat 
lefmann.pdfDNB230.56 kBAdobe PDFView/Open
lefmann.ps254.96 kBPostscriptView/Open


This item is protected by original copyright



All resources in the repository are protected by copyright.