Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > DOUBLY-SUBLINEAR:
Reports tagged with doubly-sublinear:
TR25-105 | 29th July 2025
Oded Goldreich, Guy Rothblum

Location-Invariant Properties of Functions versus Properties of Distributions: United in Testing but Separated in Verification

A property of functions is called location-invariant (or symmetric) if it can be characterized in terms of the frequencies in which each value occurs in the function, regardless of the locations in which each value occurs.
It is known that the (query) complexity of testing location-invariant properties of functions ... more >>>




ISSN 1433-8092 | Imprint