<p>It is shown that there exists <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\varvec{f}\varvec{:} \varvec{\{}\varvec{0}\varvec{,}\varvec{1}\varvec{\}}^{\varvec{n/2}} \varvec{\times } \varvec{\{0,1\}}^{\varvec{n/2}} \varvec{\rightarrow } \varvec{\{0,1\}}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mi mathvariant="bold-italic">f</mi> </mrow> <mrow> <mo mathvariant="bold">:</mo> </mrow> <mrow> <mo mathvariant="bold" stretchy="false">{</mo> </mrow> <mrow> <mn mathvariant="bold">0</mn> </mrow> <mrow> <mo mathvariant="bold">,</mo> </mrow> <mrow> <mn mathvariant="bold">1</mn> </mrow> <msup> <mrow> <mo mathvariant="bold" stretchy="false">}</mo> </mrow> <mrow> <mi mathvariant="bold-italic">n</mi> <mo mathvariant="bold" stretchy="false">/</mo> <mn mathvariant="bold">2</mn> </mrow> </msup> <mrow> <mo mathvariant="bold">×</mo> </mrow> <msup> <mrow> <mo mathvariant="bold" stretchy="false">{</mo> <mn mathvariant="bold">0</mn> <mo mathvariant="bold">,</mo> <mn mathvariant="bold">1</mn> <mo mathvariant="bold" stretchy="false">}</mo> </mrow> <mrow> <mi mathvariant="bold-italic">n</mi> <mo mathvariant="bold" stretchy="false">/</mo> <mn mathvariant="bold">2</mn> </mrow> </msup> <mrow> <mo mathvariant="bold">→</mo> </mrow> <mrow> <mo mathvariant="bold" stretchy="false">{</mo> <mn mathvariant="bold">0</mn> <mo mathvariant="bold">,</mo> <mn mathvariant="bold">1</mn> <mo mathvariant="bold" stretchy="false">}</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> in E<InlineEquation ID="IEq2"> <EquationSource Format="TEX">$^\textbf{NP}$</EquationSource> <EquationSource Format="MATHML"><math> <mmultiscripts> <mrow /> <mrow /> <mi mathvariant="bold">NP</mi> </mmultiscripts> </math></EquationSource> </InlineEquation> such that for every <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\varvec{2}^{\varvec{n/2}} \varvec{\times } \varvec{2}^{\varvec{n/2}}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mrow> <mn mathvariant="bold">2</mn> </mrow> <mrow> <mi mathvariant="bold-italic">n</mi> <mo mathvariant="bold" stretchy="false">/</mo> <mn mathvariant="bold">2</mn> </mrow> </msup> <mrow> <mo mathvariant="bold">×</mo> </mrow> <msup> <mrow> <mn mathvariant="bold">2</mn> </mrow> <mrow> <mi mathvariant="bold-italic">n</mi> <mo mathvariant="bold" stretchy="false">/</mo> <mn mathvariant="bold">2</mn> </mrow> </msup> </mrow> </math></EquationSource> </InlineEquation> matrix <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$\varvec{M}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="bold-italic">M</mi> </mrow> </math></EquationSource> </InlineEquation> of rank <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$\varvec{\le } \varvec{\rho }$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mo mathvariant="bold">≤</mo> </mrow> <mrow> <mi mathvariant="bold-italic">ρ</mi> </mrow> </mrow> </math></EquationSource> </InlineEquation> we have <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$\mathbb {P}_{\varvec{x,y}}\varvec{[}\varvec{f}\varvec{(x,y)}\varvec{\ne } \varvec{M}_{\varvec{x,y}}\varvec{]} \varvec{\ge } \varvec{1/2-2}^{\varvec{-\Omega }\varvec{(k)}}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi mathvariant="double-struck">P</mi> <mrow> <mi mathvariant="bold-italic">x</mi> <mo mathvariant="bold">,</mo> <mi mathvariant="bold-italic">y</mi> </mrow> </msub> <mrow> <mo mathvariant="bold" stretchy="false">[</mo> </mrow> <mrow> <mi mathvariant="bold-italic">f</mi> </mrow> <mrow> <mo mathvariant="bold" stretchy="false">(</mo> <mi mathvariant="bold-italic">x</mi> <mo mathvariant="bold">,</mo> <mi mathvariant="bold-italic">y</mi> <mo mathvariant="bold" stretchy="false">)</mo> </mrow> <mrow> <mo mathvariant="bold">≠</mo> </mrow> <msub> <mrow> <mi mathvariant="bold-italic">M</mi> </mrow> <mrow> <mi mathvariant="bold-italic">x</mi> <mo mathvariant="bold">,</mo> <mi mathvariant="bold-italic">y</mi> </mrow> </msub> <mrow> <mo mathvariant="bold" stretchy="false">]</mo> </mrow> <mrow> <mo mathvariant="bold">≥</mo> </mrow> <msup> <mrow> <mn mathvariant="bold">1</mn> <mo mathvariant="bold" stretchy="false">/</mo> <mn mathvariant="bold">2</mn> <mo mathvariant="bold">-</mo> <mn mathvariant="bold">2</mn> </mrow> <mrow> <mrow> <mo mathvariant="bold">-</mo> <mi mathvariant="bold">Ω</mi> </mrow> <mrow> <mo mathvariant="bold" stretchy="false">(</mo> <mi mathvariant="bold-italic">k</mi> <mo mathvariant="bold" stretchy="false">)</mo> </mrow> </mrow> </msup> </mrow> </math></EquationSource> </InlineEquation>, whenever <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$\varvec{\log } \varvec{\rho } \varvec{\le } \varvec{\delta } \varvec{n/k}\varvec{(}\varvec{\log } \varvec{n} \varvec{+} \varvec{k}\varvec{)}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mo mathvariant="bold">log</mo> </mrow> <mrow> <mi mathvariant="bold-italic">ρ</mi> </mrow> <mrow> <mo mathvariant="bold">≤</mo> </mrow> <mrow> <mi mathvariant="bold-italic">δ</mi> </mrow> <mrow> <mi mathvariant="bold-italic">n</mi> <mo mathvariant="bold" stretchy="false">/</mo> <mi mathvariant="bold-italic">k</mi> </mrow> <mrow> <mo mathvariant="bold" stretchy="false">(</mo> </mrow> <mrow> <mo mathvariant="bold">log</mo> </mrow> <mrow> <mi mathvariant="bold-italic">n</mi> </mrow> <mrow> <mo mathvariant="bold">+</mo> </mrow> <mrow> <mi mathvariant="bold-italic">k</mi> </mrow> <mrow> <mo mathvariant="bold" stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> for a sufficiently small <InlineEquation ID="IEq8"> <EquationSource Format="TEX">$\varvec{\delta } \varvec{>} \varvec{0}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mi mathvariant="bold-italic">δ</mi> </mrow> <mrow> <mo mathvariant="bold">></mo> </mrow> <mrow> <mn mathvariant="bold">0</mn> </mrow> </mrow> </math></EquationSource> </InlineEquation>, and <InlineEquation ID="IEq9"> <EquationSource Format="TEX">$\varvec{n}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="bold-italic">n</mi> </mrow> </math></EquationSource> </InlineEquation> is large enough. This generalizes recent results which bound below the probability by <InlineEquation ID="IEq10"> <EquationSource Format="TEX">$\varvec{1/2-\Omega }\varvec{(1)}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mn mathvariant="bold">1</mn> <mo mathvariant="bold" stretchy="false">/</mo> <mn mathvariant="bold">2</mn> <mo mathvariant="bold">-</mo> <mi mathvariant="bold">Ω</mi> </mrow> <mrow> <mo mathvariant="bold" stretchy="false">(</mo> <mn mathvariant="bold">1</mn> <mo mathvariant="bold" stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> or apply to constant-depth circuits.</p>

Average-Case Rigidity Lower Bounds

期刊论文
出版模式：

开放获取
发表日期：

2026年5月1日

查看全文

Xuangui Huang,
Emanuele Viola

摘要

It is shown that there exists $\varvec{f}\varvec{:} \varvec{\{}\varvec{0}\varvec{,}\varvec{1}\varvec{\}}^{\varvec{n/2}} \varvec{\times } \varvec{\{0,1\}}^{\varvec{n/2}} \varvec{\rightarrow } \varvec{\{0,1\}}$ $f : {0, 1}^{n / 2} \times {0, 1}^{n / 2} \to {0, 1}$ in E $^\textbf{NP}$ $^{NP}$ such that for every $\varvec{2}^{\varvec{n/2}} \varvec{\times } \varvec{2}^{\varvec{n/2}}$ $2^{n / 2} \times 2^{n / 2}$ matrix $\varvec{M}$ $M$ of rank $\varvec{\le } \varvec{\rho }$ $\leq ρ$ we have $\mathbb {P}_{\varvec{x,y}}\varvec{[}\varvec{f}\varvec{(x,y)}\varvec{\ne } \varvec{M}_{\varvec{x,y}}\varvec{]} \varvec{\ge } \varvec{1/2-2}^{\varvec{-\Omega }\varvec{(k)}}$ $P_{x, y} [f (x, y) \neq M_{x, y}] \geq {1 / 2 - 2}^{- Ω (k)}$ , whenever $\varvec{\log } \varvec{\rho } \varvec{\le } \varvec{\delta } \varvec{n/k}\varvec{(}\varvec{\log } \varvec{n} \varvec{+} \varvec{k}\varvec{)}$ $log ρ \leq δ n / k (log n + k)$ for a sufficiently small $\varvec{\delta } \varvec{>} \varvec{0}$ $δ > 0$ , and $\varvec{n}$ $n$ is large enough. This generalizes recent results which bound below the probability by $\varvec{1/2-\Omega }\varvec{(1)}$ $1 / 2 - Ω (1)$ or apply to constant-depth circuits.