Simulating (log/sup c/n)-wise independence in NC
- 1 January 1989
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
A general framework is developed for removing randomness from randomized NC algorithms whose analysis uses only polylogarithmic independence. Previously, no techniques were known to determinize those RNC algorithms depending on more than constant independence. One application of the techniques is an NC algorithm for the set discrepancy problem, which can be used to obtain many other NC algorithms, including a better NC edge-coloring algorithm. As another application an NC algorithm for the hypergraph coloring problem is provided.<>Keywords
This publication has 12 references indexed in Scilit:
- Efficient dispersal of information for security, load balancing, and fault toleranceJournal of the ACM, 1989
- Efficient NC algorithms for set cover with applications to learning and geometryPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1989
- The probabilistic method yields deterministic parallel algorithmsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1989
- Probabilistic construction of deterministic algorithms: Approximating packing integer programsJournal of Computer and System Sciences, 1988
- The influence of variables on Boolean functionsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1988
- Removing randomness in parallel computation without a processor penaltyPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1988
- Efficient parallel algorithms for edge coloring problemsJournal of Algorithms, 1987
- A fast parallel algorithm for the maximal independent set problemJournal of the ACM, 1985
- The bit extraction problem or t-resilient functionsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1985
- On coloring graphs to maximize the proportion of multicolored k-edgesJournal of Combinatorial Theory, 1968