Source author record

Diego Cifuentes

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

ResearcherUnclaimed source record

math.OC math.AC Computational Complexity Data Structures and Algorithms Discrete Mathematics math.AG math.CO Symbolic Computation

Catalog footprint

Research overview

5works

8topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

On the Burer-Monteiro method for general semidefinite programs

Consider a semidefinite program (SDP) involving an $n\times n$ positive semidefinite matrix $X$ . The Burer-Monteiro method uses the substitution $X=Y Y^T$ to obtain a nonconvex optimization problem in terms of an $n\times p$ matrix $Y$ . Boumal et al. showed that this nonconvex method provably solves equality-constrained SDPs with a generic cost matrix when $p \gtrsim \sqrt{2m}$ , where $m$ is the number of constraints. In this note we extend their result to arbitrary SDPs, possibly involving inequalities or multiple semidefinite constraints. We derive similar guarantees for a fixed cost matrix and generic constraints. We illustrate applications to matrix sensing and integer quadratic minimization.

preprint2020arXiv

Sums of squares in Macaulay2

The Macaulay2 package SumsOfSquares decomposes polynomials as sums of squares. It is based on methods to rationalize sum-of-squares decompositions due to Parrilo and Peyrl. The package features a data type for sums-of-squares polynomials, support for external semidefinite programming solvers, and optimization over varieties.

preprint2016arXiv

Exploiting chordal structure in polynomial ideals: a Gröbner bases approach

Chordal structure and bounded treewidth allow for efficient computation in numerical linear algebra, graphical models, constraint satisfaction and many other areas. In this paper, we begin the study of how to exploit chordal structure in computational algebraic geometry, and in particular, for solving polynomial systems. The structure of a system of polynomial equations can be described in terms of a graph. By carefully exploiting the properties of this graph (in particular, its chordal completions), more efficient algorithms can be developed. To this end, we develop a new technique, which we refer to as chordal elimination, that relies on elimination theory and Gröbner bases. By maintaining graph structure throughout the process, chordal elimination can outperform standard Gröbner basis algorithms in many cases. The reason is that all computations are done on "smaller" rings, of size equal to the treewidth of the graph. In particular, for a restricted class of ideals, the computational complexity is linear in the number of variables. Chordal structure arises in many relevant applications. We demonstrate the suitability of our methods in examples from graph colorings, cryptography, sensor localization and differential equations.

preprint2015arXiv

An efficient tree decomposition method for permanents and mixed discriminants

We present an efficient algorithm to compute permanents, mixed discriminants and hyperdeterminants of structured matrices and multidimensional arrays (tensors). We describe the sparsity structure of an array in terms of a graph, and we assume that its treewidth, denoted as $ω$ , is small. Our algorithm requires $O(n 2^ω)$ arithmetic operations to compute permanents, and $O(n^2 + n 3^ω)$ for mixed discriminants and hyperdeterminants. We finally show that mixed volume computation continues to be hard under bounded treewidth assumptions.

preprint2011arXiv

On the degree-chromatic polynomial of a tree

The degree chromatic polynomial $Pm(G,k)$ of a graph $G$ counts the number of $k$ -colorings in which no vertex has $m$ adjacent vertices of its same color. We prove Humpert and Martin's conjecture on the leading terms of the degree chromatic polynomial of a tree.

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.