| Title | : | Finding Cliques with Few Probes |
| Speaker | : | Prasad Tetali (Georgia Tech) |
| Details | : | Fri, 23 Aug, 2019 3:00 PM @ AM Turing Hall |
| 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. |
