Constructive Discrepancy Minimization for Convex Sets
From MaRDI portal
Abstract: A classical theorem of Spencer shows that any set system with n sets and n elements admits a coloring of discrepancy O(n^1/2). Recent exciting work of Bansal, Lovett and Meka shows that such colorings can be found in polynomial time. In fact, the Lovett-Meka algorithm finds a half integral point in any "large enough" polytope. However, their algorithm crucially relies on the facet structure and does not apply to general convex sets. We show that for any symmetric convex set K with measure at least exp(-n/500), the following algorithm finds a point y in K cap [-1,1]^n with Omega(n) coordinates in {-1,+1}: (1) take a random Gaussian vector x; (2) compute the point y in K cap [-1,1]^n that is closest to x. (3) return y. This provides another truly constructive proof of Spencer's theorem and the first constructive proof of a Theorem of Gluskin and Giannopoulos.
Recommendations
- Efficient algorithms for discrepancy minimization in convex sets
- Constructive discrepancy minimization with hereditary L2 guarantees
- Discrete convexity built on differences
- Convex sets in minimum-distance estimation
- scientific article; zbMATH DE number 3909024
- Optimal sets for a class of minimization problems with convex constraints
- Convergence of discrete approximations for constrained minimization
- Convex programming for disjunctive convex optimization
- Convex discrete optimization
- scientific article; zbMATH DE number 480244
Cites work
- ``Integer-making theorems
- Constructive discrepancy minimization by walking on the edges
- Efficient algorithms for discrepancy minimization in convex sets
- EXTREMAL PROPERTIES OF ORTHOGONAL PARALLELEPIPEDS AND THEIR APPLICATIONS TO THE GEOMETRY OF BANACH SPACES
- Geometric discrepancy. An illustrated guide
- scientific article; zbMATH DE number 1528185 (Why is no real title available?)
- scientific article; zbMATH DE number 1380581 (Why is no real title available?)
- scientific article; zbMATH DE number 6472647 (Why is no real title available?)
- scientific article; zbMATH DE number 3349081 (Why is no real title available?)
- Interlacing families. II: Mixed characteristic polynomials and the Kadison-Singer problem
- On Certain Inequalities for Normal Distributions and their Applications to Simultaneous Confidence Bounds
- On some vector balancing problems
- On the discrepancy of 3 permutations
- Probability in Banach spaces. Isoperimetry and processes
- Rectangular Confidence Regions for the Means of Multivariate Normal Distributions
- Roth's estimate of the discrepancy of integer sequences is nearly sharp
- Six Standard Deviations Suffice
- The ellipsoid method and its consequences in combinatorial optimization
Cited in
(19)- Gaussian discrepancy: a probabilistic relaxation of vector balancing
- Quantum discrepancy: a non-commutative version of combinatorial discrepancy
- Deterministic discrepancy minimization via the multiplicative weight update method
- Algorithmic pure states for the negative spherical perceptron
- Discrepancy without partial colorings
- Constructive discrepancy minimization by walking on the edges
- Efficient algorithms for discrepancy minimization in convex sets
- A greedy algorithm for quantizing neural networks
- The Gram-Schmidt walk: a cure for the Banaszczyk blues
- The discrepancy of random rectangular matrices
- Algorithmic obstructions in the random number partitioning problem
- Searching for (sharp) thresholds in random structures: where are we now?
- A spectral bound on hypergraph discrepancy
- Revisit the partial coloring method: prefix spencer and sampling
- An optimal sparsification lemma for low-crossing matchings and its applications to discrepancy and approximations
- Weaver's discrepancy for Gaussian random vectors
- Smoothed analysis of the Komlós conjecture: Rademacher noise
- Smoothed analysis with adaptive adversaries
- Discrepancy minimization via a self-balancing walk
This page was built for publication: Constructive Discrepancy Minimization for Convex Sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2968153)
