Discrepancy theory and related algorithms

  • Nikhil Bansal

    Computer Science and Engineering (CSE), University of Michigan, Ann Arbor, MI 48109-2121, USA
Discrepancy theory and related algorithms cover
Download Chapter PDF

This book chapter is published open access.


We survey some classical results and techniques in discrepancy theory, and the recent developments in making these techniques algorithmic. The previous methods were typically based on non-constructive approaches such as the pigeonhole principle, and counting arguments involving exponentially many objects and volume of convex bodies. The recent algorithmic methods are based on an interesting interplay of methods from discrete Brownian motion, convex geometry, optimization, and matrix analysis, and their study has led to interesting new connections and progress in both discrepancy and algorithm design.