(De)randomized construction of small sample spaces in NC
From MaRDI portal
Publication:1384529
DOI10.1006/JCSS.1997.1532zbMATH Open0897.68043OpenAlexW2094449803MaRDI QIDQ1384529FDOQ1384529
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
Recommendations
Cites Work
- Small-Bias Probability Spaces: Efficient Constructions and Applications
- On a combinatorial game
- Constructing a perfect matching is in random NC
- A Simple Parallel Algorithm for the Maximal Independent Set Problem
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- Matching is as easy as matrix inversion
- On a set of almost deterministic k-independent random variables
- A parallel approximation algorithm for positive linear programming
- Title not available (Why is that?)
- Pseudorandom generators for space-bounded computation
- Using fast matrix multiplication to find basic solutions
- The probabilistic method yields deterministic parallel algorithms
- Simulating (log c n )-wise independence in NC
- On construction of \(k\)-wise independent random variables
- Constructing small sample spaces satisfying given constraints
- Approximating probability distributions using small sample spaces
- Title not available (Why is that?)
Cited In (3)
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)
