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 -