Specialists from the Apple Machine Learning Research division presented a work dedicated to analyzing location-invariant properties of functions. Such properties, also called symmetric, are defined exclusively by the frequency of occurrence of values in a function, regardless of the specific positions where these values are located.
In previously known studies, it was established that the query complexity for testing such function properties is closely related to the sample complexity for testing corresponding distribution properties. However, the authors of the new work emphasize that this robust interconnection does not hold when transitioning to verification tasks.
The main conclusion of the study points to a fundamental difference between testing and verification processes in this domain. What united approaches to functions and distributions at the testing stage proves to be separated when it comes to confirming property correctness.
editorial commentary
Why it matters
A likely consequence will be the emergence of new research directions focusing exclusively on verification complexity, separate from testing. The next observable signal will be attempts by other research groups to reproduce this result or find counterexamples. The material uncertainty lies in how wide this gap is in real-world applied tasks, not only in theoretical models.