The probabilistic method yields deterministic parallel algorithms
From MaRDI portal
Publication:1342858
DOI10.1016/S0022-0000(05)80069-8zbMath0824.68047MaRDI QIDQ1342858
Moni Naor, Rajeev Motwani, Joseph (Seffi) Naor
Publication date: 24 October 1995
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Distributed algorithms (68W15)
Related Items
Randomized OBDD-based graph algorithms, MODp-tests, almost independence and small probability spaces, Weighted fractional and integral \(k\)-matching in hypergraphs, Unnamed Item, Tight approximations for resource constrained scheduling and bin packing, On construction of \(k\)-wise independent random variables, Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions, (De)randomized construction of small sample spaces in \(\mathcal{NC}\), Derandomized Construction of Combinatorial Batch Codes, Derandomizing local distributed algorithms under bandwidth restrictions, Deterministic Massively Parallel Connectivity, Small Sample Spaces Cannot Fool Low Degree Polynomials, Deterministic parallel algorithms for bilinear objective functions, Rosenthal type inequalities for random variables, Improved parallel approximation of a class of integer programming problems, Finding a vector orthogonal to roughly half a collection of vectors, Very fast parallel algorithms for approximate edge coloring, On the parallel approximability of a subclass of quadratic programming., Improved algorithms via approximations of probability distributions, Uniform generation of NP-witnesses using an NP-oracle
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A deterministic view of random sampling and its use in geometry
- Balancing vectors in the max norm
- \(\epsilon\)-nets and simplex range queries
- Matching is as easy as matrix inversion
- A fast parallel algorithm to compute the rank of a matrix over an arbitrary field
- Constructing a perfect matching is in random NC
- The complexity of parallel search
- Probabilistic construction of deterministic algorithms: approximating packing integer programs
- Balanced two-colorings of finite sets in the cube
- ``Integer-making theorems
- On the ratio of optimal integral and fractional covers
- Balancing families of sets
- New applications of random sampling in computational geometry
- Derandomization through approximation
- Small-Bias Probability Spaces: Efficient Constructions and Applications
- An Efficient Algorithm for Colouring the Edges of a Graph With Δ + 1 Colours
- Six Standard Deviations Suffice
- 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
- A Randomized Algorithm for Closest-Point Queries
- A fast parallel algorithm for routing in permutation networks
- The NP-Completeness of Edge-Coloring
- Simulating (log c n )-wise independence in NC
- NP completeness of finding the chromatic index of regular graphs
- On a combinatorial game
