Finding cliques using few probes

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

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

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

Funding

information:This research was supported by the NSF, DMS 1811724. DMS-1407657. DMS-1811935; Israel Science Foundation (grant No. 1388/16) to [U.F.]; ONR grant N00014-17-1-2790 to [D.G.]; Alfred P. Sloan Foundation to [J.N.]; National Science Foundation (NSF) grant DMS 1811724 to [M.Z.R.]; National Science Foundation (NSF) grants DMS 1407657 and DMS 1811935 to [P.T.].The problem considered here was proposed by David Gamarnik at the American Institute of Mathematics workshop “Phase transitions in randomized computational problems” in June 2017. It arose from a discussion with Madhu Sudan, whose contribution to the inception of the problem is gratefully acknowledged. We thank AIM and the organizers, Amir Dembo, Jian Ding, and Nike Sun, for putting together the workshop. We also thank Jane Gao for initial discussions and two anonymous referees for their feedback.

Keywords

  • adaptive query model
  • cliques
  • random graphs

ASJC Scopus subject areas

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

Fingerprint

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

Cite this