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

[Margaret Jaffey]

This is a reminder about Sourav Chakraborty's Dissertation Defense  
tomorrow.  This note includes a revised abstract.


			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:
In this thesis we study various models of query complexity. A query
algorithm computes a function under the restriction that the input
can be accessed only by making probes to the the bits of the input.
The query complexity of a function $f$ is the minimum number of
probes made by any query algorithm that computes $f$. In this
thesis, we consider three different models of query complexity, (1)
deterministic decision tree complexity (query complexity when the
underlying algorithm is deterministic), (2) approximate decision
tree complexity aka. property testing (query complexity when the
underlying algorithm is probabilistic and only expected to
"approximately" compute $f$) and quantum query complexity (query
complexity when the underlying algorithm is allowed to make quantum
queries).

The main results in this thesis are:

(1) We study the relation between deterministic decision tree
complexity and other combinatorial measures of complexity measures
like sensitivity and block sensitivity. We prove that for
minterm-transitive functions the sensitivity is quadratically
related to block sensitivity which is polynomially related to
deterministic decision tree complexity.

(2) In the context of property testing we obtain the following two
results:

(2a) Given two binary strings of length $n$ and a primitive group $G
\subseteq Sym(n)$ we prove that the query complexity for testing
isomorphism of strings under the group action is
$\wti{\Theta}(\sqrt{n\log|G|})$ or $\wti{\Theta}(\log|G|)$ depending
on whether we have to query both or only one string.

(2b) Given an undirected graph $G$ and a pair of vertices $s$ and $t$
in $G$, we design a tester that tests whether there is a directed
path from $s$ to $t$ by querying the orientation of at most a
constant number of edges.

(3) We study quantum query complexity in the context of database
search algorithms. Given $f:[n] \to {0,1}$ with $|f^{-1}(0)| =
\epsilon n$, we design an quantum algorithm that make only $t$
quantum queries to $f$ and outputs a member of $f^{-1}(1)$ with
probability at least $(1-\epsilon^{2t+1})$. We prove that the error
reduction achieved is tight.

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
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=