On possible values of maximum relative influence of variables on threshold functions

I. V. Gribushin

Lomonosov Moscow State University

Abstract: We study a relative influence of variables on Boolean functions. We find lower and upper bounds of maximum relative influence on threshold functions of n variables. They are equal to 1/n and (2n-1- 1)/(2n-1+ n - 2). We give a partition of all threshold functions of four-dimensional space into classes depending on the maximum relative influence of variables.

Keywords: Threshold functions, influence of variables on Boolean functions, relative influence of variables on Boolean functions, tau - regular threshold functions.