Finding cliques using few probes

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

Research output: Contribution to journalArticle

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 (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
Volume56
Issue number1
DOIs
StatePublished - Jan 1 2020

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics

Keywords

  • adaptive query model
  • cliques
  • random graphs

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

  • Cite this

    Feige, U., Gamarnik, D., Neeman, J., Rácz, M. Z., & Tetali, P. (2020). Finding cliques using few probes. Random Structures and Algorithms, 56(1), 142-153. https://doi.org/10.1002/rsa.20896