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 Tools annual

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 Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

In this paper, we develop machinery which makes it much easier to prove sumof squares lower bounds when the problem is symmetric under permutations of$[1,n]$ and the unsatisfiability of our problem comes from integralityarguments, i.e. arguments that an expression must be an integer. Roughlyspeaking, to prove SOS lower bounds with our machinery it is sufficient toverify that the answer to the following three questions is yes:  1. Are there natural pseudo-expectation values for the problem?  2. Are these pseudo-expectation values rational functions of the problemparameters?  3. Are there sufficiently many values of the parameters for which thesepseudo-expectation values correspond to the actual expected values over adistribution of solutions which is the uniform distribution over permutationsof a single solution?  We demonstrate our machinery on three problems, the knapsack problem analyzedby Grigoriev, the MOD 2 principle (which says that the complete graph $K_n$ hasno perfect matching when $n$ is odd), and the following Turan type problem:Minimize the number of triangles in a graph $G$ with a given edge density. Forknapsack, we recover Grigoriev's lower bound exactly. For the MOD 2 principle,we tighten Grigoriev's linear degree sum of squares lower bound, making itexact. Finally, for the triangle problem, we prove a sum of squares lower boundfor finding the minimum triangle density. This lower bound is completely newand gives a simple example where constant degree sum of squares methods have aconstant factor error in estimating graph densities.

Sum of squares lower bounds from symmetry and a good story