Constructing Small Sample Spaces Satisfying Given Constraints

DOI10.1137/S0895480192228140MaRDI QIDQ4296520zbMATH OpenFDO

Authors Daphne Koller, Nimrod Megiddo

Publication date 10 October 1994

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0895480192228140

zbMATH Keywords

derandomizationdiscrete probability distributionhypergraphindependence constraintslinear programming

Mathematics Subject Classification ID

Probability distributions: general theory (60E05) Discrete mathematics in relation to computer science (68R99)

Recommendations

• Approximating probability distributions using small sample spaces
• (De)randomized construction of small sample spaces in \(\mathcal{NC}\)
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• Estimating dimension from small samples
• Small sample approximations for spacing statistics

Cited in

(9)

• (De)randomized construction of small sample spaces in \(\mathcal{NC}\)
• Finding mixed strategies with small supports in extensive form games
• Derandomized constructions of \(k\)-wise (almost) independent permutations
• Probabilistic existence of regular combinatorial structures
• The complexity of LSH feasibility
• On sampling from multivariate distributions
• scientific article; zbMATH DE number 1563190 (Why is no real title available?)
• \(H\)-wise independence
• Tight Probability Bounds with Pairwise Independence

This page was built for publication: Constructing Small Sample Spaces Satisfying Given Constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4296520)