[Colloquium] Chakraborty/Dissertation Defense/4-15-08

[Margaret Jaffey]

This is a reminder about Sourav Chakraborty's Dissertation Defense on  
Tuesday.  Please note that the title of his dissertation has changed  
(the revised title is shown in the announcement below).


			Department of Computer Science/The University of Chicago

					*** Dissertation Defense ***


Candidate:  Sourav Chakraborty

Date:  Tuesday, April 15, 2008

Time and Location:  1:30 p.m. in Ryerson 251

Title:  Models of Query Complexity for Boolean Functions

Abstract:
Query algorithms computes $f(x)$ by accessing the input $x$ through
queries it is allowed to make to the input. The decision tree
complexity of $f$ is the number of queries the best query algorithm
makes for computing $f$. There are various models of query
algorithms. For example the algorithm can be deterministic or
randomized or the algorithm can make quantum queries. In this thesis
we study the decision tree complexity for various functions in
various models of query algorithms.

In order to understand the complexity of Boolean functions
theoretical computer scientist have introduced various measures on
Boolean functions.  Sensitivity, block sensitivity, certificate
complexity, degree of representing polynomial and approximate
polynomial are some examples. These measures are related to other
important measures of complexities like decision tree complexity for
various models of computation, circuit complexity, parallel
computing, communication complexity and the construction of oracles
in computational complexity.  We study some of these measures of
certain Boolean functions and how they relate to decsion tree complexity
for various models of query algorithm.

We focus on sensitivity and block sensitivity of Boolean functions,  
approximate
decision tree complexity (or Property Testig) for certain graph  
properties
and their generalizations. We also obtain tight bounds on error
reduction in quantum database  search when only a few queries to the  
database
is allowed.

Candidate's Advisor:  Prof. Laszlo Babai

A draft copy of Mr. Chakraborty's dissertation is available in Ry 156.

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