{"@context":["https://w3id.org/fdo/context/v1",{"schema":"https://schema.org/","prov":"http://www.w3.org/ns/prov#","fdo":"https://w3id.org/fdo/vocabulary/"}],"@id":"https://fdo.portal.mardi4nfdi.de/fdo/Q344935","@type":"DigitalObject","kernel":{"@id":"https://fdo.portal.mardi4nfdi.de/fdo/Q344935","digitalObjectType":"https://schema.org/ScholarlyArticle","primaryIdentifier":"mardi:Q344935","kernelVersion":"v1","immutable":true,"modified":"2026-03-23T16:35:14Z"},"profile":{"@context":"https://schema.org","@type":"ScholarlyArticle","@id":"https://portal.mardi4nfdi.de/entity/Q344935","name":"Sparse sums of squares on finite abelian groups and improved semidefinite lifts","headline":"Sparse sums of squares on finite abelian groups and improved semidefinite lifts","description":"scientific article; zbMATH DE number 6656094","url":"https://portal.mardi4nfdi.de/entity/Q344935","datePublished":"2016-11-25","author":[{"@id":"https://portal.mardi4nfdi.de/entity/Q304253"},{"@id":"https://portal.mardi4nfdi.de/entity/Q344904"},{"@id":"https://portal.mardi4nfdi.de/entity/Q304254"}],"publisher":[{"@id":"https://portal.mardi4nfdi.de/entity/Q163006"}],"identifier":{"@type":"PropertyValue","propertyID":"doi","value":"10.1007/S10107-015-0977-Z","url":"https://doi.org/10.1007/S10107-015-0977-Z"},"sameAs":["https://doi.org/10.1007/S10107-015-0977-Z"],"comment":"The paper is concerned with nonnegative functions on a finite abelian group \\(G\\) that are sparse with respect to the Fourier basis. The authors establish combinatorial conditions on subsets \\(\\mathcal{S}\\) and \\(\\mathcal{T}\\) of Fourier basis elements under which nonnegative functions with Fourier support \\(\\mathcal{S}\\) are sums of squares of functions with Fourier support \\(\\mathcal{T}\\). Their combinatorial condition involves constructing a chordal cover of a graph related to \\(G\\) and \\(\\mathcal{S}\\) (Cayley graph Cay(\\(\\widehat{G},\\mathcal{S}\\))) with maximal cliques related to \\(\\mathcal{T}\\). Their result relies on two main ingredients: the decomposition of sparse positive semidefinite matrices with a chordal sparsity pattern, as well as a simple but key observation exploiting the structure of the Fourier basis elements of \\(G\\). They apply their main result to two important special cases, namely \\(G=\\mathbb{Z}^n_2\\) (the Boolean hypercube) and \\(G=\\mathbb{Z}_N\\).","citation":[{"@id":"https://portal.mardi4nfdi.de/entity/Q1109100"},{"@id":"https://portal.mardi4nfdi.de/entity/Q4790110"},{"@id":"https://portal.mardi4nfdi.de/entity/Q2351019"},{"@id":"https://portal.mardi4nfdi.de/entity/Q329957"},{"@id":"https://portal.mardi4nfdi.de/entity/Q4902572"},{"@id":"https://portal.mardi4nfdi.de/entity/Q5899432"},{"@id":"https://portal.mardi4nfdi.de/entity/Q745689"},{"@id":"https://portal.mardi4nfdi.de/entity/Q1759811"},{"@id":"https://portal.mardi4nfdi.de/entity/Q5739152"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3451762"},{"@id":"https://portal.mardi4nfdi.de/entity/Q5511980"},{"@id":"https://portal.mardi4nfdi.de/entity/Q798738"},{"@id":"https://portal.mardi4nfdi.de/entity/Q5169664"},{"@id":"https://portal.mardi4nfdi.de/entity/Q5186653"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3009770"},{"@id":"https://portal.mardi4nfdi.de/entity/Q2706355"},{"@id":"https://portal.mardi4nfdi.de/entity/Q5704154"},{"@id":"https://portal.mardi4nfdi.de/entity/Q4496025"},{"@id":"https://portal.mardi4nfdi.de/entity/Q5890171"},{"@id":"https://portal.mardi4nfdi.de/entity/Q4256626"},{"@id":"https://portal.mardi4nfdi.de/entity/Q1186549"},{"@id":"https://portal.mardi4nfdi.de/entity/Q4323295"}]},"provenance":{"prov:generatedAtTime":"2026-03-23T16:35:14Z","prov:wasAttributedTo":"MaRDI Knowledge Graph"}}