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](/_next/image?url=https%3A%2F%2Fcontent.preview.ems.press%2Fassets%2Fpublic%2Fimages%2Fbooks%2Fcover-279.png&w=3840&q=90)
Download Chapter PDF
This book chapter is published open access.
Abstract
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.