License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2023.1
URN: urn:nbn:de:0030-drops-182714
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18271/
Cheung, Tsun-Ming ;
Hatami, Hamed ;
Hosseini, Kaave ;
Shirley, Morgan
Separation of the Factorization Norm and Randomized Communication Complexity
Abstract
In an influential paper, Linial and Shraibman (STOC '07) introduced the factorization norm as a powerful tool for proving lower bounds against randomized and quantum communication complexities. They showed that the logarithm of the approximate γ₂-factorization norm is a lower bound for these parameters and asked whether a stronger lower bound that replaces approximate γ₂ norm with the γ₂ norm holds.
We answer the question of Linial and Shraibman in the negative by exhibiting a 2ⁿ×2ⁿ Boolean matrix with γ₂ norm 2^Ω(n) and randomized communication complexity O(log n).
As a corollary, we recover the recent result of Chattopadhyay, Lovett, and Vinyals (CCC '19) that deterministic protocols with access to an Equality oracle are exponentially weaker than (one-sided error) randomized protocols. In fact, as a stronger consequence, our result implies an exponential separation between the power of unambiguous nondeterministic protocols with access to Equality oracle and (one-sided error) randomized protocols, which answers a question of Pitassi, Shirley, and Shraibman (ITSC '23).
Our result also implies a conjecture of Sherif (Ph.D. thesis) that the γ₂ norm of the Integer Inner Product function (IIP) in dimension 3 or higher is exponential in its input size.
BibTeX - Entry
@InProceedings{cheung_et_al:LIPIcs.CCC.2023.1,
author = {Cheung, Tsun-Ming and Hatami, Hamed and Hosseini, Kaave and Shirley, Morgan},
title = {{Separation of the Factorization Norm and Randomized Communication Complexity}},
booktitle = {38th Computational Complexity Conference (CCC 2023)},
pages = {1:1--1:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-282-2},
ISSN = {1868-8969},
year = {2023},
volume = {264},
editor = {Ta-Shma, Amnon},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18271},
URN = {urn:nbn:de:0030-drops-182714},
doi = {10.4230/LIPIcs.CCC.2023.1},
annote = {Keywords: Factorization norms, randomized communication complexity}
}
Keywords: |
|
Factorization norms, randomized communication complexity |
Collection: |
|
38th Computational Complexity Conference (CCC 2023) |
Issue Date: |
|
2023 |
Date of publication: |
|
10.07.2023 |