Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Tolerant Property Testing:
TR18-195 | 18th November 2018
Sofya Raskhodnikova, Noga Ron-Zewi, Nithin Varma

Erasures versus Errors in Local Decoding and Property Testing

We initiate the study of the role of erasures in local decoding and use our understanding to prove a separation between erasure-resilient and tolerant property testing. Local decoding in the presence of errors has been extensively studied, but has not been considered explicitly in the presence of erasures.

Motivated by ... more >>>

TR20-149 | 29th September 2020
Oded Goldreich, Avi Wigderson

Robustly Self-Ordered Graphs: Constructions and Applications to Property Testing

A graph $G$ is called {\em self-ordered}\/ (a.k.a asymmetric) if the identity permutation is its only automorphism.
Equivalently, there is a unique isomorphism from $G$ to any graph that is isomorphic to $G$.
We say that $G=(V,E)$ is {\em robustly self-ordered}\/ if the size of the symmetric difference ... more >>>

ISSN 1433-8092 | Imprint