3:30 pm,Seminar Hall
Finding Cliques with Few Probes
Prasad Tetali
School of Mathematics and School of Computer Science, Georgia Institute of Technology,USA.
26-08-19

---

Abstract

We consider algorithms with unbounded computation time that probe the entries of the adjacency matrix of an n-vertex graph and output a clique. We show positive and negative results - what is doable versus unlikely - assuming the input graph is an Erdos-Renyi random graph with edge probability 1/2, under the assumption that the algorithm uses a constant number of rounds, with each round limited to a linear number (or more generally, o(n^2)) of probes. Several questions remain open.

This is joint work with Uri Feige, David Gamarnik, Joe Neeman, and Miklos Racz.