Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > ASSIGNMENT TESTERS:
Reports tagged with Assignment Testers:
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