Rutgers Discrete Mathematics Seminar

Title: Composition Limits and Separating Examples for some Boolean Function Complexity Measures

Speaker: Justin Gilmer, Rutgers

Date: Tuesday, April 16, 2013 2:00pm

Location: Hill Center, Room 124, Rutgers University, Busch Campus, Piscataway, NJ


Block sensitivity, bs(f), and certificate complexity, C(f), are two fundamental combinatorial measures of complexity of a boolean function f. It has long been known that bs(f) <= C(f) = O(bs(f)^2). We will discuss an infinite family of examples for which C(f) grows quadratically in bs(f), giving optimal separations between these measures. In order to analyze the complexity of this family of examples, we characterize how these measures behave under function composition. This is a joint work with Michael Saks and Srikanth Srinivasan.