The probabilistic method yields deterministic parallel algorithms
From MaRDI portal
Publication:1342858
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
Cites work
- scientific article; zbMATH DE number 4152425 (Why is no real title available?)
- scientific article; zbMATH DE number 4155888 (Why is no real title available?)
- scientific article; zbMATH DE number 3577144 (Why is no real title available?)
- scientific article; zbMATH DE number 3255204 (Why is no real title available?)
- A Randomized Algorithm for Closest-Point Queries
- A Simple Parallel Algorithm for the Maximal Independent Set Problem
- A deterministic view of random sampling and its use in geometry
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- A fast parallel algorithm for routing in permutation networks
- A fast parallel algorithm for the maximal independent set problem
- A fast parallel algorithm to compute the rank of a matrix over an arbitrary field
- An Efficient Algorithm for Colouring the Edges of a Graph With Δ + 1 Colours
- Balanced two-colorings of finite sets in the cube
- Balancing families of sets
- Balancing vectors in the max norm
- Constructing a perfect matching is in random NC
- Derandomization through approximation, an NC algorithm for minimum cuts
- Efficient parallel algorithms for edge coloring problems
- Matching is as easy as matrix inversion
- NP completeness of finding the chromatic index of regular graphs
- New applications of random sampling in computational geometry
- On a combinatorial game
- On the ratio of optimal integral and fractional covers
- Probabilistic construction of deterministic algorithms: approximating packing integer programs
- Simulating (log c n )-wise independence in NC
- Six Standard Deviations Suffice
- Small-Bias Probability Spaces: Efficient Constructions and Applications
- The NP-Completeness of Edge-Coloring
- The complexity of parallel search
- \(\epsilon\)-nets and simplex range queries
- ``Integer-making theorems
Cited in
(22)- scientific article; zbMATH DE number 2102778 (Why is no real title available?)
- (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
- Uniform generation of NP-witnesses using an NP-oracle
- On construction of \(k\)-wise independent random variables
- Rosenthal type inequalities for random variables
- Improved parallel approximation of a class of integer programming problems
- Improved algorithms via approximations of probability distributions (extended abstract)
- Lower bounds on black-box reductions of hitting to density estimation
- Deterministic parallel algorithms for bilinear objective functions
- Finding a vector orthogonal to roughly half a collection of vectors
- Randomized OBDD-based graph algorithms
- Derandomized construction of combinatorial batch codes
- Small Sample Spaces Cannot Fool Low Degree Polynomials
- Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions
- A parallel algorithm for the complexity of \(O(\log^ 2 n)\) for the set balancing problem
- Derandomizing local distributed algorithms under bandwidth restrictions
- \(\mathrm{MOD}_p\)-tests, almost independence and small probability spaces (extended abstract)
- On the parallel approximability of a subclass of quadratic programming.
- Very fast parallel algorithms for approximate edge coloring
- Weighted fractional and integral \(k\)-matching in hypergraphs
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)
