BEGIN:VCALENDAR
VERSION:2.0
PRODID:talks.ox.ac.uk
BEGIN:VEVENT
SUMMARY:Finding cliques using few probes - Miklós Rácz (Princeton Unive
rsity)
DTSTART;VALUE=DATE-TIME:20181029T120000Z
DTEND;VALUE=DATE-TIME:20181029T130000Z
UID:https://talks.ox.ac.uk/talks/id/e96d4efd-c944-4dd3-8684-25f1eba6b948/
DESCRIPTION:I will talk about algorithms (with unlimited computational pow
er) which adaptively probe pairs of vertices of a graph to learn the prese
nce or absence of edges and whose goal is to output a large clique. I will
focus on the case of the random graph G(n\,1/2)\, in which case the size
of the largest clique is roughly 2\\log(n). Our main result shows that if
the number of pairs queried is linear in n and adaptivity is restricted to
finitely many rounds\, then the largest clique cannot be found\; more pre
cisely\, no algorithm can find a clique larger than c\\log(n) where c < 2
is an explicit constant. This is joint work with Uriel Feige\, David Gamar
nik\, Joe Neeman\, and Prasad Tetali. \nSpeakers:\nMiklós Rácz (Princeto
n University)
LOCATION:Mathematical Institute\, Woodstock Road OX2 6GG
TZID:Europe/London
URL:https://talks.ox.ac.uk/talks/id/e96d4efd-c944-4dd3-8684-25f1eba6b948/
BEGIN:VALARM
ACTION:display
DESCRIPTION:Talk:Finding cliques using few probes - Miklós Rácz (Prince
ton University)
TRIGGER:-PT1H
END:VALARM
END:VEVENT
END:VCALENDAR