Sourav Chakraborty

I am an Assistant Professor in the Computer Science Group at the Chennai Mathematical Institute, Chennai, India. Before this I was a postdoc at the Algorithms and Complexity department of CWI, Amsterdam, netherlands from September 2009 to August 2010. From October 2008 to August 2009 I was a postdoc at the Computer Science Department in Technion, Israel. In June 2008 I finished my Phd in Computer Science from University of Chicago under the supervision of Prof. László Babai. I received my Master's degree in Computer Science in March 2005 from University of Chicago and my Bachelor's degree in Mathematics in August 2003 from Chennai Mathematical Institute, India.

My field of research is Theoretical Computer Science. My focus has been in the classical and quantum complexity of Boolean functions (including property testing, sensitivity and block sensitivity of Boolean functions and quantum database search), in electronic commerce, in graph algorithms and in coding theory.

My Curriculum Vitae [ps], [pdf] and my Research Statement [ps], [pdf]

Thesis

- Phd Thesis: "Models of Query Complexity for Boolean Functions." [ps][pdf]

- Master's Thesis: "Sensitivity, Block Sensitivity and Certificate Complexity of Boolean Functions." [ps][pdf]

Journal Papers

-  "Property Testing of Equivalence under a Permutation Group Action" [ps][pdf]
Joint work with László Babai.
To appear in The ACM Transactions on Computation Theory (ToCT). Online version is available at ECCC .

-  "Hardness and Algorithms for Rainbow Connectivity" [ps][pdf]
Joint work with Eldar Fischer, Arie Matsliah and Raphael Yuster.
To appear in the Journal of Combinatorial Optimization (JOCO).

Conference Papers

-  "Cycle Detection, Order Finding and Discrete Log with Jumps"
Joint work with David García-Soriano and Arie Matsliah.
Innovations in Computer Science (ICS 2011).

-  "Query Complexity Lower Bounds for Reconstruction of Codes"
Joint work with Eldar Fischer and Arie Matsliah.
Innovations in Computer Science (ICS 2011).

-  "Tight Bounds for Testing Function Isomorphism."
Joint work with David García-Soriano and Arie Matsliah.
ACM-SIAM Symposium on Discrete Algorithms (SODA 2011).

-  "Market Clearance Pricing in a Metric"
Joint work with Nikhil Devanur and Chinmay Karande.
WINE 2010.

-  "Quantum Query Complexity for Testing Distribution" [ps][pdf]
Joint work with Eldar Fischer, Arie Matsliah and Ronald de Wolf.
30th International Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010).

-  "Monotonicity Testing and Shortest-Path Routing on the cube"
Joint work with Jop Briët, David García-Soriano and Arie Matsliah.
14th International Workshop on Randomization and Computation (RANDOM 2010).

-  "Two-phase algorithms for the parametric shortest path problem" [ps][pdf]
Joint work with Eldar Fischer, Oded Lachish and Raphael Yuster.
27th International Symposium on Theoretical Aspects of Computer Science (STACS'10).

-  "Improved Algorithms for Multi-unit Auction with unknown supplies" [ps][pdf]
Joint work with Nikhil Devanur.
WINE 2009. Preliminary version appeared at the Forth Workshop on Ad Auctions 2008.

-  "Hardness and Algorithms for Rainbow Connectivity" [ps][pdf]
Joint work with Eldar Fischer, Arie Matsliah and Raphael Yuster.
26th International Symposium on Theoretical Aspects of Computer Science (STACS'09), Pages 243-254.

-  "Testing st-Connectivity" [ps][pdf]
Joint work with Eldar Fischer, Oded Lachish, Arie Matsliah and Ilan Newman.
11th International Workshop on Randomization and Computation (RANDOM 2007), Pages 380-394.

-  "Zero-error list decoding capacity of the q/(q-1) channel" [ps][pdf]
Joint work with Jaikumar Radhakrishnan, Nandakumar Raghunathan and Prashant Sasatte.
26th International Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2006), Pages 129-138.

-  "Bounds for Error Reduction with Few Quantum Queries" [ps][pdf]
Joint work with Jaikumar Radhakrishnan and Nandakumar Raghunathan.
9th International Workshop on Randomization and Computation (RANDOM 2005), Pages 245-256.

-  "On the Sensitivity of Cyclically-Invariant Functions" [ps][pdf]
20th Annual IEEE Conference on Computational Complexity (CCC 2005), Pages 163-167.

Un-refereed Papers and Other Works

-  "Testing by Implicit Learning with Fewer Queries"
Joint work with Jop Briët, David García-Soriano and Arie Matsliah.
In preparation.

-  "Constant Query Locally Decodable Codes against a Computationally Bounded Adversary"
Joint work with Rishiraj Bhatyacharyya.
In preparation.

-  "Popular Matching"
Joint work with Varsha Dani.
In preparation.

-  "Point Set Topological Proof of the `no-retraction' Theorem for 2 and 3 dimentional Cases" [ps][pdf]
Resonance, journal of science education, Vol 8, No.~10, Pages 63-68.