Sublinear-Time Computation in the Presence of Online Erasures
summary
Introduces an online erasure model where after each query an adversary can hide up to t entries and proves concrete testing limits: linearity is testable with O((log T)/ε) queries and matching Ω(log T) lower bound, using a Fourier-analysis structural theorem about K-tuples; quadraticity is testable with O(1/ε) queries for constant t though with doubly-exponential dependence on t; sortedness is impossible to test even for t=1 via disjoint adjacent inversions.
AI-written summary · about