We show that several discrepancy-like problems can be solved in NC nearly a
chieving the discrepancies guaranteed by a probabilistic analysis and achie
vable sequentially. For example, we describe an NC algorithm that given a s
et system (X, S), where X is a ground set and S subset of or equal to 2(X),
computes a set R subset of or equal to X so that for each S is an element
of S the discrepancy parallel toR boolean AND S\ - \(R) over bar boolean AN
D S parallel to is O(root \S\log\S\). Whereas previous NC algorithms could
only achieve discrepancies O(root \S\(1+epsilon) log\S\) with epsilon > 0,
ours matches the probabilistic bound within a multiplicative factor 1 + o(1
). Other problems whose NC solution we improve are lattice approximation, E
-approximations of range spaces with constant VC-exponent, sampling in geom
etric configuration spaces, approximation of integer linear programs, and e
dge coloring of graphs.