Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review

**Constructive Discrepancy Minimization with Hereditary L2 Guarantees.** / Larsen, Kasper Green.

Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review

Larsen, KG 2019, Constructive Discrepancy Minimization with Hereditary L2 Guarantees. in R Niedermeier & C Paul (eds), *36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019).*, 48, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Dagstuhl, Leibniz International Proceedings in Informatics, vol. 126, 36th International Symposium on Theoretical Aspects of Computer Science , Berlin, Germany, 13/03/2019. https://doi.org/10.4230/LIPIcs.STACS.2019.48

Larsen, K. G. (2019). Constructive Discrepancy Minimization with Hereditary L2 Guarantees. In R. Niedermeier, & C. Paul (Eds.), *36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019) *[48] Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH. Leibniz International Proceedings in Informatics, Vol.. 126 https://doi.org/10.4230/LIPIcs.STACS.2019.48

Larsen KG. 2019. Constructive Discrepancy Minimization with Hereditary L2 Guarantees. Niedermeier R, Paul C, editors. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH. Article 48. (Leibniz International Proceedings in Informatics, Vol. 126). https://doi.org/10.4230/LIPIcs.STACS.2019.48

Larsen, Kasper Green "Constructive Discrepancy Minimization with Hereditary L2 Guarantees". and Niedermeier, Rolf Paul, Christophe (editors). *36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019).* Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH. (Leibniz International Proceedings in Informatics, Vol. 126). 2019. https://doi.org/10.4230/LIPIcs.STACS.2019.48

Larsen KG. Constructive Discrepancy Minimization with Hereditary L2 Guarantees. In Niedermeier R, Paul C, editors, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH. 2019. 48. (Leibniz International Proceedings in Informatics, Vol. 126). https://doi.org/10.4230/LIPIcs.STACS.2019.48

Larsen, Kasper Green. / **Constructive Discrepancy Minimization with Hereditary L2 Guarantees**. 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). editor / Rolf Niedermeier ; Christophe Paul. Dagstuhl : Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, 2019. (Leibniz International Proceedings in Informatics, Vol. 126).

@inproceedings{e7bf912adc494f948adb3985a4c5d31c,

title = "Constructive Discrepancy Minimization with Hereditary L2 Guarantees",

abstract = "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.",

keywords = "BOUNDS, Combinatorics, Computational Geometry, Discrepancy, Hereditary Discrepancy",

author = "Larsen, {Kasper Green}",

year = "2019",

doi = "10.4230/LIPIcs.STACS.2019.48",

language = "English",

isbn = "978-3-95977-100-9",

series = "Leibniz International Proceedings in Informatics",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH",

editor = "Niedermeier, {Rolf } and Paul, {Christophe }",

booktitle = "36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)",

note = "null ; Conference date: 13-03-2019 Through 16-03-2019",

}

TY - GEN

T1 - Constructive Discrepancy Minimization with Hereditary L2 Guarantees

AU - Larsen, Kasper Green

PY - 2019

Y1 - 2019

N2 - 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.

AB - 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.

KW - BOUNDS

KW - Combinatorics

KW - Computational Geometry

KW - Discrepancy

KW - Hereditary Discrepancy

U2 - 10.4230/LIPIcs.STACS.2019.48

DO - 10.4230/LIPIcs.STACS.2019.48

M3 - Article in proceedings

SN - 978-3-95977-100-9

T3 - Leibniz International Proceedings in Informatics

BT - 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)

A2 - Niedermeier, Rolf

A2 - Paul, Christophe

PB - Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH

CY - Dagstuhl

Y2 - 13 March 2019 through 16 March 2019

ER -