Scholarlink

In this paper, we improve the best known constant for the discrepancy formulated in the Komlós Conjecture. The result is based on an improvement of the sub-Gaussian bound for the random vector constructed in the Gram-Schmidt Random Walk algorithm. Moreover, we present detailed argument for the smoothed analysis of this random vector. The analysis concerns a modification of a given matrix in the conjecture by a Gaussian type perturbation. Our result improves on a recent paper in this direction Bansal et al. (Smoothed Analysis of the Komlós Conjecture (2022). arXiv:2204.11427).

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Some Remarks on the Gram-Schmidt Walk Algorithm and Consequences for the Komlós Conjecture

  • 会议论文

  • 发表日期：

    2026年

查看全文
  • Witold Bednorz,
  • Piotr Godlewski

摘要

In this paper, we improve the best known constant for the discrepancy formulated in the Komlós Conjecture. The result is based on an improvement of the sub-Gaussian bound for the random vector constructed in the Gram-Schmidt Random Walk algorithm. Moreover, we present detailed argument for the smoothed analysis of this random vector. The analysis concerns a modification of a given matrix in the conjecture by a Gaussian type perturbation. Our result improves on a recent paper in this direction Bansal et al. (Smoothed Analysis of the Komlós Conjecture (2022). arXiv:2204.11427).