@article{1d6c96e01bbb455190cb0dfd6f1a2670,

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",

}