The structure of almost linear Boolean functions

The structure of almost linear Boolean functions

-
Yuval Filmus , IAS
Fine Hall 224

A Boolean function f: {0,1}^n -> {0,1} is "linear" if it is a linear combination of its inputs. It is a simple exercise to show that a linear Boolean function depends on at most one coordinate. Friedgut, Kalai and Naor showed that if f is "almost" linear then it is "close" to a function depending on at most one coordinate. We consider generalizations of their result to functions on S_n and on the Johnson association scheme.   Joint work with David Ellis and Ehud Friedgut.