Testing Juntas: A Brief Survey

摘要

A function on n variables is called a k-junta if it depends on at most k of its variables. In this survey, we review three recent algorithms for testing k-juntas with few queries.