A polynomial time approximation scheme for computing the supremum of Gaussian processes

DOI10.1214/13-AAP997zbMath1323.60056arXiv1202.4970MaRDI QIDQ2341621

Raghu Meka

Publication date: 27 April 2015

Published in: The Annals of Applied Probability (Search for Journal in Brave)

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

zbMATH Keywords

random walksGaussian processesderandomizationcover time\(\varepsilon\)-nets

Mathematics Subject Classification ID

Gaussian processes (60G15) Combinatorial probability (60C05) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (2)

Simple and efficient pseudorandom generators from gaussian processes ⋮ On the Cover Time of Dense Graphs

Cites Work

• Cover times, blanket times, and majorizing measures
• Asymptotics of cover times via Gaussian free fields: bounded-degree graphs and general trees
• Multiple cover time
• Algorithmic derandomization via complexity theory
• Unimodality and Dominance For Symmetric Random Vectors
• The Generic Chaining
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A polynomial time approximation scheme for computing the supremum of Gaussian processes