Finding cliques using few probes

Uriel Feige, David Gamarnik, Joe Neeman, Miklós Z. Rácz, Prasad Tetali

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


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 (Formula presented.) (and hence is likely to have a clique of size roughly (Formula presented.)), then for every δ<2 and constant ℓ, there is an α<2 (that may depend on δ 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 (Formula presented.).

Original languageEnglish (US)
Pages (from-to)142-153
Number of pages12
JournalRandom Structures and Algorithms
Issue number1
StatePublished - Jan 1 2020

All Science Journal Classification (ASJC) codes

  • Software
  • General Mathematics
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics


  • adaptive query model
  • cliques
  • random graphs


Dive into the research topics of 'Finding cliques using few probes'. Together they form a unique fingerprint.

Cite this