Approximate nonnegative rank is equivalent to the smooth rectangle bound

Gillat Kol; Shay Moran; Amir Shpilka; Amir Yehudayoff

doi:10.1007/978-3-662-43948-7_58

Approximate nonnegative rank is equivalent to the smooth rectangle bound

Gillat Kol, Shay Moran, Amir Shpilka, Amir Yehudayoff

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

11 Scopus citations

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.

Original language	English (US)
Title of host publication	Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Proceedings
Publisher	Springer Verlag
Pages	701-712
Number of pages	12
Edition	PART 1
ISBN (Print)	9783662439470
DOIs	https://doi.org/10.1007/978-3-662-43948-7_58
State	Published - 2014
Externally published	Yes
Event	41st International Colloquium on Automata, Languages, and Programming, ICALP 2014 - Copenhagen, Denmark Duration: Jul 8 2014 → Jul 11 2014

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Number	PART 1
Volume	8572 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	41st International Colloquium on Automata, Languages, and Programming, ICALP 2014
Country	Denmark
City	Copenhagen
Period	7/8/14 → 7/11/14

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-662-43948-7_58

Fingerprint Dive into the research topics of 'Approximate nonnegative rank is equivalent to the smooth rectangle bound'. Together they form a unique fingerprint.

Cite this

Kol, G., Moran, S., Shpilka, A., & Yehudayoff, A. (2014). Approximate nonnegative rank is equivalent to the smooth rectangle bound. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Proceedings (PART 1 ed., pp. 701-712). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8572 LNCS, No. PART 1). Springer Verlag. https://doi.org/10.1007/978-3-662-43948-7_58

Kol, Gillat ; Moran, Shay ; Shpilka, Amir ; Yehudayoff, Amir. / Approximate nonnegative rank is equivalent to the smooth rectangle bound. Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Proceedings. PART 1. ed. Springer Verlag, 2014. pp. 701-712 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 1).

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

note = "Copyright: Copyright 2014 Elsevier B.V., All rights reserved.; 41st International Colloquium on Automata, Languages, and Programming, ICALP 2014 ; Conference date: 08-07-2014 Through 11-07-2014",

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

}

Kol, G, Moran, S, Shpilka, A & Yehudayoff, A 2014, Approximate nonnegative rank is equivalent to the smooth rectangle bound. in Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Proceedings. PART 1 edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), no. PART 1, vol. 8572 LNCS, Springer Verlag, pp. 701-712, 41st International Colloquium on Automata, Languages, and Programming, ICALP 2014, Copenhagen, Denmark, 7/8/14. https://doi.org/10.1007/978-3-662-43948-7_58

Approximate nonnegative rank is equivalent to the smooth rectangle bound. / Kol, Gillat; Moran, Shay; Shpilka, Amir; Yehudayoff, Amir.

Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Proceedings. PART 1. ed. Springer Verlag, 2014. p. 701-712 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8572 LNCS, No. PART 1).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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

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 -

Kol G, Moran S, Shpilka A, Yehudayoff A. Approximate nonnegative rank is equivalent to the smooth rectangle bound. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Proceedings. PART 1 ed. Springer Verlag. 2014. p. 701-712. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 1). https://doi.org/10.1007/978-3-662-43948-7_58