Solving some discrepancy problems in NC

achieving the corresponding probabilistic bounds. For example, given a set
system (X,F), where X is a ground set and F is a subset of 2^X, a subset R
from X can be computed in NC^2 so that, for each S in F, the "discrepancy" :

| |R intersection S| - |(X-R) intersection S| |

is O(sqrt{|S| log|F|}). Previous NC algorithms could only achieve a bound
O(sqrt{|S|^{1+epsilon} log |F|}), while ours matches the probabilistic bound
achieved sequentially by the method of conditional probabilities within a
multiplicative factor 1+o(1). Other problems whose NC solution we improve are
lattice approximation, epsilon-approximations of range spaces of bounded
VC-dimension, sampling in geometric configuration spaces, and approximation of
integer linear programs.

Joint work with Sanjeev Mahajan and K.V. Subrahmanyam