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 6GGSee location on maps.ox**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