Constructive discrepancy minimization with hereditary L2 guarantees

DOI10.4230/LIPICS.STACS.2019.48MaRDI QIDQ5090499zbMATH OpenFDO

Authors Kasper Green Larsen

Publication date 18 July 2022

Full work available at URL https://arxiv.org/abs/1711.02860

zbMATH Keywords

combinatoricscomputational geometrydiscrepancyhereditary discrepancy

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Deterministic discrepancy minimization
• The determinant bound for discrepancy is almost tight
• Constructive discrepancy minimization by walking on the edges
• Approximating hereditary discrepancy via small width ellipsoids
• Efficient algorithms for discrepancy minimization in convex sets

Cites work

• ``Integer-making theorems
• A trace bound for the hereditary discrepancy
• Algorithmic discrepancy beyond partial coloring
• An algorithm for Komlós conjecture matching Banaszczyk's bound
• Combinatorial discrepancy for boxes via the \(\gamma_2\) norm
• Constructive discrepancy minimization by walking on the edges
• Deterministic discrepancy minimization via the multiplicative weight update method
• Discrepancy of set-systems and matrices
• Factorization norms and hereditary discrepancy
• Geometric discrepancy. An illustrated guide
• Geometric methods in the study of irregularities of distribution
• scientific article; zbMATH DE number 1460605 (Why is no real title available?)
• scientific article; zbMATH DE number 1528185 (Why is no real title available?)
• scientific article; zbMATH DE number 1380581 (Why is no real title available?)
• On range searching in the group model and combinatorial discrepancy
• Six Standard Deviations Suffice
• The Gram-Schmidt walk: a cure for the Banaszczyk blues
• Tight hardness results for minimizing discrepancy
• Tight upper bounds for the discrepancy of half-spaces
• Tighter bounds for the discrepancy of boxes and polytopes

Cited in

(4)

• Constructive Discrepancy Minimization for Convex Sets
• A simplified disproof of Beck’s three permutations conjecture and an application to root-mean-squared discrepancy
• Constructive Discrepancy Minimization with Hereditary L2 Guarantees
• The discrepancy of shortest paths

This page was built for publication: Constructive discrepancy minimization with hereditary L2 guarantees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5090499)