1.3k citations · 2k across the 44 of their papers we have counts for
23 papers · 1 filter
Exact algorithms for quadratic optimization over roots of unity
Ahmad Al-Sulami, Hamza Fawzi, Shengding Sun
We consider the problem of optimizing a multivariate quadratic function where each decision variable is constrained to be a complex 'th root of unity. Such problems have applica…
Convergence of linear programming hierarchies for Gibbs states of spin systems
Hamza Fawzi, Omar Fawzi
We consider the problem of computing expectation values of local functions under the Gibbs distribution of a spin system. In particular, we study two families of linear programming…
Operator convexity along lines, self-concordance, and sandwiched Rényi entropies
Kerry He, James Saunderson, Hamza Fawzi
Barrier methods play a central role in the theory and practice of convex optimization. One of the most general and successful analyses of barrier methods for convex optimization, d…
QICS: Quantum Information Conic Solver
Kerry He, James Saunderson, Hamza Fawzi
We introduce QICS (Quantum Information Conic Solver), an open-source primal-dual interior point solver fully implemented in Python, which is focused on solving optimization problem…
Rational approximations of operator monotone and operator convex functions
Oisín Faust, Hamza Fawzi
Operator convex functions defined on the positive half-line play a prominent role in the theory of quantum information, where they are used to define quantum -divergences. Such…
Optimal self-concordant barriers for quantum relative entropies
Hamza Fawzi, James Saunderson
Quantum relative entropies are jointly convex functions of two positive definite matrices that generalize the Kullback-Leibler divergence and arise naturally in quantum information…
Sum-of-Squares proofs of logarithmic Sobolev inequalities on finite Markov chains
Oisín Faust, Hamza Fawzi
Logarithmic Sobolev inequalities are a fundamental class of inequalities that play an important role in information theory. They play a key role in establishing concentration inequ…
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…
The sum-of-squares hierarchy on the sphere, and applications in quantum information theory
Kun Fang, Hamza Fawzi
We consider the problem of maximizing a homogeneous polynomial on the unit sphere and its hierarchy of Sum-of-Squares (SOS) relaxations. Exploiting the polynomial kernel technique,…
On polyhedral approximations of the positive semidefinite cone
Hamza Fawzi
Let be the set of positive semidefinite matrices of trace equal to one, also known as the set of density matrices. We prove two results on the hardness of approxima…
A lower bound on the positive semidefinite rank of convex bodies
Hamza Fawzi, Mohab Safey El Din
The positive semidefinite rank of a convex body is the size of its smallest positive semidefinite formulation. We show that the positive semidefinite rank of any convex body $C…
Semidefinite approximations of the matrix logarithm
Hamza Fawzi, James Saunderson, Pablo A. Parrilo
The matrix logarithm, when applied to Hermitian positive definite matrices, is concave with respect to the positive semidefinite order. This operator concavity property leads to nu…
On representing the positive semidefinite cone using the second-order cone
Hamza Fawzi
The second-order cone plays an important role in convex optimization and has strong expressive abilities despite its apparent simplicity. Second-order cone formulations can also be…
Lieb's concavity theorem, matrix geometric means, and semidefinite optimization
Hamza Fawzi, James Saunderson
A famous result of Lieb establishes that the map is jointly concave in the pair of positive definite matrices, where…
Sparse sum-of-squares certificates on finite abelian groups
Hamza Fawzi, James Saunderson, Pablo A. Parrilo
Let G be a finite abelian group. This paper is concerned with nonnegative functions on G that are sparse with respect to the Fourier basis. We establish combinatorial conditions on…
Equivariant semidefinite lifts of regular polygons
Hamza Fawzi, James Saunderson, Pablo A. Parrilo
Given a polytope P in , we say that P has a positive semidefinite lift (psd lift) of size d if one can express P as the linear projection of an affine slice of the 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…
Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank
Hamza Fawzi, Pablo A. Parrilo
The nonnegative rank of a matrix A is the smallest integer r such that A can be written as the sum of r rank-one nonnegative matrices. The nonnegative rank has received a lot of at…
Equivariant semidefinite lifts and sum-of-squares hierarchies
Hamza Fawzi, James Saunderson, Pablo A. Parrilo
A central question in optimization is to maximize (or minimize) a linear function over a given polytope P. To solve such a problem in practice one needs a concise description of th…
Exponential lower bounds on fixed-size psd rank and semidefinite extension complexity
Hamza Fawzi, Pablo A. Parrilo
There has been a lot of interest recently in proving lower bounds on the size of linear programs needed to represent a given polytope P. In a breakthrough paper Fiorini et al. [Pro…
Lower bounds on nonnegative rank via nonnegative nuclear norms
Hamza Fawzi, Pablo A. Parrilo
The nonnegative rank of an entrywise nonnegative matrix A of size mxn is the smallest integer r such that A can be written as A=UV where U is mxr and V is rxn and U and V are both…
Secure estimation and control for cyber-physical systems under adversarial attacks
Hamza Fawzi, Paulo Tabuada, Suhas Diggavi
The vast majority of today's critical infrastructure is supported by numerous feedback control loops and an attack on these control loops can have disastrous consequences. This is…