Constructive discrepancy minimization with hereditary L2 guarantees

DOI10.4230/LIPICS.STACS.2019.48MaRDI QIDQ5090499FDOQ5090499

Authors: Kasper Green Larsen 

Publication date: 18 July 2022

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

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

zbMATH Keywords

combinatoricscomputational geometrydiscrepancyhereditary discrepancy

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

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

Cited In (2)

• Constructive Discrepancy Minimization for Convex Sets
• A simplified disproof of Beck’s three permutations conjecture and an application to root-mean-squared discrepancy

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)