License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2022.101
URN: urn:nbn:de:0030-drops-156975
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15697/
Liu, Yang P. ;
Sah, Ashwin ;
Sawhney, Mehtaab
A Gaussian Fixed Point Random Walk
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.
BibTeX - Entry
@InProceedings{liu_et_al:LIPIcs.ITCS.2022.101,
author = {Liu, Yang P. and Sah, Ashwin and Sawhney, Mehtaab},
title = {{A Gaussian Fixed Point Random Walk}},
booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
pages = {101:1--101:10},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-217-4},
ISSN = {1868-8969},
year = {2022},
volume = {215},
editor = {Braverman, Mark},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15697},
URN = {urn:nbn:de:0030-drops-156975},
doi = {10.4230/LIPIcs.ITCS.2022.101},
annote = {Keywords: Discrepancy, Partial Coloring}
}
Keywords: |
|
Discrepancy, Partial Coloring |
Collection: |
|
13th Innovations in Theoretical Computer Science Conference (ITCS 2022) |
Issue Date: |
|
2022 |
Date of publication: |
|
25.01.2022 |