(De)randomized construction of small sample spaces in NC

DOI10.1006/JCSS.1997.1532MaRDI QIDQ1384529zbMATH OpenOpenAlexFDO

Authors David R. Karger, Daphne Koller

Publication date 4 August 1998

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jcss.1997.1532

zbMATH Keywords

hypergraphsexpectation constraintsindependence constraints

Mathematics Subject Classification ID

Recommendations

• Constructing Small Sample Spaces Satisfying Given Constraints
• The probabilistic method yields deterministic parallel algorithms
• Improved algorithms via approximations of probability distributions
• Deterministic parallel algorithms for bilinear objective functions

Cites work

• scientific article; zbMATH DE number 4152425 (Why is no real title available?)
• scientific article; zbMATH DE number 1256678 (Why is no real title available?)
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• A parallel approximation algorithm for positive linear programming
• Approximating probability distributions using small sample spaces
• Constructing a perfect matching is in random NC
• Constructing small sample spaces satisfying given constraints
• Matching is as easy as matrix inversion
• On a combinatorial game
• On a set of almost deterministic k-independent random variables
• On construction of \(k\)-wise independent random variables
• Pseudorandom generators for space-bounded computation
• Simulating (log ^c n )-wise independence in NC
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• The probabilistic method yields deterministic parallel algorithms
• Using fast matrix multiplication to find basic solutions

Cited in

(3)

• Improved algorithms via approximations of probability distributions
• Constructing Small Sample Spaces Satisfying Given Constraints
• Improved algorithms via approximations of probability distributions (extended abstract)

This page was built for publication: (De)randomized construction of small sample spaces in \(\mathcal{NC}\)

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