@inproceedings{ebd0717384be43a4b045d9fce2fc1284,
title = "Approximate nonnegative rank is equivalent to the smooth rectangle bound",
abstract = "We consider two known lower bounds on randomized communication complexity: The smooth rectangle bound and the logarithm of the approximate nonnegative rank. Our main result is that they are the same up to a multiplicative constant and a small additive term. The logarithm of the nonnegative rank is known to be a nearly tight lower bound on the deterministic communication complexity. Our result indicates that proving the analogue for the randomized case, namely that the log approximate nonnegative rank is a nearly tight bound on randomized communication complexity, would imply the tightness of the information cost bound. Another corollary of our result is the existence of a boolean function with a quasipolynomial gap between its approximate rank and approximate nonnegative rank.",
author = "Gillat Kol and Shay Moran and Amir Shpilka and Amir Yehudayoff",
year = "2014",
month = jan,
day = "1",
doi = "10.1007/978-3-662-43948-7_58",
language = "English (US)",
isbn = "9783662439470",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
number = "PART 1",
pages = "701--712",
booktitle = "Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Proceedings",
address = "Germany",
edition = "PART 1",
note = "41st International Colloquium on Automata, Languages, and Programming, ICALP 2014 ; Conference date: 08-07-2014 Through 11-07-2014",
}