2018/09/18 by Feige, Uriel, Gamarnik, David, Neeman, Joe +2
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR)
paper · doi:10.48550/arxiv.1809.06950
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 Gn,(1)/(2) (and hence is likely to have a clique of size roughly 2log n), 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 αlog n.