Tighter bounds for the discrepancy of boxes and polytopes

DOI10.1112/S0025579317000250MaRDI QIDQ4604484zbMATH OpenOpenAlexFDO

Authors Aleksandar Nikolov

Publication date 26 February 2018

Published in Mathematika (Search for Journal in Brave)

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

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)

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.

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

Cites work

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

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
• scientific article; zbMATH DE number 7559157 (Why is no real title available?)
• 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)