TY - GEN
T1 - Approximate nonnegative rank is equivalent to the smooth rectangle bound
AU - Kol, Gillat
AU - Moran, Shay
AU - Shpilka, Amir
AU - Yehudayoff, Amir
N1 - Copyright:
Copyright 2014 Elsevier B.V., All rights reserved.
PY - 2014
Y1 - 2014
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84904206080&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84904206080&partnerID=8YFLogxK
U2 - 10.1007/978-3-662-43948-7_58
DO - 10.1007/978-3-662-43948-7_58
M3 - Conference contribution
AN - SCOPUS:84904206080
SN - 9783662439470
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 701
EP - 712
BT - Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Proceedings
PB - Springer Verlag
T2 - 41st International Colloquium on Automata, Languages, and Programming, ICALP 2014
Y2 - 8 July 2014 through 11 July 2014
ER -