[Colloquium] Start time of 3:30: Chakraborty's M.S. Presentation Today

[Margaret Jaffey]

The start time for Sourav Chakraborty's MS Presentation this afternoon 
has been changed to 3:30 (3:00 was the former start time).
---------------
Date:  Wednesday, February 16, 2005

Time:  3:30 p.m. (revised start time)

Place:  Ryerson 251

M.S. Candidate:  Sourav Chakraborty

M.S. Paper Title:  Sensitivity, Block Sensitivity and Certificate 
Complexity
of Boolean Functions: A Survey

Abstract:
We discuss several complexity measures for Boolean functions:
sensitivity, block sensitivity, $\ell$-block sensitivity,
certificate complexity, average sensitivity and average block
sensitivity.  We survey various known bounds for these measures
and relations between these measures for different classes of
functions. The problem of finding tight bounds for these measures
and finding tight relations among these measures have recieved a lot of
attention. For a general Boolean function our understanding of these
measures are still very limited. Many of the relations that we
have seems to be far from being tight. For example, the best known
upper bound on block sensitivity in terms of sensitivity is
exponential while the largest known gap is quadratic.

For small classes of functions (like functions with certain amount of
symmetries) our understanding is much better. In this survey we discuss
how the various measures perform on these classes of
functions. The classes of functions we discuss are
monotone functions, symmetric functions, graph properties,
functions closed under some transitive group action and
minterm-transitive functions. For monotone functions and symmetric
functions we have quite a clear understanding of the measures. For
graph properties we have almost tight bounds. In this
survey we look at $k$-uniform-hyper-graph properties and try to prove
similar bounds. Minterm-transitive functions were defined
as a class of very simple functions closed under
transitive group actions. For this class of functions some tight bounds
were proved. Using similar techniques we try to prove
similar tight bounds for functions invariant under some transitive group
action.

Most of these measures were initially defined to give nice bounds
for the decision tree complexity for various models of
computation. So we also present a short survey on how these measures
are related to decision tree complexity for deterministic, randomized 
and
quantum model.

Advisor:  Prof. Laszlo Babai

A draft copy of Sourav Chakraborty's MS Paper is available in Ry 161A.


-- 
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Margaret P. Jaffey				margaret at cs.uchicago.edu
Department of Computer Science
Student Support Rep (Ry 161A)		(773) 702-6011
The University of Chicago		http://www.cs.uchicago.edu
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-