Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with UP:
TR18-050 | 15th March 2018
Irit Dinur, Oded Goldreich, Tom Gur

Every set in P is strongly testable under a suitable encoding

We show that every set in $\cal P$ is strongly testable under a suitable encoding. By ``strongly testable'' we mean having a (proximity oblivious) tester that makes a constant number of queries and rejects with probability that is proportional to the distance of the tested object from the property. By ... more >>>

ISSN 1433-8092 | Imprint