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

fast derandomization schemegraph algorithmsmaximal independent setmaximal matchingparallel algorithmstime complexityvertex-coloring

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) 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

(12)

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