Algorithmic aspects of combinatorial discrepancy

Research output: Chapter in Book/Report/Conference proceedingChapterAcademic

Abstract

This chapter describes some recent results in combinatorial discrepancy theory motivated by designing efficient polynomial time algorithms for finding low discrepancy colorings. Until recently, the best known results for several combinatorial discrepancy problems were based on counting arguments, most notably the entropy method, and were widely believed to be non-algorithmic. We describe some algorithms based on semidefinite programming that can achieve many of these bounds. Interestingly, the new connections between semidefinite optimization and discrepancy have lead to several new structural results in discrepancy itself, such as tightness of the so-called determinant lower bound and improved bounds on the discrepancy of union of set systems. We will also see a surprising new algorithmic proof of Spencer’s celebrated six standard deviations result due to Lovett and Meka, that does not rely on any semidefinite programming or counting argument.
Original languageEnglish
Title of host publicationA Panorama of Discrepancy Theory
EditorsW. Chen, A. Srivastav, G. Travaglini
Place of PublicationCham
PublisherSpringer
Chapter6
Pages425-457
ISBN (Print)978-3-319-04695-2
DOIs
Publication statusPublished - 2014

Publication series

NameLecture Notes in Mathematics
Volume2107
ISSN (Print)0075-8434

Fingerprint

Dive into the research topics of 'Algorithmic aspects of combinatorial discrepancy'. Together they form a unique fingerprint.

Cite this