Three‐wise independent random walks can be slightly unbounded

DOI10.1002/rsa.21075zbMath1523.60082arXiv1807.04910OpenAlexW4205263045MaRDI QIDQ6052485

Shyam Narayanan

Publication date: 17 October 2023

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1807.04910

zbMATH Keywords

momentsrandom walk\(k\)-wise independence

Mathematics Subject Classification ID

Sums of independent random variables; random walks (60G50)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation of the distribution of the supremum of a centered random walk. Application to the local score
• Universal classes of hash functions
• The space complexity of approximating the frequency moments
• Bounds for the torsion of elliptic curves over number fields
• Random walks with \(k\)-wise independent increments
• The sizes of compact subsets of Hilbert space and continuity of Gaussian processes
• Optimal Streaming and Tracking Distinct Elements with High Probability
• Stochastic Processes for Physicists
• Linear Probing with Constant Independence
• The best constants in the Khintchine inequality
• On the k -Independence Required by Linear Probing and Minwise Independence
• Beating CountSketch for heavy hitters in insertion streams
• Frontmatter, Table of Contents, Preface, Organization, External Reviewers, List of Authors
• On the best constant in Marcinkiewicz-Zygmund inequality