Tighter bounds for the discrepancy of boxes and polytopes

DOI10.1112/S0025579317000250zbMATH Open1390.11096arXiv1701.05532OpenAlexW2963043279MaRDI QIDQ4604484FDOQ4604484

Authors: Aleksandar Nikolov 

Publication date: 26 February 2018

Published in: Mathematika (Search for Journal in Brave)

Abstract: Combinatorial discrepancy is a complexity measure of a collection of sets which quantifies how well the sets in the collection can be simultaneously balanced. More precisely, we are given an n-point set $P$, and a collection $mathcalF=F_1,\mathrm{...},F_m$ of subsets of $P$, and our goal is color $P$ with two colors, red and blue, so that the maximum over the $F_i$ of the absolute difference between the number of red elements and the number of blue elements (the discrepancy) is minimized. Combinatorial discrepancy has many applications in mathematics and computer science, including constructions of uniformly distributed point sets, and lower bounds for data structures and private data analysis algorithms. We investigate the combinatorial discrepancy of geometrically defined systems, in which $P$ is an n-point set in $d$-dimensional space ,and $mathcalF$ is the collection of subsets of $P$ induced by dilations and translations of a fixed convex polytope $B$. Such set systems include systems of sets induced by axis-aligned boxes, whose discrepancy is the subject of the well known Tusnady problem. We prove new discrepancy upper and lower bounds for such set systems by extending the approach based on factorization norms previously used by the author and Matousek. We improve the best known upper bound for the Tusnady problem by a logarithmic factor, using a result of Banaszczyk on signed series of vectors. We extend this improvement to any arbitrary convex polytope $B$ by using a decomposition due to Matousek. Using Fourier analytic techniques, we also prove a nearly matching discrepancy lower bound for sets induced by any fixed bounded polytope $B$ satisfying a certain technical condition. We also outline applications of our results to geometric discrepancy, data structure lower bounds, and differential privacy.

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

Recommendations

• On the discrepancy for boxes and polytopes
• Bracketing numbers for axis-parallel boxes and applications to geometric discrepancy
• Tight upper bounds for the discrepancy of half-spaces
• On the discrepancy of combinatorial rectangles
• scientific article; zbMATH DE number 881163

zbMATH Keywords

data structuresdifferential privacycombinatorial discrepancygeometric discrepancyfactorization norm

Mathematics Subject Classification ID

Irregularities of distribution, discrepancy (11K38) (n)-dimensional polytopes (52B11) Fourier series and coefficients in several variables (42B05)

Cites Work

• On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals
• Title not available (Why is that?)
• Theory of Cryptography
• The Complexity of Maintaining an Array and Computing Its Partial Sums
• Irregularities of distribution, VII
• On irregularities of distribution
• Geometric discrepancy. An illustrated guide
• MONTE CARLO METHODS FOR SOLVING MULTIVARIABLE PROBLEMS
• Average decay of Fourier transforms and integer points in polyhedra
• Irregularities of distributions with respect to polytopes
• Complexity measures of sign matrices
• On the small ball inequality in all dimensions
• Title not available (Why is that?)
• Tight hardness results for minimizing discrepancy
• On series of signed vectors and their rearrangements
• Remark concerning integer sequences
• On range searching in the group model and combinatorial discrepancy
• On the discrepancy for boxes and polytopes
• The algorithmic foundations of differential privacy
• Title not available (Why is that?)
• How well does the finite Fourier transform approximate the Fourier transform?
• Balanced two-colorings of finite sets in the square. I
• Note on irregularities of distribution
• Combinatorial discrepancy for boxes via the \(\gamma_2\) norm
• Discrepancy and the error in integration
• Tusnády's problem, the transference principle, and non-uniform QMC sampling
• Principles of a new method in the study of irregularities of distribution
• An algorithm for Komlós conjecture matching Banaszczyk's bound
• Factorization norms and hereditary discrepancy
• Approximating hereditary discrepancy via small width ellipsoids
• Algorithmic discrepancy beyond partial coloring

Cited In (15)

• On the discrepancy for boxes and polytopes
• Box-inequalities for quadratic assignment polytopes
• On the Computational Complexity of Linear Discrepancy
• The discrepancy of boxes in higher dimension
• Combinatorial discrepancy for boxes via the \(\gamma_2\) norm
• Lower bounds for boxicity
• Discrepancy theory and related algorithms
• Bracketing numbers for axis-parallel boxes and applications to geometric discrepancy
• On the Discrepancy for Cartesian Products
• On the gap between hereditary discrepancy and the determinant lower bound
• Factorization norms and hereditary discrepancy
• Quantum discrepancy: a non-commutative version of combinatorial discrepancy
• On the \(L_2\)-discrepancy for anchored boxes
• Title not available (Why is that?)
• Some of Jiří Matoušek's contributions to combinatorial discrepancy theory

This page was built for publication: Tighter bounds for the discrepancy of boxes and polytopes

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