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.
See: http://math.rutgers.edu/seminars/allseminars.php?sem_name=Discrete%20Math