In an influential paper, Linial and Shraibman (STOC '07)introduced the factorization norm as a powerful tool for proving lowerbounds against randomized and quantum communication complexities.They showed that the logarithm of the approximate <InlineEquation ID="IEq100"> <EquationSource Format="TEX">$\gamma_2$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>γ</mi> <mn>2</mn> </msub> </math></EquationSource> </InlineEquation>-factorization norm is a lower bound for these parameters and asked whether astronger lower bound that replaces approximate <InlineEquation ID="IEq200"> <EquationSource Format="TEX">$\gamma_2$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>γ</mi> <mn>2</mn> </msub> </math></EquationSource> </InlineEquation> norm with the <InlineEquation ID="IEq300"> <EquationSource Format="TEX">$\gamma_2$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>γ</mi> <mn>2</mn> </msub> </math></EquationSource> </InlineEquation> norm holds.We answer the question of Linial and Shraibman in the negative byexhibiting a <InlineEquation ID="IEq600"> <EquationSource Format="TEX">$2^n\times2^n $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mn>2</mn> <mi>n</mi> </msup> <mo>×</mo> <msup> <mn>2</mn> <mi>n</mi> </msup> </mrow> </math></EquationSource> </InlineEquation> Boolean matrix with <InlineEquation ID="IEq400"> <EquationSource Format="TEX">$\gamma_2$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>γ</mi> <mn>2</mn> </msub> </math></EquationSource> </InlineEquation> norm <InlineEquation ID="IEq700"> <EquationSource Format="TEX">$2^{\Omega(n)}$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mn>2</mn> <mrow> <mi mathvariant="normal">Ω</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </msup> </math></EquationSource> </InlineEquation> and randomized communication complexity <InlineEquation ID="IEq800"> <EquationSource Format="TEX">$O(\log n)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mo>log</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>.As a corollary, we recover the recent result of Chattopadhyay, Lovett,and Vinyals (CCC '19) that deterministic protocols with access to anEquality oracle are exponentially weaker than (one-sided error) randomizedprotocols. In fact, as a stronger consequence, our result implies anexponential separation between the power of unambiguous nondeterministicprotocols with access to Equality oracle and (one-sided error)randomized protocols, which answers a question of Pitassi, Shirley, andShraibman (ITCS '23).Our result also implies a conjecture of Sherif (Ph.D. thesis) that the<InlineEquation ID="IEq500"> <EquationSource Format="TEX">$\gamma_2$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>γ</mi> <mn>2</mn> </msub> </math></EquationSource> </InlineEquation> norm of the Integer Inner Product function (IIP) in dimension 3 orhigher is exponential in its input size.

Separation of the Factorization Norm and Randomized Communication Complexity

期刊论文
发表日期：

2025年10月27日

查看全文

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

摘要

In an influential paper, Linial and Shraibman (STOC '07)introduced the factorization norm as a powerful tool for proving lowerbounds against randomized and quantum communication complexities.They showed that the logarithm of the approximate $\gamma_2$ $γ_{2}$ -factorization norm is a lower bound for these parameters and asked whether astronger lower bound that replaces approximate $\gamma_2$ $γ_{2}$ norm with the $\gamma_2$ $γ_{2}$ norm holds.

We answer the question of Linial and Shraibman in the negative byexhibiting a $2^n\times2^n $ $2^{n} \times 2^{n}$ Boolean matrix with $\gamma_2$ $γ_{2}$ norm $2^{\Omega(n)}$ $2^{Ω (n)}$ and randomized communication complexity $O(\log n)$ $O (log n)$ .

As a corollary, we recover the recent result of Chattopadhyay, Lovett,and Vinyals (CCC '19) that deterministic protocols with access to anEquality oracle are exponentially weaker than (one-sided error) randomizedprotocols. In fact, as a stronger consequence, our result implies anexponential separation between the power of unambiguous nondeterministicprotocols with access to Equality oracle and (one-sided error)randomized protocols, which answers a question of Pitassi, Shirley, andShraibman (ITCS '23).

Our result also implies a conjecture of Sherif (Ph.D. thesis) that the $\gamma_2$ $γ_{2}$ norm of the Integer Inner Product function (IIP) in dimension 3 orhigher is exponential in its input size.