Scholarlink

<p>Motivated by questions concerning the multilinear and homogeneous complexity of the elementary symmetric polynomials, we prove the following results: We first show that by making small modifications to the nonzero coefficients of the degree-<i>K</i>, <i>N</i>-variate elementary symmetric polynomial <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\sigma _{N,K}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>σ</mi> <mrow> <mi>N</mi> <mo>,</mo> <mi>K</mi> </mrow> </msub> </math></EquationSource> </InlineEquation>, one obtains a polynomial that can be computed by a monotone formula of size <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(K^{O(\log K)} \cdot N\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mi>K</mi> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mo>log</mo> <mi>K</mi> <mo stretchy="false">)</mo> </mrow> </msup> <mo>·</mo> <mi>N</mi> </mrow> </math></EquationSource> </InlineEquation>. As a corollary, we show that the result of (Raz <CitationRef CitationID="CR25">2013</CitationRef>) concerning the homogenization of algebraic multilinear or monotone formulas is tight. Another corollary is that the monotone bounded rigidity of the inclusion matrix between <i>K</i>-subsets and <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(N-K\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>N</mi> <mo>-</mo> <mi>K</mi> </mrow> </math></EquationSource> </InlineEquation> subsets of a universe of size <i>N</i> is small.</p>

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

On Approximate Symmetric Polynomials and Tightness of Homogenization Results

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年5月7日

查看全文
  • Amir Shpilka

摘要

Motivated by questions concerning the multilinear and homogeneous complexity of the elementary symmetric polynomials, we prove the following results: We first show that by making small modifications to the nonzero coefficients of the degree-K, N-variate elementary symmetric polynomial \(\sigma _{N,K}\) σ N , K , one obtains a polynomial that can be computed by a monotone formula of size \(K^{O(\log K)} \cdot N\) K O ( log K ) · N . As a corollary, we show that the result of (Raz 2013) concerning the homogenization of algebraic multilinear or monotone formulas is tight. Another corollary is that the monotone bounded rigidity of the inclusion matrix between K-subsets and \(N-K\) N - K subsets of a universe of size N is small.