Theory of Computing Systems Вычислительная теория и математика

Average-Case Rigidity Lower Bounds

Xuangui Huang, Emanuele Viola
Springer Nature · 2026-05-01 · DOI 10.1007/s00224-026-10268-9

Аннотация

Abstract 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 × { 0 , 1 } n / 2 → { 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 × 2 n / 2 matrix $$\varvec{M}$$ M of rank $$\varvec{\le } \varvec{\rho }$$ ≤ ρ 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 ) ≠ M x , y ] ≥ 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 ρ ≤ δ 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.

Читать у издателя →