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

^*Corresponding author for this work

Statistics and Data Science

Research output: Contribution to journal › Article › peer-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 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

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

Access to Document

10.1002/rsa.20896

Cite this

@article{8c818be4eb9d4caea17317f5c184a166,

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 = "Funding Information: 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. 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

N1 - Funding Information: 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. Publisher Copyright: © 2019 Wiley Periodicals, Inc.

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 - http://www.scopus.com/inward/record.url?scp=85076522721&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85076522721&partnerID=8YFLogxK

U2 - 10.1002/rsa.20896

DO - 10.1002/rsa.20896

M3 - Article

AN - SCOPUS:85076522721

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

Funding

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this