Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > VINAYAK KUMAR:
All reports by Author Vinayak Kumar:

TR20-151 | 8th October 2020
Venkatesan Guruswami, Vinayak Kumar

Pseudobinomiality of the Sticky Random Walk

Random walks on expanders are a central and versatile tool in pseudorandomness. If an arbitrary half of the vertices of an expander graph are marked, known Chernoff bounds for expander walks imply that the number $M$ of marked vertices visited in a long $n$-step random walk strongly concentrates around the ... more >>>




ISSN 1433-8092 | Imprint