Please help transcribe this video using our simple transcription tool. You need to be logged in to do so.

## Description

Given a set system (V,S), V=[n] and S={S_1,ldots,S_m}, the minimum discrepancy problem is to find a 2-coloring X:V -> {-1,+1}, such that each set is colored as evenly as possible, i.e. find X to minimize max_{j in [m]} |sum_{i in S_j} X(i)|. In this paper we give the first polynomial time algorithms for discrepancy minimization, that achieve bounds similar to those known existentially using the so-called Entropy Method. We also give a first approximation-like result for discrepancy. Specifically we give efficient randomized algorithms to: 1. Construct an \$O(sqrt{n})\$ discrepancy coloring for general sets systems when \$m=O(n)\$, matching the celebrated result of Spencer up to constant factors. Previously, no algorithmic guarantee better than the random coloring bound, i.e. O((n log n)^{1/2}), was known. More generally, for \$mgeq n\$, we obtain a discrepancy bound of O(n^{1/2} log (2m/n)). 2. Construct a coloring with discrepancy \$O(t^{1/2} log n)\$, if each element lies in at most \$t\$ sets. This matches the (non-constructive) result of Srinivasan cite{Sr}. 3. Construct a coloring with discrepancy O(lambdalog(nm)), where lambda is the hereditary discrepancy of the set system. In particular, this implies a logarithmic approximation for hereditary discrepancy. The main idea in our algorithms is to gradually produce a coloring by solving a sequence of semidefinite programs, while using the entropy method to guide the choice of the semidefinite program at each stage.