Oxford Events, the new replacement for OxTalks, will launch on 16th March. From now until the launch of Oxford Events, new events cannot be published or edited on OxTalks while all existing records are migrated to the new platform. The existing OxTalks site will remain available to view during this period.
From 16th, Oxford Events will launch on a new website: events.ox.ac.uk, and event submissions will resume. You will need a Halo login to submit events. Full details are available on the Staff Gateway.
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.
