research-article

Tight hardness results for minimizing discrepancy

Authors:

Moses Charikar,

Alantha Newman,

Aleksandar NikolovAuthors Info & Claims

SODA '11: Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithms

Pages 1607 - 1614

Published: 23 January 2011 Publication History

Get Access

Abstract

In the Discrepancy problem, we are given M sets {S₁,..., S_M} on N elements. Our goal is to find an assignment χ of {−1, + 1} values to elements, so as to minimize the maximum discrepancy max_j | Σ_iεSj χ(i)|. Recently, Bansal gave an efficient algorithm for achieving O(√N) discrepancy for any set system where M = O(N) [Ban10], giving a constructive version of Spencer's proof that the discrepancy of any set system is at most O(√N) for this range of M [Spe85].

We show that from the perspective of computational efficiency, these results are tight for general set systems where M = O(N). Specifically, we show that it is NP-hard to distinguish between such set systems with discrepancy zero and those with discrepancy Ω(√N). This means that even if the optimal solution has discrepancy zero, we cannot hope to efficiently find a coloring with discrepancy o(√N). We also consider the hardness of the Discrepancy problem on sets with bounded shatter function, and show that the upper bounds due to Matoušek [Mat95] are tight for these sets systems as well.

The hardness results in both settings are obtained from a common framework: we compose a family of high discrepancy set systems with set systems for which it is NP-hard to distinguish instances with discrepancy zero from instances in which a large number of the sets (i.e. constant fraction of the sets) have non-zero discrepancy. Our composition amplifies this zero versus non-zero gap.

References

[1]

{Ale90} R. Alexander. Geometric methods in the study of irregularities of distribution. Combinatorica, 10(2):115--136, 1990.

Google Scholar

[2]

{Ban10} Nikhil Bansal. Constructive algorithms for discrepancy minimization. CoRR, abs/1002.2259, 2010.

Google Scholar

[3]

{BS96} J. Beck and V. T. Sós. Discrepancy theory. In Handbook of combinatorics (vol. 2), page 1446. MIT Press, 1996.

Digital Library

Google Scholar

[4]

{CGW05} Moses Charikar, Venkatesan Guruswami, and Anthony Wirth. Clustering with qualitative information. J. Comput. Syst. Sci., 71(3):360--383, 2005.

Digital Library

Google Scholar

[5]

{Cha91} Bernard Chazelle. The Discrepancy Method. Cambridge University Press, 1991.

Google Scholar

[6]

{CMS95} B. Chazelle, J. Matoušek, and M. Sharir. An elementary approach to lower bounds in geometric discrepancy. Discrete and Computational Geometry, 13(1):363--381, 1995.

Google Scholar

[7]

{Gur03} Venkatesan Guruswami. Inapproximability results for set splitting and satisfiability problems with no mixed clauses. Algorithmica, 38(3):451--469, 2003.

Google Scholar

[8]

{Mat95} J. Matoušek. Tight upper bounds for the discrepancy of half-spaces. Discrete and Computational Geometry, 13(1):593--601, 1995.

Google Scholar

[9]

{Mat10} J. Matousek. Geometric Discrepancy: An Illustrated Guide. Springer Verlag, 2010.

Google Scholar

[10]

{Spe85} Joel Spencer. Six standard deviations suffice. Trans. Amer. Math. Soc., 289:679--706, 1985.

Google Scholar

Cited By

View all

Bansal NDadush DGarg SLovett SDiakonikolas IKempe DHenzinger M(2018)The Gram-Schmidt walk: a cure for the Banaszczyk bluesProceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3188745.3188850(587-597)Online publication date: 20-Jun-2018
https://dl.acm.org/doi/10.1145/3188745.3188850
Bansal NNagarajan V(2016)Approximation-Friendly Discrepancy RoundingProceedings of the 18th International Conference on Integer Programming and Combinatorial Optimization - Volume 968210.1007/978-3-319-33461-5_31(375-386)Online publication date: 1-Jun-2016
https://dl.acm.org/doi/10.1007/978-3-319-33461-5_31
Guruswami VLee EIndyk P(2015)Strong inapproximability results on balanced rainbow-colorable hypergraphsProceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms10.5555/2722129.2722185(822-836)Online publication date: 4-Jan-2015
https://dl.acm.org/doi/10.5555/2722129.2722185
Show More Cited By

Tight hardness results for minimizing discrepancy

Recommendations

Impossibility results on weakly black-box hardness amplification
FCT'07: Proceedings of the 16th international conference on Fundamentals of Computation Theory

