文章基本信息

标题：Average-case rigidity lower bounds
本地全文：下载
作者：Xuangui Huang ; Emanuele Viola
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2020
卷号：2020
页码：1-18
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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 ρ.