Sourav Chakraborty

I am an Associate Professor in the Computer Science Group at the Chennai Mathematical Institute, Chennai, India. Before joining CMI as an Assistant Professor in September 2010 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]

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

-  "Testing Uniformity of Stationary Distribution" [ps][pdf]
Joint work with Akshay Kamath and Rameshwar Pratap.
In Information Processing Letters.

-  "Upper Bounds on Fourier Entropy" [ps][pdf]
Joint work with Raghav Kulkarni, Satyanarayana V. Lokam and Nitin Saurabh.
In Theoretical Computer Science.

-  "On the power of conditional samples in distribution testing" [ps][pdf]
Joint work with Eldar Fischer, Yonatan Goldhirsh and Arie Matsliah.
In SIAM Journal of Computing.

-  "Query Complexity Lower Bounds for Reconstruction of Codes." [ps][pdf]
Joint work with Eldar Fischer and Arie Matsliah.
In Theory of Computing.

-  "Nearly Tight Bounds for Testing Function Isomorphism" [ps][pdf]
Joint work with Noga Alon, Eric Blais, David García-Soriano and Arie Matsliah.
In SIAM Journal on Computing.

-  "On the Sensitivity of Cyclically-Invariant Functions" [ps][pdf]
In journal of Discrete Mathematics and Theoretical Computer Science (special issue celebrating Laci Babai's 60th birthday).

-  "Monotonicity Testing and Shortest-Path Routing on the cube" [ps][pdf]
Joint work with Jop Briët, David García-Soriano and Arie Matsliah.
In Combinatorica.

-  "Property Testing of Equivalence under a Permutation Group Action" [ps][pdf]
Joint work with László Babai.
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.
In the Journal of Combinatorial Optimization (JOCO).

Conference Papers

-  "Maximal and Maximum Transitive Relation Contained in a Given Binary Relation" [ps][pdf]
Joint work with Shamik Ghosh, Nitesh Jha and Sasanka Roy.
International Computing and Combinatorics Conference (COCOON'15).

-  "Upper Bounds on Fourier Entropy" [ps][pdf]
Joint work with Raghav Kulkarni, Satyanarayana V. Lokam and Nitin Saurabh.
International Computing and Combinatorics Conference (COCOON'15).

-  "Counting Popular Matchings in House Allocation Problems" [ps][pdf]
Joint work with Rupam Acharyya and Nitesh Jha.
International Computer Science Symposium in Russia (CSR 2014).

-  "Property Testing Bounds for Linear and Quadratic Functions via Parity Decision Trees" [ps][pdf]
Joint work with Abhishek Bhrushundi and Raghav Kulkarni.
International Computer Science Symposium in Russia (CSR 2014).

-  "Helly-Type Theorems in Property Testing" [ps][pdf]
Joint work with Rameshwar Pratap, Sasanka Roy, Shubhangi Saraf.
Latin American Theoretical INformatics Symposium (LATIN 2014).

-  "Testing Uniformity of Stationary Distribution" [ps][pdf]
Joint work with Akshay Kamath and Rameshwar Pratap.
European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2012).
Also presented at the 12th Cologne-Twente Workshop on Graphs & Combinatorial Optimization (CTW 2013).

-  "On the Power of Conditional Samples in Distribution Testing" [ps][pdf]
Joint work with Eldar Fischer, Yonatan Goldhirsh and Arie Matsliah.
Innovations in Theoretical Computer Science (ITCS 2013).

-  "Junto-symmetric functions, hypergraph isomorphism, and crunching" [ps][pdf]
Joint work with Eldar Fischer, David García-Soriano and Arie Matsliah.
27th Annual IEEE Conference on Computational Complexity (CCC 2012).

-  "Improved Competitive Ratio for the Matroid Secretary Problem." [ps][pdf]
Joint work with Oded Lachish.
ACM-SIAM Symposium on Discrete Algorithms (SODA 2012).

-  "Testing by Implicit Learning with Fewer Queries" [ps][pdf]
Joint work with David García-Soriano and Arie Matsliah.
38th International Colloquium on Automata, Languages and Programming (ICALP 2011).

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

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

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

-  "Market Clearance Pricing in a Metric" [ps][pdf]
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" [ps][pdf]
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

-  "Constant Query Locally Decodable Codes against a Computationally Bounded Adversary" [ps][pdf]
Joint work with Rishiraj Bhatyacharyya.

-  "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.