Source author record

Marianna Eisenberg-Nagy

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.OC Discrete Mathematics math.CO

Catalog footprint

Research overview

2works

3topics

2close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2014arXiv

Forbidden minor characterizations for low-rank optimal solutions to semidefinite programs over the elliptope

We study a new geometric graph parameter $\egd(G)$, defined as the smallest integer $r\ge 1$ for which any partial symmetric matrix which is completable to a correlation matrix and whose entries are specified at the positions of the edges of $G$ , can be completed to a matrix in the convex hull of correlation matrices of $\rank $ at most $r$ . This graph parameter is motivated by its relevance to the problem of finding low rank solutions to semidefinite programs over the elliptope, and also by its relevance to the bounded rank Grothendieck constant. Indeed, $\egd(G)\le r$ if and only if the rank- $r$ Grothendieck constant of $G$ is equal to 1. We show that the parameter $\egd(G)$ is minor monotone, we identify several classes of forbidden minors for $\egd(G)\le r$ and we give the full characterization for the case $r=2$ . We also show an upper bound for $\egd(G)$ in terms of a new tree-width-like parameter $\sla(G)$, defined as the smallest $r$ for which $G$ is a minor of the strong product of a tree and $K_r$ . We show that, for any 2-connected graph $G\ne K_{3,3}$ on at least 6 nodes, $\egd(G)\le 2$ if and only if $\sla(G)\le 2$.

preprint2012arXiv

Complexity of the positive semidefinite matrix completion problem with a rank constraint

We consider the decision problem asking whether a partial rational symmetric matrix with an all-ones diagonal can be completed to a full positive semidefinite matrix of rank at most $k$ . We show that this problem is $\NP$-hard for any fixed integer $k\ge 2$ . Equivalently, for $k\ge 2$ , it is $\NP$-hard to test membership in the rank constrained elliptope $\EE_k(G)$, i.e., the set of all partial matrices with off-diagonal entries specified at the edges of $G$ , that can be completed to a positive semidefinite matrix of rank at most $k$ . Additionally, we show that deciding membership in the convex hull of $\EE_k(G)$ is also $\NP$-hard for any fixed integer $k\ge 2$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.