document: Property testers for dense Constraint Satisfaction programs on finite domains Many NP-hard languages can be `` decided '' in subexponential time if the definition of `` decide '' is relaxed only slightly . Rubinfeld and Sudan introduced the notion of property testers , probabilistic algorithms that can decide , with high probability , if a function has a certain property or if it is far from any function having this property . Goldreich , Goldwasser , and Ron constructed property testers with constant query complexity for dense instances of a large class of graph problems . Since many graph problems can be viewed as special cases of the Constraint Satisfaction Problem on Boolean domains , it is natural to try to construct property testers for more general cases of the Constraint Satisfaction Problem . In this paper , we give explicit constructions of property testers using a constant number of queries for dense instances of Constraint Satisfaction Problems where the constraints have constant arity and the variables assume values in some domain of finite size
doc_bio_tags: B I O O B I O O O O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O B I O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I O B I I O B I O O O O O B I O O O B I O O O O O O O O B I O O O O O O O O O O O O B I O O O O O O B I O O O O O O O O O O O B I O O O O O O O B I O B I O O O O O O O O O O O O O O O O O O