Questions tagged [property-testing]
The property-testing tag has no usage guidance.
2
questions
2
votes
1
answer
95
views
Lower bound for ϵ-tester with one-sided error for the "2-injective" property of functions
An $\epsilon$-tester given an input and a property, is defined as follows:
If the input holds the property then the tester should accept with probability at least $\frac 2 3$. Otherwise if the input ...
- 123
4
votes
2
answers
358
views
Testing the property of being a union of three disjoint cliques
Design an $\epsilon$-test for the following property in the dense graph model: $G(V,E)$ is a union of three disjoint cliques.
I've been sitting for a few hours and I don't have any idea of how to ...
- 41