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

This work addresses the block-diagonal semidefinite program (SDP) relaxationsfor the clique number of the Paley graphs. The size of the maximal clique(clique number) of a graph is a classic NP-complete problem; a Paley graph is adeterministic graph where two vertices are connected if their difference is aquadratic residue (square) in a finite field with the number of elements givenby certain primes and prime powers. Improving the upper bound for the Paleygraph clique number for prime powers that are non-squares is an open problem incombinatorics. Moreover, since quadratic residues exhibit pseudorandomproperties, Paley graphs are related to the construction of deterministicrestricted isometries, an open problem in compressed sensing. Recent workprovides numerical evidence that the current upper bounds can be improved bythe sum-of-squares (SOS) relaxations. In particular, the bounds given by theSOS relaxations of degree 4 (SOS-4) have been empirically observed to begrowing at an order smaller than square root of the prime. However,computations of SOS-4 appear to be intractable with respect to large graphs.Gvozdenovic et al. introduced a more computationally efficient block-diagonalhierarchy of SDPs and computed the values of these SDPs of degrees 2 (L2) forthe Paley graph clique numbers associated with primes p less or equal to 809,which bound from above the corresponding SOS-4 relaxations. We compute thevalues of the L2 relaxations for p's between 821 and 997. Our results providesome numerical evidence that these relaxations, and therefore also the SOS-4relaxations, may be scaling at an order smaller than the square root of p.However, due to the size of the SDPs, we have not been able to compute L2relaxations for p's greater than 997. Therefore, our scaling estimate is notconclusive and presents an interesting open problem for further study.

Revisiting Block-Diagonal SDP Relaxations for the Clique Number of the Paley Graphs