The probabilistic method yields deterministic parallel algorithms
From MaRDI portal
Publication:1342858
DOI10.1016/S0022-0000(05)80069-8zbMath0824.68047MaRDI QIDQ1342858
Moni Naor, 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 (20)
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
This page was built for publication: The probabilistic method yields deterministic parallel algorithms
