***********************************
                * Princeton Discrete Math Seminar *
                ***********************************

Date: Thursday 24th April, 4:30 in Fine Hall 224.
 
Speaker: Yuval Filmus (IAS)

Title: The structure of almost linear Boolean functions

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.

                       -----------

Next week: Jacob Fox

Anyone wishing to be added to or removed from this mailing list should
contact Paul Seymour (pds@math.princeton.edu)