One of the main goals of theoretical computer science as a field of study is to establish the limitations of various models of computation. In general, such limitations are useful both for the purpose of guiding algorithmic design, and for the purpose of creating cryptographic schemes that are provably secure against certain adversaries. Communication complexity is a theoretical tool for establishing such limitations, and it has found applications in a surprisingly wide variety of other areas of computer science, such as VLSI design, Turing Machine and circuit complexity, pseudorandomness, data structures, streaming, and game theory. My main research interests are in the area of communication complexity and its applications to various models of computation.
Other areas of theoretical computer science that I find particularly appealing and that I would like to investigate include information theory, derandomization, streaming, and game theory.
Journal Publications:
Conference Publications:
(links point to journal/extended versions)
The subject of my PhD thesis is directly reflected in its title, Multiparty Communication Complexity. Two of the main contributions in this thesis deal with the relative powers of determinism, randomization, and nondeterminism, in the powerful Number-On-Forehead communication model. The third main contribution is a new application of the Number-In-Hand communication model to a new measure characterizing the amount of randomness used by a polynomial time probabilistic algorithm.
I am in the process of writing up my thesis, and I expect to complete the requirements for my PhD degree by June 2009. My PhD supervisor is Professor Toniann Pitassi.
The area of my MSc thesis is the theory of distributed computing. A shared-memory distributed system provides some basic object types (e.g., Register, Test&Set, Swap). Different systems might provide different basic object types, and an important theoretical and fundamental problem in distributed computing is to identify what object types can be used to implement other object types. Herlihy's consensus hierarchy partially solves this problem, yet there are basic questions that are left open. In this context, a famous conjecture states that it is impossible to implement a Queue object type using the Register and Test&Set object types. In my MSc thesis, I make progress towards proving this conjecture, but the conjecture remains open.
I have completed my MSc degree in 2004 under the supervision of Professor Faith Ellen.
My MSc thesis is available here: