BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/723
DTSTAMP:20230914T125935Z
SUMMARY:Codes\, Lower Bounds\, and Phase Transitions in the Symmetric Rende
zvous Problem
DESCRIPTION:Speaker: Tom Hayes (University of New Mexico\nDepartment of Com
puter Science\nAlbuquerque\, NM 87131\nUnited States of America\n )\n\nAb
stract: \nIn the rendezvous problem\, two parties with different labelings
of the vertices of a complete graph are trying to meet at some vertex at
the same time. It is well-known that if the parties have predetermined rol
es\, then the strategy where one of them waits at one vertex\, while the o
ther visits all n vertices in random order is optimal\, taking at most n s
teps and averaging about . Anderson and Weber (J. Appl. Prob. 1990\, pp. 8
39–851) considered the symmetric rendezvous problem\, where both parties
must use the same randomized strategy. They analyzed strategies where the
parties repeatedly play the optimal asymmetric strategy\, determining the
ir role independently each time by a biased coin-flip. By tuning the bias\
, Anderson and Weber achieved an expected meeting time of about \, which t
hey conjectured to be asymptotically optimal.\nWe change perspective sligh
tly: instead of minimizing the expected meeting time\, we seek to maximize
the probability of meeting within a specified time T. The Anderson-Weber
strategy\, which fails with constant probability when \, is not asymptotic
ally optimal for large T in this setting. Specifically\, we exhibit a symm
etric strategy that succeeds with probability in steps. This is tight: f
or any \, any symmetric strategy with fails with constant probability. Ou
r strategy uses a new combinatorial object that we dub a “rendezvous cod
e\,” which may be of independent interest.\nWhen \, we show that the pro
bability of meeting within T steps is indeed asymptotically maximized by t
he Anderson-Weber strategy. Our results imply new lower bounds\, showing t
hat the best symmetric strategy takes at least steps in expectation. We a
lso present some partial results for the symmetric rendezvous problem on o
ther vertex-transitive graphs. © 2016 Wiley Periodicals\, Inc. Random Str
uct. Alg.\, 49\, 742–765\, 2016.\n
URL:https://www.tcs.tifr.res.in/web/events/723
DTSTART;TZID=Asia/Kolkata:20161115T160000
DTEND;TZID=Asia/Kolkata:20161115T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR