.png){kind=icon}
.png){kind=icon}
Return
Average-Case Rigidity Lower Bounds
.png){kind=icon}
PRE
AI
DOI：10.1007/s00224-026-10268-9.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
It is shown that there exists f: {0,1)(n/2)& times; {0, 1)(n/2) -> {0, 1) in E(NP )such that for every 2(n/2 )& times; 2(n/2) matrix M of rank <= rho we have P-x,P- y[ f (x, y) not equal M-x,M- y] >= 1/2 - 2(-Omega(k)), whenever log rho <= delta n/k(logn+k) for a sufficiently small delta > 0, and n is large enough. This generalizes recent results which bound below the probability by 1/2 - Omega(1) or to constant circuits.
Keywords:
Average-case lower bounds
Matrix rigidity
Correlation bounds