# Dagstuhl Report 13082: Communication Complexity, Linear Optimization, and lower bounds for the nonnegative rank of matrices

@article{Beasely2013DagstuhlR1, title={Dagstuhl Report 13082: Communication Complexity, Linear Optimization, and lower bounds for the nonnegative rank of matrices}, author={LeRoy Beasely and Troy Lee and Hartmut Klauck and Dirk Oliver Theis}, journal={ArXiv}, year={2013}, volume={abs/1305.4147} }

This report documents the program and the outcomes of Dagstuhl Seminar 13082 "Communication Complexity, Linear Optimization, and lower bounds for the nonnegative rank of matrices", held in February 2013 at Dagstuhl Castle.

#### Topics from this paper

#### 2 Citations

Heuristics for exact nonnegative matrix factorization

- Mathematics, Computer Science
- J. Glob. Optim.
- 2016

Two heuristics for exact NMF are proposed, one inspired from simulated annealing and the other from the greedy randomized adaptive search procedure, able to compute exact nonnegative factorizations for several classes of nonnegative matrices and demonstrate their superiority over standard multi-start strategies. Expand

A universality theorem for nonnegative matrix factorizations

- Mathematics
- 2016

Let $A$ be a matrix with nonnegative real entries. A nonnegative factorization of size $k$ is a representation of $A$ as a sum of $k$ nonnegative rank-one matrices. The space of all such… Expand

#### References

SHOWING 1-10 OF 16 REFERENCES

An upper bound for nonnegative rank

- Computer Science, Mathematics
- J. Comb. Theory, Ser. A
- 2014

We provide a nontrivial upper bound for the nonnegative rank of rank-three matrices which allows us to prove that ? 6 n / 7 ? linear inequalities suffice to describe a convex n-gon up to a linear… Expand

Which nonnegative matrices are slack matrices

- Mathematics
- 2013

Abstract 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 matrix. The… Expand

Fooling-sets and rank in nonzero characteristic

- Mathematics, Computer Science
- CTW
- 2013

Dietzfel-binger, Hromkovic, and Schnitger (1996) showed that n ≤ (rkM)2, regardless of over which field the rank is computed, and asked whether the exponent on rkM can be improved. Expand

Real rank versus nonnegative rank

- Mathematics
- 2009

Abstract We consider the set of m × n nonnegative real matrices and define the nonnegative rank of a matrix A to be the minimum k such that A = BC where B is m × k and C is k × n . Given that the… Expand

Common Information and Unique Disjointness

- Computer Science, Mathematics
- 2013 IEEE 54th Annual Symposium on Foundations of Computer Science
- 2013

An information-theoretic framework for establishing strong lower bounds on the nonnegative rank of matrices by means of common information by combining it with Hellinger distance estimations and an information theoretic variant of the fooling set method that allows to extend fooleding set lower bounds from extension complexity to approximate extension complexity are provided. Expand

An analog of the cook theorem for polytopes

- Mathematics
- 2012

We prove that the polytope M of any combinatorial optimization problem with a linear objective function is an affine image of some facet of the cut polytope whose dimension is polynomial with respect… Expand

Support-based lower bounds for the positive semidefinite rank of a nonnegative matrix

- Mathematics, Computer Science
- 2012

The power of lower bounds on positive semidefinite rank is characterized based on solely on the support of the matrix S, i.e., its zero/non-zero pattern. Expand

On the copositive representation of binary and continuous nonconvex quadratic programs

- Mathematics, Computer Science
- Math. Program.
- 2009

Any nonconvex quadratic program having a mix of binary and continuous variables as a linear program over the dual of the cone of copositive matrices is model, which reduces the dimension of the linear conic program. Expand

Fooling-sets and rank in nonzero characteristic (extended abstract)

- Mathematics
- 2013

An n\times n matrix M is called a fooling-set matrix of size n, if its diagonal entries are nonzero, whereas for every k\ne \ell we have M_{k,\ell} M_{\ell,k} = 0. Dietzfelbinger, Hromkovi\v{c}, and… Expand

Clique versus independent set

- Mathematics, Computer Science
- Eur. J. Comb.
- 2014

It is shown that a polynomial CS-separator is equivalent to thePolynomial Alon–Saks–Seymour Conjecture, asserting that if a graph has an edge-partition into k complete bipartite graphs, then its chromatic number is polynomially bounded in terms of k . Expand