Average-Case Rigidity Lower Bounds
Xuangui Huang, Emanuele Viola · Lecture notes in computer science · 2021
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{ e } \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