### 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 | |

State | Published - Jan 1 2020 |

### All Science Journal Classification (ASJC) codes

- Software
- Mathematics(all)
- Computer Graphics and Computer-Aided Design
- Applied Mathematics

### Keywords

- adaptive query model
- cliques
- random graphs

## Fingerprint Dive into the research topics of 'Finding cliques using few probes'. Together they form a unique fingerprint.

## Cite this

Feige, U., Gamarnik, D., Neeman, J., Rácz, M. Z., & Tetali, P. (2020). Finding cliques using few probes.

*Random Structures and Algorithms*,*56*(1), 142-153. https://doi.org/10.1002/rsa.20896