Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Publication

Extended Formulations, Nonnegative Factorizations, and Randomized Communication Protocols

Yuri Faenza, Hans Raj Tiwary
2012
Conference Papers

Résumé

We show that the binary logarithm of the nonnegative rank of a nonnegative matrix is, up to small constants, equal to the minimum complexity of a randomized communication protocol computing the matrix in expectation. We use this connection to prove new conditional lower bounds on the sizes of extended formulations, in particular, for perfect matching polytopes.

Source officielle

Yuri Faenza, Hans Raj Tiwary
2012
Conference Papers

Résumé

Source officielle

Concepts associés (21)

Matrice à coefficients positifs

Une matrice de type est à coefficients positifs lorsque tous ses éléments sont réels positifs ; on écrira alors . Elle est dite strictement positive lorsque tous ses éléments sont strictement positifs ; on écrira alors . et étant deux matrices réelles on définit une relation d'ordre partiel sur ces matrices en posant . Il est immédiat que cette relation d'ordre est compatible avec l'addition. De même elle est compatible avec la multiplication (à gauche ou à droite) par une matrice positive.

Matrix decomposition

In the mathematical discipline of linear algebra, a matrix decomposition or matrix factorization is a factorization of a matrix into a product of matrices. There are many different matrix decompositions; each finds use among a particular class of problems. In numerical analysis, different decompositions are used to implement efficient matrix algorithms. For instance, when solving a system of linear equations , the matrix A can be decomposed via the LU decomposition.

Definite matrix

In mathematics, a symmetric matrix with real entries is positive-definite if the real number is positive for every nonzero real column vector where is the transpose of . More generally, a Hermitian matrix (that is, a complex matrix equal to its conjugate transpose) is positive-definite if the real number is positive for every nonzero complex column vector where denotes the conjugate transpose of Positive semi-definite matrices are defined similarly, except that the scalars and are required to be positive or zero (that is, nonnegative).

Afficher plus

Publications associées (14)

Afficher plus

Extended Formulations, Nonnegative Factorizations, and Randomized Communication Protocols

Graph Chatbot

On the Use of the Generalized Littlewood Theorem Concerning Integrals of the Logarithm of Analytical Functions for the Calculation of Infinite Sums and the Analysis of Zeroes of Analytical Functions

Chung-type law of the iterated logarithm and exact moduli of continuity for a class of anisotropic Gaussian random fields

Propagation of singularities for the stochastic wave equation