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 derive upper and lower bounds on the degree $d$ for which the Lov\'asz$\vartheta$ function, or equivalently sum-of-squares proofs with degree two,can refute the existence of a $k$-coloring in random regular graphs $G_{n,d}$.We show that this type of refutation fails well above the $k$-colorabilitytransition, and in particular everywhere below the Kesten-Stigum threshold.This is consistent with the conjecture that refuting $k$-colorability, ordistinguishing $G_{n,d}$ from the planted coloring model, is hard in thisregion. Our results also apply to the disassortative case of the stochasticblock model, adding evidence to the conjecture that there is a regime wherecommunity detection is computationally hard even though it isinformation-theoretically possible. Using orthogonal polynomials, we alsoprovide explicit upper bounds on $\vartheta(\overline{G})$ for regular graphsof a given girth, which may be of independent interest.

The Lov\'asz Theta Function for Random Regular Graphs and Community Detection in the Hard Regime