Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism

A function f: 1,1n 1,1 is a k-junta if it depends on at most k of its variables. We consider the problem of tolerant testing of k-juntas, where the testing algorithm must accept any function that i...