[Colloquium] Kulkarni/Dissertation Defense/Apr 26, 2010

[Margaret Jaffey]

       Department of Computer Science/The University of Chicago

                     *** Dissertation Defense ***


Candidate:  Raghav Kulkarni

Date:  Monday, April 26, 2010

Time:  3:00 PM

Place:  Ryerson 251

Title: Topics in Theoretical Computer Science: Counting, Evasiveness,
and Isolation

Abstract:
We present results in three different topics of Theoretical Computer
Science, namely Complexity of Counting, Decision Tree Complexity, and
Derandomization of the Isolation Lemma (in restricted cases) via
Planarity.

We will present one representative result from each topic:

(Counting) Permanent mod $2^k$ is as easy as Determinant mod $2^k.$
More specifically, for any fixed $k,$ Permanent mod $2^k$ is complete
for $\oplus L$ (parity L).

(Evasiveness) Any monotone property of sparse graphs is evasive, i.e.,
one must query all the edges in worst case.

(Isolation) Efficient deterministic Isolation for bipartite planar
graphs is possible whereas the same for non-bipartite planar graphs
would have non-trivial consequences.

Raghav's advisor is Prof. Janos Simon

Login to the Computer Science Department website for details,
including a draft copy of the dissertation:

 https://www.cs.uchicago.edu/phd/phd_announcements#raghav

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