Prefer a chat interface with context about you and your work?
Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism
A function f :{ −1,1} n → { −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 is ε- close to some k -junta and …