2013/11/25 by Aleksandar Nikolov, Kunal Talwar, Nikolov, Aleksandar +1 · 1 citation
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Mathematical Approximation and Integration #cs.DS
paper · pdf · doi:10.48550/arxiv.1311.6204
openalex publication_date 2013/11/25 · arxiv created 2014/07/23 · arxiv updated 2014/07/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The Discrepancy of a hypergraph is the minimum attainable value, over two-colorings of its vertices, of the maximum absolute imbalance of any hyperedge. The Hereditary Discrepancy of a hypergraph, defined as the maximum discrepancy of a restriction of the hypergraph to a subset of its vertices, is a measure of its complexity. Lovasz, Spencer and Vesztergombi (1986) related the natural extension of this quantity to matrices to rounding algorithms for linear programs, and gave a determinant based lower bound on the hereditary discrepancy. Matousek (2011) showed that this bound is tight up to a polylogarithmic factor, leaving open the question of actually computing this bound. Recent work by Nikolov, Talwar and Zhang (2013) showed a polynomial time O(log3 n)-approximation to hereditary discrepancy, as a by-product of their work in differential privacy. In this paper, we give a direct simple O(log3/2 n)-approximation algorithm for this problem. We show that up to this approximation factor, the hereditary discrepancy of a matrix A is characterized by the optimal value of simple geometric convex program that seeks to minimize the largest ℓ∞ norm of any point in a ellipsoid containing the columns of A. This characterization promises to be a useful tool in discrepancy theory.