Publications

Sourav Chakraborty

I am a Professor in the Advanced Computing and Microelectronics Unit (ACMU) at the Indian Statistical Institute (ISI), Kolkata. Before joining ISI, in July 2018, I was a faculty at the Chennai Mathematical Institute (CMI), Chennai, from September 2010 to June 2018. Before that 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

  1. " Disjointness through the Lens of Vapnik-Chervonenkis Dimension: Sparsity and Beyond" [ps][pdf]
    Joint work with Anup Bhattacharya, Arijit Ghosh, Gopinath Mishra and Manaswi Paraashar.
    Computational Complexity (2022).
  2. " Linear-time Recognition of Proper Tagged Probe Interval Graph " [ps][pdf]
    Joint work with Sanchita Paul, Shamik Ghosh and Malay Sen.
    Contributions to Discrete Mathematics (CDM) (2022).
  3. " Improved Bounds on Fourier Entropy and Min-Entropy " [ps][pdf]
    Joint work with Srinivasan Arunachalam, Michal Kouck, Nitin Saurabh and Ronald de Wolf.
    ACM Transactions on Computation Theory (ToCT) (2021).
  4. " Two New Results About Quantum Exact Learning " [ps][pdf]
    Joint work with Srinivasan Arunachalam, Troy Lee, Manaswi Paraashar and Ronald de Wolf.
    Quantum (2021).
  5. " The Balanced Connected Subgraph Problem " [ps][pdf]
    Joint work with Sujoy Bhore, Satyabrata Jana, Joseph S. B. Mitchell, Supantha Pandit and Sasanka Roy.
    Discrete Applied Mathematics (2021).
  6. " Helly-Type Theorems in Property Testing" [ps][pdf]
    Joint work with Rameshwar Pratap, Sasanka Roy and Subhangi Saraf.
    International Journal of Computational Geometry and Applications (IJCGA) (2018).
  7. " Property Testing of Joint Distributions using Conditional Samples" [ps][pdf]
    Joint work with Rishiraj Bhattacharyya.
    ACM Transactions on Computation Theory (ToCT) (2018).
  8. "Testing Uniformity of Stationary Distribution" [ps][pdf]
    Joint work with Akshay Kamath and Rameshwar Pratap.
    Information Processing Letters (IPL) (2016).
  9. "Upper Bounds on Fourier Entropy" [ps][pdf]
    Joint work with Raghav Kulkarni, Satyanarayana V. Lokam and Nitin Saurabh.
    Theoretical Computer Science (TCS) (2016).
  10. "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 (SICOMP) (2016).
  11. "Query Complexity Lower Bounds for Reconstruction of Codes." [ps][pdf]
    Joint work with Eldar Fischer and Arie Matsliah.
    Theory of Computing (TOC) (2014).
  12. "Nearly Tight Bounds for Testing Function Isomorphism" [ps][pdf]
    Joint work with Noga Alon, Eric Blais, David García-Soriano and Arie Matsliah.
    SIAM Journal on Computing (SICOMP) (2013).
  13. "Monotonicity Testing and Shortest-Path Routing on the cube" [ps][pdf]
    Joint work with Jop Briët, David García-Soriano and Arie Matsliah.
    Combinatorica (2012).
  14. "On the Sensitivity of Cyclically-Invariant Functions" [ps][pdf]
    Discrete Mathematics and Theoretical Computer Science (special issue celebrating Laci Babai's 60th birthday) (2011).
  15. "Hardness and Algorithms for Rainbow Connectivity" [ps][pdf]
    Joint work with Eldar Fischer, Arie Matsliah and Raphael Yuster.
    Journal of Combinatorial Optimization (JOCO) (2011).
  16. "Property Testing of Equivalence under a Permutation Group Action" [ps][pdf]
    Joint work with László Babai.
    Accepted in ACM Transactions on Computation Theory (ToCT). Online version is available at ECCC .

Conference Papers

  1. " Testing Self-Reducible Samplers. " [ps][pdf]
    Joint work with Rishiraj Bhattacharyya, Yash Pote, Uddalok Sarkar and Sayantan Sen.
    Conference on Artificial Intelligence (AAAI), 2024.
  2. " Equivalence Testing: The Power of Bounded Adaptivity. " [ps][pdf]
    Joint work with Diptarka Chakraborty, Gunjan Kumar and Kuldeep Meel.
    International Conference on Artificial Intelligence and Statistics (AISTATS), 2024.
  3. " Approximate Degree Composition for Recursive Functions. " [ps][pdf]
    Joint work with Chandrima Kayal, Rajat Mittal, Manaswi Paraashar and Nitin Saurabh.
    International Workshop Randomization and Approximation Techniques in Computer Science (RANDOM), 2024.
  4. " Improved Streaming Algorithm for the Klee's Measure Problem and Generalizations. " [ps][pdf]
    Joint work with Mridul Nandi, N.V. Vinodchandran, Arijit Ghosh, Kuldeep Meel and Soumit Pal.
    International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX), 2024.
  5. " On Fourier Analysis of Sparse Boolean Functions over Certain Abelian Groups. " [ps][pdf]
    Joint work with Swarnalipa Datta, Pranjal Dutta, Arijit Ghosh and Swagato Sanyal
    International Symposium on Mathematical Foundations of Computer Science (MFCS), 2024.
  6. "Tight Lower Bound on Equivalence Testing in Conditional Sampling Model. " [ps][pdf]
    Joint work with Diptarka Chakraborty and Gunjan Kumar
    ACM-SIAM Symposium on Discrete Algorithms (SODA), 2024.
  7. "On the Composition of Randomized Query Complexity and Approximate Degree. " [ps][pdf]
    Joint work with Chandrima Kayal, Rajat Mittal, Manaswi Paraashar, Swagato Sanyal and Nitin Saurabh
    International Conference on Randomization and Computation (RANDOM), 2023.
  8. " Testing of Index-Invariant Properties in the Huge Object Model. " [ps][pdf]
    Joint work with Eldar Fischer, Arijit Ghosh, Gopinath Misra and Sayantan Sen.
    Proceedings of the 36th Annual Conference on Learning Theory (COLT) 2023.
  9. "On simple expectations and observations of intelligent agents: A complexity study. " [ps][pdf]
    Joint work with Avijeet Ghosh, Sujata Ghosh and Francois Schwarzentruber.
    Proceedings of the 20th International Conference on Principles of Knowledge Representation and Reasoning (KR) 2023.
  10. "Engineering an Efficient Approximate DNF-Counter. " [ps][pdf]
    Joint work with Mate Soos, Divesh Aggarwal, Kuldeep S. Meel and Maciej Obremski.
    Proceedings of the 32nd International Joint Conference on Artificial Intelligence (IJCAI) 2023.
  11. "Approximate Model Counting: Is SAT Oracle More Powerful than NP Oracle? " [ps][pdf]
    Joint work with Diptarka Chakraborty, Gunjan Kumar and Kuldeep S. Meel.
    Proceedings of the 50th EATCS International Colloquium on Automata, Languages and Programming (ICALP) 2023.
  12. "Testing of Horn Samplers. " [ps][pdf]
    Joint work with Ansuman Banerjee, Shayak Chakraborty, Kuldeep S. Meel, Uddalok Sarkar and Sayantan Sen.
    Proceedings of the 26th International Conference on Artificial Intelligence and Statistics (AISTATS) 2023.
  13. " Certificate Games. " [ps][pdf]
    Joint work with Anna Gal, Sophie Laplante, Rajat Mittal and Anupa Sunny.
    Proceedings of the 14th Innovations in Theoretical Computer Science Conference (ITCS) 2023.
  14. " Estimation of the Size of Union of Delphic Sets: Achieving Independence from Stream Size. " [ps][pdf]
    Joint work with Kuldeep Meel and N.V. Vinodchandran.
    Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS) 2022.
  15. " On the computational complexity of model checking for Public Observation Logic. " [ps][pdf]
    Joint work with Avijeet Ghosh, Sujata Ghosh and Francois Schwarzentruber.
    The 31st International Joint Conference on Artificial Intelligence (IJCAI) 2022.
  16. " A Scalable t-wise Coverage Estimator. " [ps][pdf]
    Joint work with Eduard Baranov, Axel Legay, Kuldeep Meel and N.V. Vinodchandran.
    International Conference on Software Engineering (ICSE) 2022.
  17. " On Quantitative Testing of Uniform Samplers. " [ps][pdf]
    Joint work with Priyanka Golia, Kuldeep Meel and Mate Soos.
    The 28th International Conference on Principles and Practice of Constraint Programming (CP), 2022.
  18. " Separations between Combinatorial Measures for Transitive Functions. " [ps][pdf]
    Joint work with Chandrima Kayal and Manaswi Paraashar.
    The 49th International Colloquium on Automata, Languages and Programming (ICALP), 2022.
  19. " Exploring the Gap between Tolerant and Non-tolerant Distribution Testing. " [ps][pdf]
    Joint work with Eldar Fischer, Arijit Ghosh, Gopinath Mishra and Sayantan Sen.
    International Conference on Randomization and Computation (RANDOM), 2022.
  20. " Symmetry and Quantum Query-To-Communication Simulation. " [ps][pdf]
    Joint work with Arkadev Chattopadhyay, Peter Hoyer, Nikhil S. Mande, Manaswi Paraashar and Ronald de Wolf.
    Symposium on Theoretical Aspects of Computer Science (STACS), 2022.
  21. " Distinct Elements in Streams: An Algorithm for the (Text) Book. " [ps][pdf]
    Joint work with Kuldeep Meel and N.V.Vinodchandran.
    The European Symposium on Algorithms (ESA), 2022.
  22. "Tight Chang's-Lemma-Type Bounds for Boolean Functions. " [ps][pdf]
    Joint work with Nikhil S. Mande, Rajat Mittal, Tulasimohan Molli, Manaswi Paraashar and Swagato Sanyal.
    41st Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2021.
  23. "Interplay between Graph Isomorphism and Earth Mover’s Distance in the Query and Communication Worlds. " [ps][pdf]
    Joint work with Arijit Ghosh, Gopinath Mishra and Sayantan Sen.
    International Conference on Randomization and Computation (RANDOM), 2021.
  24. " Designing Samplers is Easy: The Boon of Testers. " [ps][pdf]
    Joint work with Priyanka Golia, Mate Soos, and Kuldeep S. Meel.
    Formal Methods in Computer-Aided Design (FMCAD), 2021.
  25. " Estimating the Size of Union of Sets in Streaming Models. " [ps][pdf]
    Joint work with Kuldeep Meet and N.V. Vinodchandran.
    Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS) 2021.
  26. " On Testing of Samplers. " [ps][pdf]
    Joint work with Kuldeep Meel and Yash Pote.
    Annual Conference on Neural Information Processing Systems (NeurIPS), 2020.
  27. " Disjointness through the Lens of Vapnik-Chervonenkis Dimension: Sparsity and Beyond. " [ps][pdf]
    Joint work with Anup Bhattacharya, Arijit Ghosh, Gopinath Mishra and Manaswi Paraashar.
    International Conference on Randomization and Computation (RANDOM), 2020.
  28. " Quantum Query-To-Communication Simulation Needs a Logarithmic Overhead. " [ps][pdf]
    Joint work with Arkadev Chattopadhyay, Nikhil S. Mande and Manaswi Paraashar.
    Computational Complexity Conference (CCC), 2020. A preliminary version was presented in Quantum Information Processing (QIP), 2020.
  29. " Improved Bounds on Fourier Entropy and Min-Entropy " [ps][pdf]
    Joint work with Srinivasan Arunachalam, Michal Koucký, Nitin Saurabh and Ronald de Wolf.
    Symposium on Theoretical Aspects of Computer Science (STACS), 2020.
  30. " On Testing of Uniform Samplers " [ps][pdf]
    Joint work with Kuldeep Meel.
    AAAI Conference on Artificial Intelligence (AAAI), 2019.
  31. " The Balanced Connected Subgraph Problem " [ps][pdf]
    Joint work with Sujoy Bhore, Satyabrata Jana, Joseph S. B. Mitchell, Supantha Pandit and Sasanka Roy.
    International Conference on Algorithms and Discrete Applied Mathematics (CALDAM), 2019.
  32. " Two New Results About Quantum Exact Learning " [ps][pdf]
    Joint work with Srinivasan Arunachalam, Sourav Chakraborty, Manaswi Paraashar and Ronald de Wolf.
    International Colloquium on Automata, Languages and Programming (ICALP), 2019.
  33. " Characterization and Recognition of Proper Tagged Probe Interval Graphs " [ps][pdf]
    Joint work with Sanchita Paul, Shamik Ghosh and Malay Sen.
    Computing Conference (CompCom), 2019. Part of the Advances in Intelligent Systems and Computing (AISC).
  34. " Fourier Entropy-Influence Conjecture for Random Linear Threshold Functions" [ps][pdf]
    Joint work with Sushrut Karmalkar, Srijita Kundu, Satyanarayana V. Lokam and Nitin Saurabh.
    Latin American Theoretical INformatics Symposium (LATIN), 2018.
  35. "Exact Algorithm for Maximum Transitive Subgraph Problem" [ps][pdf]
    Joint work with Nitesh Jha.
    15th Cologne-Twente Workshop on Graph & Combinatorial Optimization (CTW), 2017.
  36. "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), 2015.
  37. "Upper Bounds on Fourier Entropy" [ps][pdf]
    Joint work with Raghav Kulkarni, Satyanarayana V. Lokam and Nitin Saurabh.
    International Computing and Combinatorics Conference (COCOON), 2015.
  38. "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.
  39. "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.
  40. "Helly-Type Theorems in Property Testing" [ps][pdf]
    Joint work with Rameshwar Pratap, Sasanka Roy, Shubhangi Saraf.
    Latin American Theoretical INformatics Symposium (LATIN), 2014.
  41. "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.
  42. "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.
  43. "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.
  44. "Improved Competitive Ratio for the Matroid Secretary Problem." [ps][pdf]
    Joint work with Oded Lachish.
    ACM-SIAM Symposium on Discrete Algorithms (SODA), 2012.
  45. "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.
  46. "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.
  47. "Query Complexity Lower Bounds for Reconstruction of Codes" [ps][pdf]
    Joint work with Eldar Fischer and Arie Matsliah.
    Innovations in Computer Science (ICS), 2011.
  48. "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.
  49. "Market Clearance Pricing in a Metric" [ps][pdf]
    Joint work with Nikhil Devanur and Chinmay Karande.
    WINE, 2010.
  50. "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.
  51. "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.
  52. "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), 2010.
  53. "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.
  54. "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), 2009.
  55. "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.
  56. "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.
  57. "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.
  58. "On the Sensitivity of Cyclically-Invariant Functions" [ps][pdf]
    20th Annual IEEE Conference on Computational Complexity (CCC), 2005.

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.