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
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

If no CC-License is given, pleas contact the the creator, if you want to use thre resource other than only read it.