Average-case rigidity lower bounds

摘要

It is shown that there exists f : {0, 1} n/2 × {0, 1} n/2 → {0, 1} in ENP such that for every 2n/2 × 2 n/2 matrix M of rank ≤ ρ we have Px,y[f(x, y) 6= Mx,y] ≥ 1/2 ? 2 ??(k) , where k ≤ Θ(√ n) and log ρ ≤ δn/k(log n k) for a sufficiently small δ 0. This generalizes recent results which bound below the probability by 1/2??(1) or apply to constant-depth circuits. The result is a step towards obtaining data-structure lower bounds for ENP: they would follow from a better trade-off between the probability bound and ρ.