Document Open Access Logo

A Unified Approach to Discrepancy Minimization

Authors Nikhil Bansal, Aditi Laddha, Santosh Vempala

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2022.1.pdf
  • Filesize: 0.83 MB
  • 22 pages

Document Identifiers

Author Details

Nikhil Bansal
  • University of Michigan, Ann Arbor, MI, USA
Aditi Laddha
  • Georgia Tech, Atlanta, GA, USA
Santosh Vempala
  • Georgia Tech, Atlanta, GA, USA

Funding

  • Bansal, Nikhil: Supported in part by the NWO VICI grant 639.023.812.
  • Laddha, Aditi: Supported in part by NSF awards CCF-2007443 and CCF-2134105.
  • Vempala, Santosh: Supported in part by NSF awards CCF-2007443 and CCF-2134105.

Acknowledgements

We are grateful to Yin Tat Lee and Mohit Singh for helpful discussions.

Cite As Get BibTex

Nikhil Bansal, Aditi Laddha, and Santosh Vempala. A Unified Approach to Discrepancy Minimization. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 1:1-1:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2022.1

Abstract

We study a unified approach and algorithm for constructive discrepancy minimization based on a stochastic process. By varying the parameters of the process, one can recover various state-of-the-art results. We demonstrate the flexibility of the method by deriving a discrepancy bound for smoothed instances, which interpolates between known bounds for worst-case and random instances.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Discrepancy theory
  • smoothed analysis

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Dylan J Altschuler and Jonathan Niles-Weed. The discrepancy of random rectangular matrices. arXiv preprint, 2021. URL: http://arxiv.org/abs/2101.04036.
  2. Jean-Yves Audibert, Sébastien Bubeck, and Gábor Lugosi. Regret in online combinatorial optimization. Mathematics of Operations Research, 39(1):31-45, 2014. Google Scholar
  3. Wojciech Banaszczyk. Balancing vectors and gaussian measures of n-dimensional convex bodies. Random Structures & Algorithms, 12(4):351-360, 1998. Google Scholar
  4. Nikhil Bansal. Constructive algorithms for discrepancy minimization. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pages 3-10. IEEE, 2010. Google Scholar
  5. Nikhil Bansal, Daniel Dadush, and Shashwat Garg. An algorithm for Komlós conjecture matching Banaszczyk’s bound. SIAM Journal on Computing, 48(2):534-553, 2019. Google Scholar
  6. Nikhil Bansal, Daniel Dadush, Shashwat Garg, and Shachar Lovett. The Gram-Schmidt walk: A cure for the Banaszczyk blues. Theory Comput., 15:1-27, 2019. Google Scholar
  7. Nikhil Bansal and Shashwat Garg. Algorithmic discrepancy beyond partial coloring. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 914-926, 2017. Google Scholar
  8. Nikhil Bansal, Aditi Laddha, and Santosh S Vempala. A unified approach to discrepancy minimization. arXiv preprint, 2022. URL: http://arxiv.org/abs/2205.01023.
  9. Nikhil Bansal and Raghu Meka. On the discrepancy of random low degree set systems. Random Structures & Algorithms, 57(3):695-705, 2020. Google Scholar
  10. Nikhil Bansal and Joel Spencer. Deterministic discrepancy minimization. Algorithmica, 67(4):451-471, 2013. Google Scholar
  11. Nikhil Bansal and Joel H. Spencer. On-line balancing of random inputs. Random Struct. Algorithms, 57(4):879-891, 2020. Google Scholar
  12. Joshua Batson, Daniel A Spielman, and Nikhil Srivastava. Twice-ramanujan sparsifiers. SIAM Journal on Computing, 41(6):1704-1721, 2012. Google Scholar
  13. József Beck. Roth’s estimate of the discrepancy of integer sequences is nearly sharp. Combinatorica, 1(4):319-325, 1981. Google Scholar
  14. József Beck. Discrepancy theory. Handbook of combinatorics, pages 1405-1446, 1995. Google Scholar
  15. József Beck and Tibor Fiala. "Integer-making" theorems. Discrete Applied Mathematics, 3(1):1-8, 1981. Google Scholar
  16. Karthekeyan Chandrasekaran and Santosh S Vempala. Integer feasibility of random polytopes: random integer programs. In Proceedings of the 5th conference on Innovations in theoretical computer science, pages 449-458, 2014. Google Scholar
  17. Bernard Chazelle. The discrepancy method: randomness and complexity. Cambridge University Press, 2001. Google Scholar
  18. Ronen Eldan and Mohit Singh. Efficient algorithms for discrepancy minimization in convex sets. Random Struct. Algorithms, 53(2):289-307, 2018. Google Scholar
  19. Esther Ezra and Shachar Lovett. On the beck-fiala conjecture for random set systems. Random Structures & Algorithms, 54(4):665-675, 2019. Google Scholar
  20. Efim Davydovich Gluskin. Extremal properties of orthogonal parallelepipeds and their applications to the geometry of banach spaces. Mathematics of the USSR-Sbornik, 64(1):85, 1989. Google Scholar
  21. Nicholas Harvey, Roy Schwartz, and Mohit Singh. Discrepancy without partial colorings. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2014. Google Scholar
  22. Rebecca Hoberg and Thomas Rothvoss. A fourier-analytic approach for the discrepancy of random set systems. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2547-2556. SIAM, 2019. Google Scholar
  23. Yin Tat Lee and Mohit Singh. Personal communication, 2016. Google Scholar
  24. Yin Tat Lee and He Sun. Constructing linear-sized spectral sparsification in almost-linear time. In Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on, pages 250-269. IEEE, 2015. Google Scholar
  25. Yin Tat Lee and Santosh S Vempala. Stochastic localization+ stieltjes barrier= tight bound for log-sobolev. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 1122-1129, 2018. Google Scholar
  26. Avi Levy, Harishchandra Ramadas, and Thomas Rothvoss. Deterministic discrepancy minimization via the multiplicative weight update method. In International Conference on Integer Programming and Combinatorial Optimization, pages 380-391. Springer, 2017. Google Scholar
  27. Shachar Lovett and Raghu Meka. Constructive discrepancy minimization by walking on the edges. SIAM Journal on Computing, 44(5):1573-1582, 2015. Google Scholar
  28. Jiri Matousek. Geometric discrepancy: An illustrated guide, volume 18. Springer Science & Business Media, 1999. Google Scholar
  29. Jiri Matousek. Geometric discrepancy: An illustrated guide, volume 18. Springer, 2009. Google Scholar
  30. Jiri Matousek. The determinant bound for discrepancy is almost tight. Proceedings of the American Mathematical Society, 141:451-60, 2013. Google Scholar
  31. Jiri Matousek and Aleksandar Nikolov. Combinatorial discrepancy for boxes via the γ₂ norm. In 31st International Symposium on Computational Geometry, SoCG, volume 34, pages 1-15, 2015. Google Scholar
  32. Aditya Potukuchi. A spectral bound on hypergraph discrepancy. In 47th International Colloquium on Automata, Languages, and Programming, ICALP, pages 93:1-93:14, 2020. Google Scholar
  33. Thomas Rothvoss. Constructive discrepancy minimization for convex sets. SIAM Journal on Computing, 46(1):224-234, 2017. Google Scholar
  34. Joel Spencer. Six standard deviations suffice. Transactions of the American mathematical society, 289(2):679-706, 1985. Google Scholar
  35. Nikhil Srivastava, Roman Vershynin, et al. Covariance estimation for distributions with 2+eps moments. The Annals of Probability, 41(5):3081-3111, 2013. Google Scholar
  36. Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact