Improved Algorithms via Approximations of Probability Distributions

Simple item page
dc.contributor.authorSuresh Charien_US
dc.contributor.authorPankaj Rohatgien_US
dc.contributor.authorAravind Srinivasanen_US
dc.date.accessioned2004-10-21T14:28:52Zen_US
dc.date.accessioned2017-01-23T07:00:19Z
dc.date.available2004-10-21T14:28:52Zen_US
dc.date.available2017-01-23T07:00:19Z
dc.date.issued1996-10-01T00:00:00Zen_US
dc.description.abstractWe present two techniques for approximating probability distributions. The first is a simple method for constructing the small-bias probability spaces introduced by Naor and Naor. We show how to efficiently combine this construction with the method of conditional probabilities to yield improved NC algorithms for many problems such as set discrepancy, finding large cuts in graphs, finding large acyclic subgraphs etc. The second is a construction of small probability spaces approximating general independent distributions, which is of smaller size than the constructions of Even, Goldreich, Luby, Nisan and Velickovic. Such approximations are useful, e.g., for the derandomization of certain randomized algorithms.en_US
dc.format.extent317913 bytesen_US
dc.format.extent263684 bytesen_US
dc.format.mimetypeapplication/pdfen_US
dc.format.mimetypeapplication/postscripten_US
dc.identifier.urihttps://dl.comp.nus.edu.sg/xmlui/handle/1900.100/1351en_US
dc.language.isoenen_US
dc.relation.ispartofseriesTR10/96en_US
dc.titleImproved Algorithms via Approximations of Probability Distributionsen_US
dc.typeTechnical Reporten_US
Files
Original bundle
Now showing 1 - 2 of 2
Thumbnail Image
Name:
report.ps
Size:
257.5 KB
Format:
Postscript Files
Description:
Download
Thumbnail Image
Name:
report.pdf
Size:
310.46 KB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
1.52 KB
Format:
Plain Text
Description:
Download
Collections
Technical Reports