Finding cliques using few probes
I will talk about algorithms (with unlimited computational power) which adaptively probe pairs of vertices of a graph to learn the presence 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 precisely, 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 Gamarnik, Joe Neeman, and Prasad Tetali.
Date:
29 October 2018, 12:00 (Monday, 4th week, Michaelmas 2018)
Venue:
Mathematical Institute, Woodstock Road OX2 6GG
Speaker:
Miklós Rácz (Princeton University)
Organising department:
Department of Statistics
Organisers:
Christina Goldschmidt (Department of Statistics, University of Oxford),
James Martin (Department of Statistics, University of Oxford)
Part of:
Probability seminar
Booking required?:
Not required
Audience:
Public
Editors:
Christina Goldschmidt,
James Martin
