124 citations · 361 across the 23 of their papers we have counts for
28 papers
Self-dual polyhedral cones and their slack matrices
João Gouveia, Bruno F. Lourenço
We analyze self-dual polyhedral cones and prove several properties about their slack matrices. In particular, we show that self-duality is equivalent to the existence of a positive…
The phase rank of a matrix
António Pedro Goucha, João Gouveia
In this paper, we introduce and study the notion of phase rank. Given a matrix filled with phases, i.e., with complex entries of modulus , its phase rank is the smallest possibl…
Complex psd-minimal polytopes in dimensions two and three
Tristram Bogart, João Gouveia, Juan Camilo Torres
The extension complexity of a polytope measures its amenability to succinct representations via lifts. There are several versions of extension complexity, including linear, real se…
General non-realizability certificates for spheres with linear programming
Joao Gouveia, Antonio Macchia, Amy Wiebe
In this paper we present a simple technique to derive certificates of non-realizability for an abstract polytopal sphere. Our approach uses a variant of the classical algebraic cer…
Quantum marginals, faces, and coatoms
Stephan Weis, João Gouveia
Many problems of quantum information theory rely on the set of quantum marginals. A precise knowledge of the faces of this convex set is necessary, for example, in the reconstructi…
An Algebraic Approach to Projective Uniqueness with an Application to Order Polytopes
Tristram Bogart, João Gouveia, Juan Camilo Torres
A combinatorial polytope is said to be projectively unique if it has a single realization up to projective transformations. Projective uniqueness is a geometrically compelling…
Lifting for Simplicity: Concise Descriptions of Convex Sets
Hamza Fawzi, João Gouveia, Pablo A. Parrilo +2
This paper presents a selected tour through the theory and applications of lifts of convex sets. A lift of a convex set is a higher-dimensional convex set that projects onto the or…
Combining realization space models of polytopes
João Gouveia, Antonio Macchia, Amy Wiebe
In this paper we examine four different models for the realization space of a polytope: the classical model, the Grassmannian model, the Gale transform model, and the slack variety…
On sums of squares of -nomials
João Gouveia, Alexander Kovačec, Mina Saee
In 2005, Boman et al introduced the concept of factor width for a real symmetric positive semidefinite matrix. This is the smallest positive integer for which the matrix ca…
The phaseless rank of a matrix
António Pedro Goucha, João Gouveia
We consider the problem of finding the smallest rank of a complex matrix whose absolute values of the entries are given. We call this minimum the phaseless rank of the matrix of th…
Projectively unique polytopes and toric slack ideals
João Gouveia, Antonio Macchia, Rekha R. Thomas +1
The slack ideal of a polytope is a saturated determinantal ideal that gives rise to a new model for the realization space of the polytope. The simplest slack ideals are toric and h…
Inner approximating the completely positive cone via the cone of scaled diagonally dominant matrices
João Gouveia, Ting Kei Pong, Mina Saee
Motivated by the expressive power of completely positive programming to encode hard optimization problems, many approximation schemes for the completely positive cone have been pro…
The Slack Realization Space of a Polytope
João Gouveia, Antonio Macchia, Rekha R. Thomas +1
In this paper we introduce a natural model for the realization space of a polytope up to projective equivalence which we call the slack realization space of the polytope. The model…
On ranks of regular polygons
António Pedro Goucha, João Gouveia, Pedro M. Silva
In this paper we study various versions of extension complexity for polygons through the study of factorization ranks of their slack matrices. In particular, we develop a new asymp…
Four Dimensional Polytopes of Minimum Positive Semidefinite Rank
João Gouveia, Kanstanstin Pashkovich, Richard Z. Robinson +1
The positive semidefinite (psd) rank of a polytope is the size of the smallest psd cone that admits an affine slice that projects linearly onto the polytope. The psd rank of a d-po…
Positive semidefinite rank
Hamza Fawzi, João Gouveia, Pablo A. Parrilo +2
Let M be a p-by-q matrix with nonnegative entries. The positive semidefinite rank (psd rank) of M is the smallest integer k for which there exist positive semidefinite matrices $A_…
Rational and real positive semidefinite rank can be different
João Gouveia, Hamza Fawzi, Richard Z. Robinson
Given a nonnegative matrix M with rational entries, we consider two quantities: the usual positive semidefinite (psd) rank, where the matrix is factored through the cone of real sy…
Sums of Squares on the Hypercube
Grigoriy Blekherman, João Gouveia, James Pfeiffer
Let X be a finite set of points in R^n. A polynomial p nonnegative on X can be written as a sum of squares of rational functions modulo the vanishing ideal I(X). From the point of…
Approximate cone factorizations and lifts of polytopes
João Gouveia, Pablo A. Parrilo, Rekha R. Thomas
In this paper we show how to construct inner and outer convex approximations of a polytope from an approximate cone factorization of its slack matrix. This provides a robust genera…
Worst-Case Results For Positive Semidefinite Rank
João Gouveia, Richard Z. Robinson, Rekha R. Thomas
This paper presents various worst-case results on the positive semidefinite (psd) rank of a nonnegative matrix, primarily in the context of polytopes. We prove that the psd rank of…
Which Nonnegative Matrices Are Slack Matrices?
João Gouveia, Roland Grappe, Volker Kaibel +3
In this paper we characterize the slack matrices of cones and polytopes among all nonnegative matrices. This leads to an algorithm for deciding whether a given matrix is a slack ma…
A Semidefinite Approach to the Cover Problem
João Gouveia, James Pfeiffer
We apply theta body relaxations to the -cover problem and show polynomial time solvability for certain classes of graphs. In particular, we give an effective relaxation where…
Polytopes of Minimum Positive Semidefinite Rank
João Gouveia, Richard Z. Robinson, Rekha R. Thomas
The positive semidefinite (psd) rank of a polytope is the smallest for which the cone of real symmetric psd matrices admits an affine slice that projects onto the…
Lifts of convex sets and cone factorizations
João Gouveia, Pablo A. Parrilo, Rekha Thomas
In this paper we address the basic geometric question of when a given convex set is the image under a linear map of an affine slice of a given closed convex cone. Such a representa…