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.