We show that several discrepancy-like problems can be solved in NC2 nearly achieving the discrepancies guaranteed by a probabilistic analysis and achievable sequentially. For example, given a set system (X, S), where X is a ground set and S ⊑ 2 X , a set R ⊑ X can be computed in NC2 so that, for each S ε S, the discrepancy $$\left\| {R \cap S\left| - \right|\bar R \cap S} \right\|$$ is $$O\left( {\sqrt {\left| S \right|\log \left| S \right|} } \right)$$ . Whereas previous NC algorithms could only achieve $$O\left( {\sqrt {\left| S \right|^{1 + e} \log \left| S \right|} } \right)$$ , ours matches the probabilistic bound achieved sequentially within a multiplicative factor 1 + o(1). Other problems whose NC solution we improve are lattice approximation, ε-approximations of range spaces of bounded VC-exponent, sampling in geometric configuration spaces, approximation of integer linear programs, and edge coloring of graphs.