Document Open Access Logo

A Gaussian Fixed Point Random Walk

Authors Yang P. Liu, Ashwin Sah, Mehtaab Sawhney

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2022.101.pdf
  • Filesize: 0.68 MB
  • 10 pages

Document Identifiers

Author Details

Yang P. Liu
  • Department of Mathematics, Stanford University, Stanford, CA, USA
Ashwin Sah
  • Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA, USA
Mehtaab Sawhney
  • Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA, USA

Funding

  • Liu, Yang P.: Yang P. Liu was supported by the Department of Defense (DoD) through the National Defense Science and Engineering Graduate Fellowship (NDSEG) Program.
  • Sah, Ashwin: Sah was supported by NSF Graduate Research Fellowship Program DGE-1745302.
  • Sawhney, Mehtaab: Sawhney was supported by NSF Graduate Research Fellowship Program DGE-1745302.

Acknowledgements

The authors thank Ryan Alweiss, Arun Jambulapati, Allen Liu, and Mark Sellke for earlier discussions on this topic. Furthermore we thank Ghaith Hiary for discussions regarding computing theta series. Finally we thank Nikhil Bansal for comments on the manuscript.

Cite AsGet BibTex

Yang P. Liu, Ashwin Sah, and Mehtaab Sawhney. A Gaussian Fixed Point Random Walk. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 101:1-101:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ITCS.2022.101

Abstract

In this note, we design a discrete random walk on the real line which takes steps 0,±1 (and one with steps in {±1,2}) where at least 96% of the signs are ±1 in expectation, and which has 𝒩(0,1) as a stationary distribution. As an immediate corollary, we obtain an online version of Banaszczyk’s discrepancy result for partial colorings and ±1,2 signings. Additionally, we recover linear time algorithms for logarithmic bounds for the Komlós conjecture in an oblivious online setting.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Probabilistic algorithms
Keywords
  • Discrepancy
  • Partial Coloring

Metrics

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

Related Versions

References

  1. Ryan Alweiss, Yang P Liu, and Mehtaab Sawhney. Discrepancy minimization via a self-balancing walk. arXiv:2006.14009. Google Scholar
  2. George E. Andrews. A simple proof of Jacobi’s triple product identity. Proc. Amer. Math. Soc., 16:333-334, 1965. URL: https://doi.org/10.2307/2033875.
  3. Juhan Aru, Bhargav Narayanan, Alex Scott, and Ramarathnam Venkatesan. Balancing sums of random vectors. Discrete Anal., pages Paper No. 4, 17, 2018. URL: https://doi.org/10.19086/da.3108.
  4. Wojciech Banaszczyk. Balancing vectors and Gaussian measures of n-dimensional convex bodies. Random Structures & Algorithms, 12(4):351-360, 1998. Google Scholar
  5. Nikhil Bansal. Constructive algorithms for discrepancy minimization. In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA, pages 3-10. IEEE Computer Society, 2010. URL: https://doi.org/10.1109/FOCS.2010.7.
  6. Nikhil Bansal, Daniel Dadush, and Shashwat Garg. An algorithm for Komlós conjecture matching Banaszczyk’s bound. In Irit Dinur, editor, IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 788-799. IEEE Computer Society, 2016. URL: https://doi.org/10.1109/FOCS.2016.89.
  7. Nikhil Bansal, Daniel Dadush, Shashwat Garg, and Shachar Lovett. The gram-schmidt walk: a cure for the Banaszczyk blues. In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 587-597. ACM, 2018. URL: https://doi.org/10.1145/3188745.3188850.
  8. 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
  9. Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, and Makrand Sinha. Online discrepancy minimization for stochastic arrivals. In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 2842-2861. SIAM, 2021. URL: https://doi.org/10.1137/1.9781611976465.169.
  10. Nikhil Bansal, Haotian Jiang, Sahil Singla, and Makrand Sinha. Online vector balancing and geometric discrepancy. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, pages 1139-1152, New York, NY, USA, 2020. Association for Computing Machinery. URL: https://doi.org/10.1145/3357713.3384280.
  11. Nikhil Bansal and Joel H Spencer. On-Line Balancing of Random Inputs. arXiv:1903.06898. Google Scholar
  12. Daniel Dadush. URL: https://homepages.cwi.nl/~dadush/workshop/discrepancy-ip/open-problems.html.
  13. Daniel Dadush, Aleksandar Nikolov, Kunal Talwar, and Nicole Tomczak-Jaegermann. Balancing vectors in any norm. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 1-10. IEEE, 2018. Google Scholar
  14. Ronen Eldan and Mohit Singh. Efficient algorithms for discrepancy minimization in convex sets. Random Struct. Algorithms, 53(2):289-307, 2018. URL: https://doi.org/10.1002/rsa.20763.
  15. Shachar Lovett and Raghu Meka. Constructive discrepancy minimization by walking on the edges. SIAM J. Comput., 44(5):1573-1582, 2015. URL: https://doi.org/10.1137/130929400.
  16. Thomas Rothvoss. Constructive discrepancy minimization for convex sets. SIAM Journal on Computing, 46(1):224-234, 2017. Google Scholar
  17. Joel Spencer. Six standard deviations suffice. Trans. Amer. Math. Soc., 289(2):679-706, 1985. URL: https://doi.org/10.2307/2000258.
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 Imprint Privacy Contact