Scholarlink

<p>Given a non-negative real matrix <i>M</i> of non-negative rank at least <i>r</i>, can we witness this fact by a small submatrix of <i>M</i>? While Moitra (SIAM J. Comput. 2013) proved that this cannot be achieved exactly, we show that such a witnessing is possible approximately: An <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(m\times n\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>m</mi> <mo>×</mo> <mi>n</mi> </mrow> </math></EquationSource> </InlineEquation> matrix of non-negative rank <i>r</i> always contains a submatrix with at most <i>r</i><sup>3</sup> rows and columns with non-negative rank at least <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(\Omega(\frac{r}{\log n\log m})\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Ω</mi> <mo stretchy="false">(</mo> <mfrac> <mi>r</mi> <mrow> <mo>log</mo> <mi>n</mi> <mo>log</mo> <mi>m</mi> </mrow> </mfrac> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>. A similar result is proved for the 1-partition number of a Boolean matrix and, consequently, also for its two-player deterministic communication complexity. Tightness of the latter estimate is closely related to the log-rank conjecture of Lovász and Saks. </p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Hard submatrices for non-negative rank and communication complexity

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年8月13日

查看全文
  • Pavel Hrubeš

摘要

Given a non-negative real matrix M of non-negative rank at least r, can we witness this fact by a small submatrix of M? While Moitra (SIAM J. Comput. 2013) proved that this cannot be achieved exactly, we show that such a witnessing is possible approximately: An \(m\times n\) m × n matrix of non-negative rank r always contains a submatrix with at most r3 rows and columns with non-negative rank at least \(\Omega(\frac{r}{\log n\log m})\) Ω ( r log n log m ) . A similar result is proved for the 1-partition number of a Boolean matrix and, consequently, also for its two-player deterministic communication complexity. Tightness of the latter estimate is closely related to the log-rank conjecture of Lovász and Saks.