The probabilistic method yields deterministic parallel algorithms
From MaRDI portal
Publication:1342858
DOI10.1016/S0022-0000(05)80069-8zbMATH Open0824.68047MaRDI QIDQ1342858FDOQ1342858
Authors: Moni Naor, Joseph (Seffi) Naor, Rajeev Motwani 
Publication date: 24 October 1995
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Recommendations
- scientific article; zbMATH DE number 1304350
- An efficient parallel algorithm for random sampling
- Probabilistic Parallel Algorithms for Sorting and Selection
- Publication:4942231
- On Synchronous Parallel Computations with Independent Probabilistic Choice
- scientific article; zbMATH DE number 5198953
- An embarrassingly parallel method for large-scale stochastic programs
- Probabilistic analysis of a parallel algorithm for finding maximal independent sets
- Correctness and determinism of parallel Monte Carlo processes
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Distributed algorithms (68W15)
Cites Work
- Title not available (Why is that?)
- \(\epsilon\)-nets and simplex range queries
- On the ratio of optimal integral and fractional covers
- New applications of random sampling in computational geometry
- Small-Bias Probability Spaces: Efficient Constructions and Applications
- The NP-Completeness of Edge-Coloring
- Title not available (Why is that?)
- A deterministic view of random sampling and its use in geometry
- Balancing vectors in the max norm
- Six Standard Deviations Suffice
- 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
- A fast parallel algorithm for the maximal independent set problem
- Efficient parallel algorithms for edge coloring problems
- Matching is as easy as matrix inversion
- NP completeness of finding the chromatic index of regular graphs
- A fast parallel algorithm to compute the rank of a matrix over an arbitrary field
- Title not available (Why is that?)
- Probabilistic construction of deterministic algorithms: approximating packing integer programs
- A Randomized Algorithm for Closest-Point Queries
- ``Integer-making theorems
- An Efficient Algorithm for Colouring the Edges of a Graph With Δ + 1 Colours
- Simulating (log c n )-wise independence in NC
- The complexity of parallel search
- A fast parallel algorithm for routing in permutation networks
- Balanced two-colorings of finite sets in the cube
- Balancing families of sets
- Title not available (Why is that?)
- Derandomization through approximation, an NC algorithm for minimum cuts
Cited In (22)
- (De)randomized construction of small sample spaces in \(\mathcal{NC}\)
- Tight approximations for resource constrained scheduling and bin packing
- Improved algorithms via approximations of probability distributions
- Derandomizing local distributed algorithms under bandwidth restrictions
- A parallel algorithm for the complexity of \(O(\log^ 2 n)\) for the set balancing problem
- Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions
- Deterministic Massively Parallel Connectivity
- Finding a vector orthogonal to roughly half a collection of vectors
- Derandomized Construction of Combinatorial Batch Codes
- Title not available (Why is that?)
- Uniform generation of NP-witnesses using an NP-oracle
- Weighted fractional and integral \(k\)-matching in hypergraphs
- Randomized OBDD-based graph algorithms
- Title not available (Why is that?)
- MODp-tests, almost independence and small probability spaces
- On the parallel approximability of a subclass of quadratic programming.
- Very fast parallel algorithms for approximate edge coloring
- Deterministic parallel algorithms for bilinear objective functions
- On construction of \(k\)-wise independent random variables
- Small Sample Spaces Cannot Fool Low Degree Polynomials
- Rosenthal type inequalities for random variables
- Improved parallel approximation of a class of integer programming problems
This page was built for publication: The probabilistic method yields deterministic parallel algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1342858)
