Simulating (log(c) n)-wise Independence in NC

Abstract

We develop a general framework for removing randomness from randomized NC algorithms whose analysis uses only polyalgorithmic independence. Previously no techniques were known to determine those RNC algorithms depending on more than constant independence. One application of our 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 of our techniques, we provide an NC algorithm for the hypergraph coloring problem.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 01, 1989
Accession Number
ADA213974

Entities

People

  • Bonnie Berger
  • John Rompel

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • Energy and Power Technologies
  • Engineered Resilient Systems

DTIC Thesaurus Topics

  • Algebra
  • Algorithms
  • Availability
  • Classification
  • Computations
  • Computer Science
  • Computers
  • Information Processing
  • Information Systems
  • Iterations
  • Linear Algebra
  • Linearity
  • Military Research
  • Polynomials
  • Probability
  • Random Variables
  • Security

Fields of Study

  • Computer science

Readers

  • Computational Modeling and Simulation
  • Graph Algorithms and Convex Optimization.