Finding cliques using few probes

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

doi:10.1002/rsa.20896

Finding cliques using few probes

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

Princeton University

Research output: Contribution to journal › Article › peer-review

2 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 language	English (US)
Pages (from-to)	142-153
Number of pages	12
Journal	Random Structures and Algorithms
Volume	56
Issue number	1
DOIs	https://doi.org/10.1002/rsa.20896
State	Published - Jan 1 2020

ASJC Scopus subject areas

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

Keywords

adaptive query model
cliques
random graphs

Access to Document

10.1002/rsa.20896

Cite this

@article{4b72f907cc08409583df9e0e35e255a2,

title = "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 (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.).",

keywords = "adaptive query model, cliques, random graphs",

author = "Uriel Feige and David Gamarnik and Joe Neeman and R{\'a}cz, \{Mikl{\'o}s Z.\} and Prasad Tetali",

note = "Publisher Copyright: {\textcopyright} 2019 Wiley Periodicals, Inc.",

year = "2020",

month = jan,

day = "1",

doi = "10.1002/rsa.20896",

language = "English (US)",

volume = "56",

pages = "142--153",

journal = "Random Structures and Algorithms",

issn = "1042-9832",

publisher = "John Wiley and Sons Ltd",

number = "1",

}

TY - JOUR

T1 - Finding cliques using few probes

AU - Feige, Uriel

AU - Gamarnik, David

AU - Neeman, Joe

AU - Rácz, Miklós Z.

AU - Tetali, Prasad

PY - 2020/1/1

Y1 - 2020/1/1

N2 - 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.).

AB - 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.).

KW - adaptive query model

KW - cliques

KW - random graphs

UR - https://www.scopus.com/pages/publications/85076522721

UR - https://www.scopus.com/pages/publications/85076522721#tab=citedBy

U2 - 10.1002/rsa.20896

DO - 10.1002/rsa.20896

M3 - Article

SN - 1042-9832

VL - 56

SP - 142

EP - 153

JO - Random Structures and Algorithms

JF - Random Structures and Algorithms

IS - 1

ER -

Finding cliques using few probes

Abstract

ASJC Scopus subject areas

Keywords

Access to Document

Other files and links

Fingerprint

Cite this