.
We show that several discrepancy-like problems can be solved in NC nearly achieving the discrepancies guaranteed by a probabilistic analysis and achievable sequentially. For example, we describe an NC algorithm that given a set system (X, S) , where X is a ground set and S⊆2 X , computes a set R⊆X so that for each S∈ S the discrepancy ||R S|-|R-∩S|| is $ O(\sqrt{\smash{\mbox{$|S| \log | {\cal S}|$}}}) O(\sqrt{\smash{\mbox{$|S|^{1+\varepsilon} \log |{\cal S}|$}}}) $ with ɛ>0 , ours matches the probabilistic bound within a multiplicative factor 1+o(1) . Other problems whose NC solution we improve are lattice approximation, ɛ -approximations of range spaces with constant VC-exponent, sampling in geometric configuration spaces, approximation of integer linear programs, and edge coloring of graphs.