Constructive Discrepancy Minimization with Hereditary L2 Guarantees

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

In discrepancy minimization problems, we are given a family of sets S =,S,A, with each Si E S a subset of some universe U =, un} of n elements. The goal is to find a coloring x : U {-1, +1} of the elements of U such that each set S E S is colored as evenly as possible. Two classic measures of discrepancy are Coo -discrepancy defined as disco, (S, x) := maxsEs E,,Es x(ui)I 2 and p2 -discrepancy defined as disc2 (S, x) := (1/ IS I,E,ses Vui)). Breakthrough work by Bansal [FOCS'10] gave a polynomial time algorithm, based on rounding an SDP, for finding a coloring x such that disc (S, x) = 0(1g n " herdisc,,(S)) where herdisc,,(S) is the hereditary Coo -discrepancy of S. We complement his work by giving a clean and simple 0((m n)n2) time algorithm for finding a coloring x such disc2(S, x) = 0( \/1g n " herdisc2(S)) where herdisc2(S) is the hereditary ?2 -discrepancy of S. Interestingly, our algorithm avoids solving an SDP and instead relies simply on computing eigendecompositions of matrices. To prove that our algorithm has the claimed guarantees, we also prove new inequalities relating both herdisc,, and herdisc2 to the eigenvalues of the incidence matrix corresponding to S. Our inequalities improve over previous work by Chazelle and Lvov [SCG'00] and by Matousek, Nikolov and Talwar [SODA'15+SCG'15]. We believe these inequalities are of independent interest as powerful tools for proving hereditary discrepancy lower bounds. Finally, we also implement our algorithm and show that it far outperforms random sampling of colorings in practice. Moreover, the algorithm finishes in a reasonable amount of time on matrices of sizes up to 10000 x 10000.

Original languageEnglish
Title of host publication36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
EditorsRolf Niedermeier, Christophe Paul
Number of pages13
Place of publicationDagstuhl
PublisherSchloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH
Publication year2019
Article number48
ISBN (print)978-3-95977-100-9
Publication statusPublished - 2019
Event36th International Symposium on Theoretical Aspects of Computer Science - Berlin, Germany
Duration: 13 Mar 201916 Mar 2019


Conference36th International Symposium on Theoretical Aspects of Computer Science
SeriesLeibniz International Proceedings in Informatics

    Research areas

  • BOUNDS, Combinatorics, Computational Geometry, Discrepancy, Hereditary Discrepancy

See relations at Aarhus University Citationformats

ID: 170314477