(De)randomized construction of small sample spaces in \(\mathcal{NC}\)
type: Item
instance of: scholarly article
title: (De)randomized construction of small sample spaces in \(\mathcal{NC}\)
zbMATH Open document ID: 0897.68043
author: David R. Karger
author: Daphne Koller
published in: Journal of Computer and System Sciences
publication date: 1998-08-04T00:00:00Z
Mathematics Subject Classification ID: 68Q05
zbMATH DE Number: 1140553
zbMATH Keywords: expectation constraints
zbMATH Keywords: independence constraints
zbMATH Keywords: hypergraphs
MaRDI profile type: Publication
full work available at URL: jcss.1997.1532
OpenAlex ID: W2094449803
cites work: A fast and simple randomized parallel algorithm for the maximal independent set problem
cites work: Approximating probability distributions using small sample spaces
cites work: Q4230365
cites work: Using fast matrix multiplication to find basic solutions
cites work: Simulating (log c n )-wise independence in NC
cites work: On a combinatorial game
cites work: On a set of almost deterministic k-independent random variables
cites work: Constructing small sample spaces satisfying given constraints
cites work: On construction of \(k\)-wise independent random variables
cites work: Constructing a perfect matching is in random NC
cites work: A parallel approximation algorithm for positive linear programming
cites work: A Simple Parallel Algorithm for the Maximal Independent Set Problem
cites work: The probabilistic method yields deterministic parallel algorithms
cites work: Matching is as easy as matrix inversion
cites work: Pseudorandom generators for space-bounded computation
cites work: Small-Bias Probability Spaces: Efficient Constructions and Applications
cites work: Q3481743
DOI: 10.1006/JCSS.1997.1532
description: scientific article; zbMATH DE number 1140553