Zobrazeno 1 - 10
of 12
pro vyhledávání: '"Theory of computation → Semidefinite programming"'
In [Saunderson, 2011; Saunderson et al., 2013], Saunderson, Parrilo, and Willsky asked the following elegant geometric question: what is the largest m = m(d) such that there is an ellipsoid in ℝ^d that passes through v_1, v_2, …, v_m with high pr
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::40cb4af87344c65d39663ad0ac794959
Autor:
Kunisky, Dmitriy, Yu, Xifan
We prove that the degree 4 sum-of-squares (SOS) relaxation of the clique number of the Paley graph on a prime number $p$ of vertices has value at least $\Omega(p^{1/3})$. This is in contrast to the widely believed conjecture that the actual clique nu
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::6a6be6cd6a2d9729b401c981e9299a14
The problem of finding the largest induced balanced bipartite subgraph in a given graph is NP-hard. This problem is closely related to the problem of finding the smallest Odd Cycle Transversal. In this work, we consider the following model of instanc
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::2c12e153e8de623ec271e6b98b2025fd
http://arxiv.org/abs/2205.03727
http://arxiv.org/abs/2205.03727
Autor:
Parekh, Ojas, Thompson, Kevin
Publikováno v:
Proposed for presentation at the International Colloquium on Automata, Languages and Programming held July 12-16, 2021 in Virtual.
The Lasserre Hierarchy is a set of semidefinite programs which yield increasingly tight bounds on optimal solutions to many NP-hard optimization problems. The hierarchy is parameterized by levels, with a higher level corresponding to a more accurate
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::920c7783c2a2b2d1c4e2c4e2ab5209bb
https://doi.org/10.2172/1884683
https://doi.org/10.2172/1884683
Front Matter, Table of Contents, Preface, Conference Organization
LIPIcs, Vol. 204, 29th Annual European Symposium on Algorithms (ESA 2021), pages 0:i-0:xx
LIPIcs, Vol. 204, 29th Annual European Symposium on Algorithms (ESA 2021), pages 0:i-0:xx
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::680fffb25a506337a0daa8b00debae2e
Autor:
Parekh, Ojas, Thompson, Kevin
The quantum k-Local Hamiltonian problem is a natural generalization of classical constraint satisfaction problems (k-CSP) and is complete for QMA, a quantum analog of NP. Although the complexity of k-Local Hamiltonian problems has been well studied,
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::62c7fac2b31e819f93f6e584a7482a35
Autor:
Pang, Shuo
We prove a SOS degree lower bound for the planted clique problem on the Erdös-Rényi random graph G(n,1/2). The bound we get is degree d = Ω(ε²log n/log log n) for clique size ω = n^{1/2-ε}, which is almost tight. This improves the result of [B
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::1fbc4b036b435ebf694b2c15d9511f16
LIPIcs, Volume 204, ESA 2021, Complete Volume
LIPIcs, Vol. 204, 29th Annual European Symposium on Algorithms (ESA 2021), pages 1-1340
LIPIcs, Vol. 204, 29th Annual European Symposium on Algorithms (ESA 2021), pages 1-1340
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::a473de808f7f82a1dee1c640d7ddabfd
Publikováno v:
Leibniz International Proceedings in Informatics (LIPIcs), 198
48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
We study the rank of the Sum of Squares (SoS) hierarchy over the Boolean hypercube for Symmetric Quadratic Functions (SQFs) in n variables with roots placed in points k - 1 and k. Functions of this type have played a central role in deepening the und
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::0a289142d34734dab2b7e1abcca883ba
Autor:
Khanna, Yash, Louis, Anand
Given an undirected graph $G$, the Densest $k$-subgraph problem (DkS) asks to compute a set $S \subset V$ of cardinality $\left\lvert S\right\rvert \leq k$ such that the weight of edges inside $S$ is maximized. This is a fundamental NP-hard problem w
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::468aea5003a76fa7584ab354673eeb1a
http://arxiv.org/abs/2004.13978
http://arxiv.org/abs/2004.13978