Finding cliques using few probes
Abstract
Consider algorithms with unbounded computation time that probe the entries of the adjacency matrix of an n vertex graph, and need to output a clique. We show that if the input graph is drawn at random from (and hence is likely to have a clique of size roughly ), then for every δℓ, there is an αδ and ℓ) such that no algorithm that makes nδ probes in ℓ rounds is likely (over the choice of the random graph) to output a clique of size larger than .
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Oct 22, 2019
- Source ID
- 10.1002/rsa.20896
Entities
People
- David Gamarnik
- Joe Neeman
- Miklós Z. Rácz
- Prasad Tetali
- Uriel Feige
Organizations
- Alfred P. Sloan Foundation
- Israel Science Foundation
- Massachusetts Institute of Technology
- National Science Foundation
- Office of Naval Research
- Princeton University
- Weizmann Institute of Science