We study the task of hardness amplification which transforms a hard function into a harder one. It is known that in a high complexity class such as exponential time, one can convert worst-case hardness into average-case hardness. However, in a lower ...
Free Bits, PCPs, and Nonapproximability---Towards Tight Results

This paper continues the investigation of the connection between probabilistically checkable proofs (PCPs) and the approximability of NP -optimization problems. The emphasis is on proving tight nonapproximability results via consideration of measures ...
Unexpected hardness results for Kolmogorov complexity under uniform reductions
STOC 2020: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing

Hardness of computing the Kolmogorov complexity of a given string is closely tied to a security proof of hitting set generators, and thus understanding hardness of Kolmogorov complexity is one of the central questions in complexity theory. In this paper,...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SODA '11: Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithms

January 2011

1785 pages

Program Chair:
Dana Randall
Georgia Institute of Technology

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 23 January 2011

Check for updates

Qualifiers

Research-article

Conference

SODA '11

Sponsor:

SIGACT

SODA '11: 22nd ACM-SIAM Symposium on Discrete Algorithms

January 23 - 25, 2011

California, San Francisco

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
83
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Bansal NDadush DGarg SLovett SDiakonikolas IKempe DHenzinger M(2018)The Gram-Schmidt walk: a cure for the Banaszczyk bluesProceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3188745.3188850(587-597)Online publication date: 20-Jun-2018
https://dl.acm.org/doi/10.1145/3188745.3188850
Bansal NNagarajan V(2016)Approximation-Friendly Discrepancy RoundingProceedings of the 18th International Conference on Integer Programming and Combinatorial Optimization - Volume 968210.1007/978-3-319-33461-5_31(375-386)Online publication date: 1-Jun-2016
https://dl.acm.org/doi/10.1007/978-3-319-33461-5_31
Guruswami VLee EIndyk P(2015)Strong inapproximability results on balanced rainbow-colorable hypergraphsProceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms10.5555/2722129.2722185(822-836)Online publication date: 4-Jan-2015
https://dl.acm.org/doi/10.5555/2722129.2722185
Nikolov ATalwar KIndyk P(2015)Approximating hereditary discrepancy via small width ellipsoidsProceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms10.5555/2722129.2722153(324-336)Online publication date: 4-Jan-2015
https://dl.acm.org/doi/10.5555/2722129.2722153
Bansal NCharikar MKrishnaswamy RLi SChekuri C(2014)Better algorithms and hardness for broadcast scheduling via a discrepancy approachProceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms10.5555/2634074.2634079(55-71)Online publication date: 5-Jan-2014
https://dl.acm.org/doi/10.5555/2634074.2634079
Chandrasekaran KVempala SNaor M(2014)Integer feasibility of random polytopesProceedings of the 5th conference on Innovations in theoretical computer science10.1145/2554797.2554838(449-458)Online publication date: 12-Jan-2014
https://dl.acm.org/doi/10.1145/2554797.2554838
Petrović SStasi D(2014)Toric algebra of hypergraphsJournal of Algebraic Combinatorics: An International Journal10.1007/s10801-013-0444-y39:1(187-208)Online publication date: 1-Feb-2014
https://dl.acm.org/doi/10.1007/s10801-013-0444-y
Eisenbrand FPálvölgyi DRothvoß T(2013)Bin Packing via Discrepancy of PermutationsACM Transactions on Algorithms10.1145/2483699.24837049:3(1-15)Online publication date: 1-Jun-2013
https://dl.acm.org/doi/10.1145/2483699.2483704
Agarwal PCormode GHuang ZPhillips JWei ZYi KLenzerini MBenedikt M(2012)Mergeable summariesProceedings of the 31st ACM SIGMOD-SIGACT-SIGAI symposium on Principles of Database Systems10.1145/2213556.2213562(23-34)Online publication date: 21-May-2012
https://dl.acm.org/doi/10.1145/2213556.2213562
Joshi SKommaraji RPhillips JVenkatasubramanian SHurtado Fvan Kreveld M(2011)Comparing distributions and shapes using the kernel distanceProceedings of the twenty-seventh annual symposium on Computational geometry10.1145/1998196.1998204(47-56)Online publication date: 13-Jun-2011
https://dl.acm.org/doi/10.1145/1998196.1998204

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Recommendations

Impossibility results on weakly black-box hardness amplification

Free Bits, PCPs, and Nonapproximability---Towards Tight Results

Unexpected hardness results for Kolmogorov complexity under uniform reductions