Sourav Chakraborty

ORCID

Publication Activity (10 Years)

Years Active: 2005-2024
Publications (10 Years): 82

Top Venues

CoRR

Electron. Colloquium Comput. Complex.

ICALP

APPROX-RANDOM

Publications

Sourav Chakraborty, Swarnalipa Datta, Pranjal Dutta, Arijit Ghosh, Swagato Sanyal
On Fourier Analysis of Sparse Boolean Functions over Certain Abelian Groups. MFCS (2024)
Mate Soos, Uddalok Sarkar, Divesh Aggarwal, Sourav Chakraborty, Kuldeep S. Meel, Maciej Obremski
Engineering an Efficient Approximate DNF-Counter. CoRR (2024)
Diptarka Chakraborty, Sourav Chakraborty, Gunjan Kumar, Kuldeep S. Meel
Equivalence Testing: The Power of Bounded Adaptivity. CoRR (2024)
Diptarka Chakraborty, Sourav Chakraborty, Gunjan Kumar, Kuldeep S. Meel
Equivalence Testing: The Power of Bounded Adaptivity. AISTATS (2024)
Diptarka Chakraborty, Sourav Chakraborty, Gunjan Kumar
Tight Lower Bound on Equivalence Testing in Conditional Sampling Model. SODA (2024)
Eduard Baranov, Sourav Chakraborty, Axel Legay, Kuldeep S. Meel, N. Variyam Vinodchandran
A Scalable $t$t-Wise Coverage Estimator: Algorithms and Applications. IEEE Trans. Software Eng. 50 (8) (2024)
Sourav Chakraborty, Swarnalipa Datta, Pranjal Dutta, Arijit Ghosh, Swagato Sanyal
On Fourier analysis of sparse Boolean functions over certain Abelian groups. CoRR (2024)
Sourav Chakraborty, Chandrima Kayal, Rajat Mittal, Manaswi Paraashar, Nitin Saurabh
Approximate Degree Composition for Recursive Functions. CoRR (2024)
Kuldeep S. Meel, Sourav Chakraborty, Umang Mathur
A faster FPRAS for #NFA. Proc. ACM Manag. Data 2 (2) (2024)
Rishiraj Bhattacharyya, Sourav Chakraborty, Yash Pote, Uddalok Sarkar, Sayantan Sen
Testing Self-Reducible Samplers. AAAI (2024)
Aduri Pavan, Sourav Chakraborty, N. V. Vinodchandran, Kuldeep S. Meel
On the Feasibility of Forgetting in Data Streams. Proc. ACM Manag. Data 2 (2) (2024)
Kuldeep S. Meel, Sourav Chakraborty, Umang Mathur
A faster FPRAS for #NFA. CoRR (2023)
Sourav Chakraborty, Chandrima Kayal, Rajat Mittal, Manaswi Paraashar, Swagato Sanyal, Nitin Saurabh
On the Composition of Randomized Query Complexity and Approximate Degree. CoRR (2023)
Ansuman Banerjee, Shayak Chakraborty, Sourav Chakraborty, Kuldeep S. Meel, Uddalok Sarkar, Sayantan Sen
Testing of Horn Samplers. AISTATS (2023)
Sourav Chakraborty, N. V. Vinodchandran, Kuldeep S. Meel
Distinct Elements in Streams: An Algorithm for the (Text) Book. CoRR (2023)
Mate Soos, Divesh Aggarwal, Sourav Chakraborty, Kuldeep S. Meel, Maciej Obremski
Engineering an Efficient Approximate DNF-Counter. IJCAI (2023)
Diptarka Chakraborty, Sourav Chakraborty, Gunjan Kumar
Tight Lower Bound on Equivalence Testing in Conditional Sampling Model. CoRR (2023)
Sourav Chakraborty, Chandrima Kayal, Rajat Mittal, Manaswi Paraashar, Swagato Sanyal, Nitin Saurabh
On the Composition of Randomized Query Complexity and Approximate Degree. Electron. Colloquium Comput. Complex. (2023)
Sourav Chakraborty, Avijeet Ghosh, Sujata Ghosh, François Schwarzentruber
On Simple Expectations and Observations of Intelligent Agents: A Complexity Study. KR (2023)
Sourav Chakraborty, Anna Gál, Sophie Laplante, Rajat Mittal, Anupa Sunny
Certificate Games. ITCS (2023)
Diptarka Chakraborty, Sourav Chakraborty, Gunjan Kumar, Kuldeep S. Meel
Approximate Model Counting: Is SAT Oracle More Powerful Than NP Oracle? ICALP (2023)
Sourav Chakraborty, Eldar Fischer, Arijit Ghosh, Gopinath Mishra, Sayantan Sen
Testing of Index-Invariant Properties in the Huge Object Model. COLT (2023)
Sourav Chakraborty, Chandrima Kayal, Rajat Mittal, Manaswi Paraashar, Swagato Sanyal, Nitin Saurabh
On the Composition of Randomized Query Complexity and Approximate Degree. APPROX/RANDOM (2023)
Sourav Chakraborty, Chandrima Kayal, Manaswi Paraashar
Separations between Combinatorial Measures for Transitive Functions. Electron. Colloquium Comput. Complex. (2023)
Sourav Chakraborty, Avijeet Ghosh, Sujata Ghosh, François Schwarzentruber
On simple expectations and observations of intelligent agents: A complexity study. CoRR (2023)
Rishiraj Bhattacharyya, Sourav Chakraborty, Yash Pote, Uddalok Sarkar, Sayantan Sen
Testing Self-Reducible Samplers. CoRR (2023)
Diptarka Chakraborty, Sourav Chakraborty, Gunjan Kumar, Kuldeep S. Meel
Approximate Model Counting: Is SAT Oracle More Powerful than NP Oracle? CoRR (2023)
Eduard Baranov, Sourav Chakraborty, Axel Legay, Kuldeep S. Meel, N. Variyam Vinodchandran
A Scalable t-wise Coverage Estimator. ICSE (2022)
Sourav Chakraborty, Eldar Fischer, Arijit Ghosh, Gopinath Mishra, Sayantan Sen
Testing of Index-Invariant Properties in the Huge Object Model. CoRR (2022)
Kuldeep S. Meel, Sourav Chakraborty, N. V. Vinodchandran
Estimation of the Size of Union of Delphic Sets: Achieving Independence from Stream Size. PODS (2022)
Sourav Chakraborty, Chandrima Kayal, Manaswi Paraashar
Separations Between Combinatorial Measures for Transitive Functions. ICALP (2022)
Mate Soos, Priyanka Golia, Sourav Chakraborty, Kuldeep S. Meel
On Quantitative Testing of Samplers. CP (2022)
Sourav Chakraborty, Arkadev Chattopadhyay, Peter Høyer, Nikhil S. Mande, Manaswi Paraashar, Ronald de Wolf
Symmetry and Quantum Query-To-Communication Simulation. STACS (2022)
Anup Bhattacharya, Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra, Manaswi Paraashar
Disjointness through the Lens of Vapnik-Chervonenkis Dimension: Sparsity and Beyond. Comput. Complex. 31 (2) (2022)
Sourav Chakraborty, N. V. Vinodchandran, Kuldeep S. Meel
Distinct Elements in Streams: An Algorithm for the (Text) Book. ESA (2022)
Sourav Chakraborty, Anna Gál, Sophie Laplante, Rajat Mittal, Anupa Sunny
Certificate games. CoRR (2022)
Sourav Chakraborty, Eldar Fischer, Arijit Ghosh, Gopinath Mishra, Sayantan Sen
Testing of Index-Invariant Properties in the Huge Object Model. Electron. Colloquium Comput. Complex. (2022)
Sourav Chakraborty, Avijeet Ghosh, Sujata Ghosh, François Schwarzentruber
On Verifying Expectations and Observations of Intelligent Agents. IJCAI (2022)
Sourav Chakraborty, Avijeet Ghosh, Sujata Ghosh, François Schwarzentruber
On verifying expectations and observations of intelligent agents. CoRR (2022)
Sourav Chakraborty, Anna Gál, Sophie Laplante, Rajat Mittal, Anupa Sunny
Certificate games. Electron. Colloquium Comput. Complex. (2022)
Sourav Chakraborty, Arijit Ghosh, Soumi Nandi
Colorful Helly Theorem for Piercing Boxes with Two Points. CoRR (2022)
Sourav Chakraborty, Eldar Fischer, Arijit Ghosh, Gopinath Mishra, Sayantan Sen
Exploring the Gap Between Tolerant and Non-Tolerant Distribution Testing. APPROX/RANDOM (2022)
Sujoy Bhore, Sourav Chakraborty, Satyabrata Jana, Joseph S. B. Mitchell, Supantha Pandit, Sasanka Roy
The balanced connected subgraph problem. Discret. Appl. Math. 319 (2022)
Sourav Chakraborty, Eldar Fischer, Arijit Ghosh, Gopinath Mishra, Sayantan Sen
Exploring the Gap between Tolerant and Non-tolerant Distribution Testing. CoRR (2021)
Srinivasan Arunachalam, Sourav Chakraborty, Troy Lee, Manaswi Paraashar, Ronald de Wolf
Two new results about quantum exact learning. Quantum 5 (2021)
Srinivasan Arunachalam, Sourav Chakraborty, Michal Koucký, Nitin Saurabh, Ronald de Wolf
Improved Bounds on Fourier Entropy and Min-entropy. ACM Trans. Comput. Theory 13 (4) (2021)
Sourav Chakraborty, Nikhil S. Mande, Rajat Mittal, Tulasimohan Molli, Manaswi Paraashar, Swagato Sanyal
Tight Chang's-Lemma-Type Bounds for Boolean Functions. FSTTCS (2021)
Sourav Chakraborty, Chandrima Kayal, Manaswi Paraashar
Separations between Combinatorial Measures for Transitive Functions. CoRR (2021)
Kuldeep S. Meel, N. V. Vinodchandran, Sourav Chakraborty
Estimating the Size of Union of Sets in Streaming Models. PODS (2021)
Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra, Sayantan Sen
Interplay Between Graph Isomorphism and Earth Mover's Distance in the Query and Communication Worlds. APPROX-RANDOM (2021)
Priyanka Golia, Mate Soos, Sourav Chakraborty, Kuldeep S. Meel
Designing Samplers is Easy: The Boon of Testers. FMCAD (2021)
Sourav Chakraborty, Arkadev Chattopadhyay, Peter Høyer, Nikhil S. Mande, Manaswi Paraashar, Ronald de Wolf
Symmetry and Quantum Query-to-Communication Simulation. CoRR (2020)
Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra, Sayantan Sen
Estimation of Graph Isomorphism Distance in the Query World. Electron. Colloquium Comput. Complex. 27 (2020)
Kuldeep S. Meel, Yash Pote, Sourav Chakraborty
On Testing of Samplers. NeurIPS (2020)
Anup Bhattacharya, Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra, Manaswi Paraashar
Disjointness through the Lens of Vapnik-Chervonenkis Dimension: Sparsity and Beyond. Electron. Colloquium Comput. Complex. 27 (2020)
Sourav Chakraborty, Arkadev Chattopadhyay, Nikhil S. Mande, Manaswi Paraashar
Quantum Query-To-Communication Simulation Needs a Logarithmic Overhead. Computational Complexity Conference (2020)
Kuldeep S. Meel, Yash Pote, Sourav Chakraborty
On Testing of Samplers. CoRR (2020)
Srinivasan Arunachalam, Sourav Chakraborty, Michal Koucký, Nitin Saurabh, Ronald de Wolf
Improved Bounds on Fourier Entropy and Min-Entropy. STACS (2020)
Anup Bhattacharya, Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra, Manaswi Paraashar
Disjointness Through the Lens of Vapnik-Chervonenkis Dimension: Sparsity and Beyond. APPROX-RANDOM (2020)
Anup Bhattacharya, Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra, Manaswi Paraashar
Disjointness through the Lens of Vapnik-Chervonenkis Dimension: Sparsity and Beyond. CoRR (2020)
Sourav Chakraborty, Nikhil S. Mande, Rajat Mittal, Tulasimohan Molli, Manaswi Paraashar, Swagato Sanyal
Tight Chang's-lemma-type bounds for Boolean functions. CoRR (2020)
Srinivasan Arunachalam, Sourav Chakraborty, Troy Lee, Manaswi Paraashar, Ronald de Wolf
Two New Results About Quantum Exact Learning. ICALP (2019)
Sourav Chakraborty, Arkadev Chattopadhyay, Nikhil S. Mande, Manaswi Paraashar
Quantum Query-to-Communication Simulation Needs a Logarithmic Overhead. Electron. Colloquium Comput. Complex. 26 (2019)
Sourav Chakraborty, Arkadev Chattopadhyay, Nikhil S. Mande, Manaswi Paraashar
Quantum Query-to-Communication Simulation Needs a Logarithmic Overhead. CoRR (2019)
Sujoy Bhore, Sourav Chakraborty, Satyabrata Jana, Joseph S. B. Mitchell, Supantha Pandit, Sasanka Roy
The Balanced Connected Subgraph Problem. CALDAM (2019)
Sourav Chakraborty, Kuldeep S. Meel
On Testing of Uniform Samplers. AAAI (2019)
Sourav Chakraborty, Sushrut Karmalkar, Srijita Kundu, Satyanarayana V. Lokam, Nitin Saurabh
Fourier Entropy-Influence Conjecture for Random Linear Threshold Functions. CoRR (2019)
Rishiraj Bhattacharyya, Sourav Chakraborty
Property Testing of Joint Distributions using Conditional Samples. ACM Trans. Comput. Theory 10 (4) (2018)
Srinivasan Arunachalam, Sourav Chakraborty, Troy Lee, Ronald de Wolf
Two new results about quantum exact learning. CoRR (2018)
Sujoy Bhore, Sourav Chakraborty, Satyabrata Jana, Joseph S. B. Mitchell, Supantha Pandit, Sasanka Roy
The Balanced Connected Subgraph Problem. CoRR (2018)
Sourav Chakraborty, Shamik Ghosh, Nitesh Jha, Sasanka Roy
Maximal and maximum transitive relation contained in a given binary relation. CoRR (2018)
Sourav Chakraborty, Rameshwar Pratap, Sasanka Roy, Shubhangi Saraf
Helly-Type Theorems in Property Testing. Int. J. Comput. Geom. Appl. 28 (4) (2018)
Srinivasan Arunachalam, Sourav Chakraborty, Michal Koucký, Nitin Saurabh, Ronald de Wolf
Improved bounds on Fourier entropy and Min-entropy. CoRR (2018)
Srinivasan Arunachalam, Sourav Chakraborty, Michal Koucký, Nitin Saurabh, Ronald de Wolf
Improved bounds on Fourier entropy and Min-entropy. Electron. Colloquium Comput. Complex. 25 (2018)
Sourav Chakraborty, Sushrut Karmalkar, Srijita Kundu, Satyanarayana V. Lokam, Nitin Saurabh
Fourier Entropy-Influence Conjecture for Random Linear Threshold Functions. LATIN (2018)
Rishiraj Bhattacharyya, Sourav Chakraborty
Property Testing of Joint Distributions using Conditional Samples. CoRR (2017)
Sourav Chakraborty, Raghav Kulkarni, Satyanarayana V. Lokam, Nitin Saurabh
Upper bounds on Fourier entropy. Theor. Comput. Sci. 654 (2016)
Sourav Chakraborty, Eldar Fischer, Yonatan Goldhirsh, Arie Matsliah
On the Power of Conditional Samples in Distribution Testing. SIAM J. Comput. 45 (4) (2016)
Sourav Chakraborty, Akshay Kamath, Rameshwar Pratap
Testing whether the uniform distribution is a stationary distribution. Inf. Process. Lett. 116 (7) (2016)
Sourav Chakraborty, Shamik Ghosh, Sanchita Paul, Malay K. Sen
Characterization and recognition of proper tagged probe interval graphs. CoRR (2016)
Sourav Chakraborty, Raghav Kulkarni, Satyanarayana V. Lokam, Nitin Saurabh
Upper Bounds on Fourier Entropy. COCOON (2015)
Sourav Chakraborty, Shamik Ghosh, Nitesh Jha, Sasanka Roy
Maximal and Maximum Transitive Relation Contained in a Given Binary Relation. COCOON (2015)
Sourav Chakraborty, Eldar Fischer, Arie Matsliah
Query Complexity Lower Bounds for Reconstruction of Codes. Theory Comput. 10 (2014)
Rupam Acharyya, Sourav Chakraborty, Nitesh Jha
Counting Popular Matchings in House Allocation Problems. CSR (2014)
Sourav Chakraborty, Rameshwar Pratap, Sasanka Roy, Shubhangi Saraf
Helly-Type Theorems in Property Testing. LATIN (2014)
Abhishek Bhrushundi, Sourav Chakraborty, Raghav Kulkarni
Property Testing Bounds for Linear and Quadratic Functions via Parity Decision Trees. CSR (2014)
Sourav Chakraborty, Eldar Fischer, Yonatan Goldhirsh, Arie Matsliah
On the power of conditional samples in distribution testing. ITCS (2013)
Rupam Acharyya, Sourav Chakraborty, Nitesh Jha
Counting Popular Matchings in House Allocation Problems. CoRR (2013)
Noga Alon, Eric Blais, Sourav Chakraborty, David García-Soriano, Arie Matsliah
Nearly Tight Bounds for Testing Function Isomorphism. SIAM J. Comput. 42 (2) (2013)
Sourav Chakraborty, Raghav Kulkarni, Satyanarayana V. Lokam, Nitin Saurabh
Upper Bounds on Fourier Entropy. Electron. Colloquium Comput. Complex. 20 (2013)
Sourav Chakraborty, Rameshwar Pratap, Sasanka Roy, Shubhangi Saraf
Helly-Type Theorems in Property Testing. CoRR (2013)
Sourav Chakraborty, Akshay Kamath, Rameshwar Pratap
Testing Uniformity of Stationary Distribution CoRR (2013)
Sourav Chakraborty, Akshay Kamath, Rameshwar Pratap
Testing uniformity of stationary distribution. CTW (2013)
Abhishek Bhrushundi, Sourav Chakraborty, Raghav Kulkarni
Property Testing Bounds for Linear and Quadratic Functions via Parity Decision Trees. Electron. Colloquium Comput. Complex. 20 (2013)
Sourav Chakraborty, Eldar Fischer, Yonatan Goldhirsh, Arie Matsliah
On the Power of Conditional Samples in Distribution Testing. Electron. Colloquium Comput. Complex. 19 (2012)
Sourav Chakraborty, Eldar Fischer, David García-Soriano, Arie Matsliah
Junto-Symmetric Functions, Hypergraph Isomorphism and Crunching. Computational Complexity Conference (2012)
Sourav Chakraborty, Oded Lachish
Improved competitive ratio for the matroid secretary problem. SODA (2012)
Sourav Chakraborty, Eldar Fischer, Yonatan Goldhirsh, Arie Matsliah
On the Power of Conditional Samples in Distribution Testing CoRR (2012)
Jop Briët, Sourav Chakraborty, David García-Soriano, Arie Matsliah
Monotonicity testing and shortest-path routing on the cube. Comb. 32 (1) (2012)
Sourav Chakraborty, David García-Soriano, Arie Matsliah
Efficient Sample Extractors for Juntas with Applications. ICALP (1) (2011)

Sourav Chakraborty.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Sourav Chakraborty