Under the auspices of the Computational Complexity Foundation (CCF) REPORTS > KEYWORD > SUM-OF-SQUARES HIERARCHY:
Reports tagged with sum-of-squares hierarchy:
TR16-079 | 2nd May 2016
Adam Kurpisz, Samuli Lepp\"anen, Monaldo Mastrolilli

#### Sum-of-squares hierarchy lower bounds for symmetric formulations

We introduce a method for proving Sum-of-Squares (SoS)/ Lasserre hierarchy lower bounds when the initial problem formulation exhibits a high degree of symmetry. Our main technical theorem allows us to reduce the study of the positive semidefiniteness to the analysis of well-behaved'' univariate polynomial inequalities.

We illustrate the technique on ... more >>>

TR16-185 | 18th November 2016
Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani

#### Multiplicative Approximations for Polynomial Optimization Over the Unit Sphere

Revisions: 1

We consider the following basic problem: given an $n$-variate degree-$d$ homogeneous polynomial $f$ with real coefficients, compute a unit vector $x \in \mathbb{R}^n$ that maximizes $|f(x)|$. Besides its fundamental nature, this problem arises in many diverse contexts ranging from tensor and operator norms to graph expansion to quantum information ... more >>>

ISSN 1433-8092 | Imprint
{"ft_lang_label":"__label__en","ft_lang_prob":0.81020224,"math_prob":0.8925797,"size":797,"snap":"2020-45-2020-50","text_gpt3_token_len":168,"char_repetition_ratio":0.083228245,"word_repetition_ratio":0.0,"special_character_ratio":0.20577164,"punctuation_ratio":0.092307694,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9840474,"pos_list":[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14],"im_url_duplicate_count":[null,null,null,null,null,null,null,null,null,null,null,null,null,null,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2020-12-04T05:57:50Z\",\"WARC-Record-ID\":\"<urn:uuid:62a592a3-6064-45e4-a610-0311533d5b0d>\",\"Content-Length\":\"19635\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:de438df9-d9ab-45bb-9c0e-67fa59c83b00>\",\"WARC-Concurrent-To\":\"<urn:uuid:b7ce046a-a830-49de-8f42-d032fff99324>\",\"WARC-IP-Address\":\"132.77.150.87\",\"WARC-Target-URI\":\"https://eccc.weizmann.ac.il/keyword/19229/\",\"WARC-Payload-Digest\":\"sha1:QMBHLRDKKS434CZROXR65XFIL7AEABTG\",\"WARC-Block-Digest\":\"sha1:U26KNSLFXURLMWO3NXZHPWSQDW3C5Z2R\",\"WARC-Identified-Payload-Type\":\"application/xhtml+xml\",\"warc_filename\":\"/cc_download/warc_2020/CC-MAIN-2020-50/CC-MAIN-2020-50_segments_1606141733122.72_warc_CC-MAIN-20201204040803-20201204070803-00575.warc.gz\"}"}