Abstract:
A $(n,k)$-junta is a Boolean function of $n$ variables that depends on at most $k$ of these variables. The task of determining whether a given Boolean function is a $k$-junta and finding these $n-k$ unessential variables is common in machine learning (irrelevant feature reduction) and electronic circuit design (fictitious variable reduction). A natural extension of this idea, which is commonly found in these and other areas, for example, in game theory, is the notion of a variable with little influence on the results of a function's calculation. Of particular interest is the issue of whether insignificant or low-impact variables are considered individually or as an ensemble. The computational efficiency of solving these problems is of significant relevance for practical applications. This depends, in particular, on the representation of the boolean function employed. In this paper Boolean functions are specified by complete or partial truth tables (sample datasets). This paper presents two poly-time algorithms for finding juntas, as well as discussing the case where we approximate a given function making low-impact variables entirely unessential.
Fulltext:
PDF file (319 kB)
First page:
PDF file