Simulating (log c n )-wise independence in NC
From MaRDI portal
Publication:4302863
DOI10.1145/115234.115347zbMath0799.68094OpenAlexW2158219072MaRDI QIDQ4302863
Publication date: 21 August 1994
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/115234.115347
parallelismedge coloringgraph algorithmscombinatorial algorithmshypergraph coloringprobabilistic computationcomputations on discrete structuresremoving randomnesspolylogarithmic independencerandomized NC algorithmsset discrepancy problem
Graph theory (including graph drawing) in computer science (68R10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
MODp-tests, almost independence and small probability spaces ⋮ The probabilistic method yields deterministic parallel algorithms ⋮ Weighted fractional and integral \(k\)-matching in hypergraphs ⋮ Unnamed Item ⋮ Tight approximations for resource constrained scheduling and bin packing ⋮ 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 ⋮ Near-optimal distributed edge coloring ⋮ Deterministic parallel algorithms for bilinear objective functions ⋮ Rosenthal type inequalities for random variables ⋮ Improved parallel approximation of a class of integer programming problems ⋮ Very fast parallel algorithms for approximate edge coloring ⋮ Near-optimal, distributed edge colouring via the nibble method ⋮ Improved algorithms via approximations of probability distributions ⋮ Uniform generation of NP-witnesses using an NP-oracle ⋮ Parallel approximation schemes for a class of planar and near planar combinatorial optimization problems. ⋮ Removing randomness in parallel computation without a processor penalty
