39 citations · 143 across the 11 of their papers we have counts for
15 papers
3D genome reconstruction from partially phased Hi-C data
Diego Cifuentes, Jan Draisma, Oskar Henriksson +2
The 3-dimensional (3D) structure of the genome is of significant importance for many cellular processes. In this paper, we study the problem of reconstructing the 3D structure of c…
Efficient sampling from shallow Gaussian quantum-optical circuits with local interactions
Haoyu Qi, Diego Cifuentes, Kamil Brádler +3
We prove that a classical computer can efficiently sample from the photon-number probability distribution of a Gaussian state prepared by using an optical circuit that is shallow a…
Polynomial time guarantees for the Burer-Monteiro method
Diego Cifuentes, Ankur Moitra
The Burer-Monteiro method is one of the most widely used techniques for solving large-scale semidefinite programs (SDP). The basic idea is to solve a nonconvex program in , wher…
A convex relaxation to compute the nearest structured rank deficient matrix
Diego Cifuentes
Given an affine space of matrices and a matrix , consider the problem of computing the closest rank deficient matrix to on with re…
On the Burer-Monteiro method for general semidefinite programs
Diego Cifuentes
Consider a semidefinite program (SDP) involving an positive semidefinite matrix . The Burer-Monteiro method uses the substitution to obtain a nonconvex opt…
On the Complexity of Toric Ideals
Diego Cifuentes, Shmuel Onn
We investigate the computational complexity of problems on toric ideals such as normal forms, Gröbner bases, and Graver bases. We show that all these problems are strongly NP-hard…
Sums of squares in Macaulay2
Diego Cifuentes, Thomas Kahle, Pablo A. Parrilo
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 pac…
Voronoi Cells of Varieties
Diego Cifuentes, Kristian Ranestad, Bernd Sturmfels +1
Every real algebraic variety determines a Voronoi decomposition of its ambient Euclidean space. Each Voronoi cell is a convex semialgebraic set in the normal space of the variety a…
The Geometry of SDP-Exactness in Quadratic Optimization
Diego Cifuentes, Corey Harris, Bernd Sturmfels
Consider the problem of minimizing a quadratic objective subject to quadratic equations. We study the semialgebraic region of objective functions for which this problem is solved b…
On the local stability of semidefinite relaxations
Diego Cifuentes, Sameer Agarwal, Pablo A. Parrilo +1
We consider a parametric family of quadratically constrained quadratic programs (QCQP) and their associated semidefinite programming (SDP) relaxations. Given a nominal value of the…
Chordal networks of polynomial ideals
Diego Cifuentes, Pablo A. Parrilo
We introduce a novel representation of structured polynomial ideals, which we refer to as chordal networks. The sparsity structure of a polynomial system is often described by a gr…
Sampling algebraic varieties for sum of squares programs
Diego Cifuentes, Pablo A. Parrilo
We study sum of squares (SOS) relaxations to optimize polynomial functions over a set , where is a complex algebraic variety. We propose a new methodology that, rath…
An efficient tree decomposition method for permanents and mixed discriminants
Diego Cifuentes, Pablo A. Parrilo
We present an efficient algorithm to compute permanents, mixed discriminants and hyperdeterminants of structured matrices and multidimensional arrays (tensors). We describe the spa…
Exploiting chordal structure in polynomial ideals: a Gröbner bases approach
Diego Cifuentes, Pablo Parrilo
Chordal structure and bounded treewidth allow for efficient computation in numerical linear algebra, graphical models, constraint satisfaction and many other areas. In this paper,…
On the degree-chromatic polynomial of a tree
Diego Cifuentes
The degree chromatic polynomial of a graph counts the number of -colorings in which no vertex has adjacent vertices of its same color. We prove Humpert and Mar…