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

G_{n, f r a c 12}

(and hence is likely to have a clique of size roughly

2 l o g n

), then for every

d e l t a < 2

and constant

e l l

, there is an

a l p h a < 2

(that may depend on

d e l t a

and

e l l

) such that no algorithm that makes

n^{d e l t a}

probes in

e l l

rounds is likely (over the choice of the random graph) to output a clique of size larger than

a l p h a l o g n

.

Cited In (6)

This page was built for publication: Finding cliques using few probes