English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We consider a problem introduced by Feige, Gamarnik, Neeman, R\'acz andTetali [2020], that of finding a large clique in a random graph $G\simG(n,\frac{1}{2})$, where the graph $G$ is accessible by queries to entries ofits adjacency matrix. The query model allows some limited adaptivity, with aconstant number of rounds of queries, and $n^\delta$ queries in each round.With high probability, the maximum clique in $G$ is of size roughly $2\log n$,and the goal is to find cliques of size $\alpha\log n$, for $\alpha$ as largeas possible. We prove that no two-rounds algorithm is likely to find a cliquelarger than $\frac{4}{3}\delta\log n$, which is a tight upper bound when$1\leq\delta\leq \frac{6}{5}$. For other ranges of parameters, namely,two-rounds with $\frac{6}{5}<\delta<2$, and three-rounds with $1\leq\delta<2$,we improve over the previously known upper bounds on $\alpha$, but our upperbounds are not tight. If early rounds are restricted to have fewer queries thanthe last round, then for some such restrictions we do prove tight upper bounds.

A tight bound for the clique query problem in two rounds