@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",

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",

}