Vi uppvisar ett starkt samband mellan omslagstider av grafer, Gaussiska processer, och Talagrands teori om majoriserande åtgärder. I synnerhet visar vi att omslagstiden för någon graf G är likvärdig, upp till universella konstanter, med kvadraten på det förväntade maximum av Gaussiska fria fältet på G, skalas av antalet kanter i G. Detta gör att vi kan lösa ett antal öppna frågor. Vi ger en deterministisk polynom-tid algoritm som beräknar omslaget tid till inom en O(1) faktor för alla grafer, svarar på en fråga om Aldous och Fill (1994). Vi löser också positivt de filt tid gissningar av Winkler och Zuckerman (1996), visar att för alla grafer, filten och täcktider är inom en O(1) faktor. Den bästa tidigare approximationen faktor för båda dessa problem var O((log log n) 2 ) för n-vertex grafer, på grund av Kahn, Kim, Lovász, och Vu (2000).
Mer nyligen, ett genombrott gjordes av Ding, Lee och Peres REF varigenom täcka tid gavs (upp till en konstant faktor) i termer av Gaussian fri fältet.
Cover times, blanket times, and majorizing measures
{'venue': "STOC '11", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}