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/
Go to the corresponding LIPIcs Volume Portal

Cheung, Tsun-Ming ; Hatami, Hamed ; Hosseini, Kaave ; Shirley, Morgan

Separation of the Factorization Norm and Randomized Communication Complexity

pdf-format:
LIPIcs-CCC-2023-1.pdf (0.8 MB)

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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI