(De)randomized construction of small sample spaces in \(\mathcal{NC}\)

DOI10.1006/jcss.1997.1532zbMath0897.68043OpenAlexW2094449803MaRDI QIDQ1384529

Daphne Koller, David R. Karger

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

Cites Work

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