A Fast Derandomization Scheme and Its Applications

DOI10.1137/S0097539790192702MaRDI QIDQ4875445zbMATH OpenOpenAlexFDO

Authors Yijie Han

Publication date 5 June 1996

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539790192702

zbMATH Keywords

graph algorithmsmaximal independent setparallel algorithmstime complexityvertex-coloringmaximal matchingfast derandomization scheme

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parallel algorithms in computer science (68W10) Distributed algorithms (68W15)

Recommendations

• scientific article; zbMATH DE number 177547
• A new general derandomization method
• On a Fast Version of a Pseudorandom Generator
• scientific article; zbMATH DE number 3919629
• Fast pseudorandomness for independence and load balancing (extended abstract)
• Some results on derandomization
• scientific article; zbMATH DE number 1962815
• Simple and fast derandomization from very hard functions: eliminating randomness at almost no cost
• A note to the paper ``On a fast version of a pseudorandom generator

Cited in

(11)

• An optimal parallel algorithm for general maximal matchings is as easy as for bipartite graphs
• Improved algorithms via approximations of probability distributions
• Derandomizing local distributed algorithms under bandwidth restrictions
• Fast Computation of Large Distributions and Its Cryptographic Applications
• Simple, Deterministic, Constant-Round Coloring in Congested Clique and MPC
• SPRING: Fast Pseudorandom Functions from Rounded Ring Products
• A fast method for complete randomization of messages.
• Amplification and Derandomization without Slowdown
• scientific article; zbMATH DE number 177547 (Why is no real title available?)
• Fast Time-Recursive Block Correlators for Pseudorandom Sequences
• Deterministic parallel algorithms for bilinear objective functions

This page was built for publication: A Fast Derandomization Scheme and Its Applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4875445)