Sourav Chakraborty

According to our database, Sourav Chakraborty authored at least 71 papers between 2005 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2024

A Scalable $t$t-Wise Coverage Estimator: Algorithms and Applications.

Eduard Baranov, Sourav Chakraborty, Axel Legay, Kuldeep S. Meel, N. Variyam Vinodchandran

IEEE Trans. Software Eng., August, 2024

On the Feasibility of Forgetting in Data Streams.

Aduri Pavan, Sourav Chakraborty, N. V. Vinodchandran, Kuldeep S. Meel

Proc. ACM Manag. Data, 2024

A faster FPRAS for #NFA.

Kuldeep S. Meel, Sourav Chakraborty, Umang Mathur

Proc. ACM Manag. Data, 2024

Testing vs Estimation for Index-Invariant Properties in the Huge Object Model.

Sourav Chakraborty, Eldar Fischer, Arijit Ghosh, Amit Levi, Gopinath Mishra, Sayantan Sen

Electron. Colloquium Comput. Complex., 2024

Testing Credibility of Public and Private Surveys through the Lens of Regression.

Debabrota Basu, Sourav Chakraborty, Debarshi Chanda, Buddha Dev Das, Arijit Ghosh, Arnab Ray

CoRR, 2024

Engineering an Efficient Approximate DNF-Counter.

Mate Soos, Uddalok Sarkar, Divesh Aggarwal, Sourav Chakraborty, Kuldeep S. Meel, Maciej Obremski

CoRR, 2024

Tight Lower Bound on Equivalence Testing in Conditional Sampling Model.

Diptarka Chakraborty, Sourav Chakraborty, Gunjan Kumar

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

On Fourier Analysis of Sparse Boolean Functions over Certain Abelian Groups.

Sourav Chakraborty, Swarnalipa Datta, Pranjal Dutta, Arijit Ghosh, Swagato Sanyal

Proceedings of the 49th International Symposium on Mathematical Foundations of Computer Science, 2024

Improved Streaming Algorithm for the Klee's Measure Problem and Generalizations.

Mridul Nandi, N. V. Vinodchandran, Arijit Ghosh, Kuldeep S. Meel, Soumit Pal, Sourav Chakraborty

Proceedings of the Approximation, 2024

Approximate Degree Composition for Recursive Functions.

Sourav Chakraborty, Chandrima Kayal, Rajat Mittal, Manaswi Paraashar, Nitin Saurabh

Proceedings of the Approximation, 2024

Equivalence Testing: The Power of Bounded Adaptivity.

Diptarka Chakraborty, Sourav Chakraborty, Gunjan Kumar, Kuldeep S. Meel

Proceedings of the International Conference on Artificial Intelligence and Statistics, 2024

Testing Self-Reducible Samplers.

Rishiraj Bhattacharyya, Sourav Chakraborty, Yash Pote, Uddalok Sarkar, Sayantan Sen

Proceedings of the Thirty-Eighth AAAI Conference on Artificial Intelligence, 2024

2023

Separations between Combinatorial Measures for Transitive Functions.

Sourav Chakraborty, Chandrima Kayal, Manaswi Paraashar

Electron. Colloquium Comput. Complex., 2023

On the Composition of Randomized Query Complexity and Approximate Degree.

Sourav Chakraborty, Chandrima Kayal, Rajat Mittal, Manaswi Paraashar, Swagato Sanyal, Nitin Saurabh

Electron. Colloquium Comput. Complex., 2023

On Simple Expectations and Observations of Intelligent Agents: A Complexity Study.

Sourav Chakraborty, Avijeet Ghosh, Sujata Ghosh, François Schwarzentruber

Proceedings of the 20th International Conference on Principles of Knowledge Representation and Reasoning, 2023

Engineering an Efficient Approximate DNF-Counter.

Mate Soos, Divesh Aggarwal, Sourav Chakraborty, Kuldeep S. Meel, Maciej Obremski

Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, 2023

Approximate Model Counting: Is SAT Oracle More Powerful Than NP Oracle?

Diptarka Chakraborty, Sourav Chakraborty, Gunjan Kumar, Kuldeep S. Meel

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

Testing of Horn Samplers.

Ansuman Banerjee, Shayak Chakraborty, Sourav Chakraborty, Kuldeep S. Meel, Uddalok Sarkar, Sayantan Sen

Proceedings of the International Conference on Artificial Intelligence and Statistics, 2023

2022

Certificate games.

Sourav Chakraborty, Anna Gál, Sophie Laplante, Rajat Mittal, Anupa Sunny

Electron. Colloquium Comput. Complex., 2022

Testing of Index-Invariant Properties in the Huge Object Model.

Sourav Chakraborty, Eldar Fischer, Arijit Ghosh, Gopinath Mishra, Sayantan Sen

Electron. Colloquium Comput. Complex., 2022

The balanced connected subgraph problem.

Sujoy Bhore, Sourav Chakraborty, Satyabrata Jana, Joseph S. B. Mitchell, Supantha Pandit, Sasanka Roy

Discret. Appl. Math., 2022

Colorful Helly Theorem for Piercing Boxes with Two Points.

Sourav Chakraborty, Arijit Ghosh, Soumi Nandi

CoRR, 2022

Disjointness through the Lens of Vapnik-Chervonenkis Dimension: Sparsity and Beyond.

Anup Bhattacharya, Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra, Manaswi Paraashar

Comput. Complex., 2022

Symmetry and Quantum Query-To-Communication Simulation.

Sourav Chakraborty, Arkadev Chattopadhyay, Peter Høyer, Nikhil S. Mande, Manaswi Paraashar, Ronald de Wolf

Proceedings of the 39th International Symposium on Theoretical Aspects of Computer Science, 2022

Estimation of the Size of Union of Delphic Sets: Achieving Independence from Stream Size.

Kuldeep S. Meel, Sourav Chakraborty, N. V. Vinodchandran

Proceedings of the PODS '22: International Conference on Management of Data, Philadelphia, PA, USA, June 12, 2022

On Verifying Expectations and Observations of Intelligent Agents.

Sourav Chakraborty, Avijeet Ghosh, Sujata Ghosh, François Schwarzentruber

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, 2022

A Scalable t-wise Coverage Estimator.

Eduard Baranov, Sourav Chakraborty, Axel Legay, Kuldeep S. Meel, N. Variyam Vinodchandran

Proceedings of the 44th IEEE/ACM 44th International Conference on Software Engineering, 2022

Distinct Elements in Streams: An Algorithm for the (Text) Book.

Sourav Chakraborty, N. V. Vinodchandran, Kuldeep S. Meel

Proceedings of the 30th Annual European Symposium on Algorithms, 2022

On Quantitative Testing of Samplers.

Mate Soos, Priyanka Golia, Sourav Chakraborty, Kuldeep S. Meel

Proceedings of the 28th International Conference on Principles and Practice of Constraint Programming, 2022

Exploring the Gap Between Tolerant and Non-Tolerant Distribution Testing.

Sourav Chakraborty, Eldar Fischer, Arijit Ghosh, Gopinath Mishra, Sayantan Sen

Proceedings of the Approximation, 2022

2021

Two new results about quantum exact learning.

Srinivasan Arunachalam, Sourav Chakraborty, Troy Lee, Manaswi Paraashar, Ronald de Wolf

Quantum, 2021

Estimating the Size of Union of Sets in Streaming Models.

Kuldeep S. Meel, N. V. Vinodchandran, Sourav Chakraborty

Proceedings of the PODS'21: Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2021

Tight Chang's-Lemma-Type Bounds for Boolean Functions.

Sourav Chakraborty, Nikhil S. Mande, Rajat Mittal, Tulasimohan Molli, Manaswi Paraashar, Swagato Sanyal

Proceedings of the 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2021

Designing Samplers is Easy: The Boon of Testers.

Priyanka Golia, Mate Soos, Sourav Chakraborty, Kuldeep S. Meel

Proceedings of the Formal Methods in Computer Aided Design, 2021

Interplay Between Graph Isomorphism and Earth Mover's Distance in the Query and Communication Worlds.

Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra, Sayantan Sen

Proceedings of the Approximation, 2021

2020

Estimation of Graph Isomorphism Distance in the Query World.

Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra, Sayantan Sen

Electron. Colloquium Comput. Complex., 2020

On Testing of Samplers.

Kuldeep S. Meel, Yash Pote, Sourav Chakraborty

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

2019

Quantum Query-to-Communication Simulation Needs a Logarithmic Overhead.

Sourav Chakraborty, Arkadev Chattopadhyay, Nikhil S. Mande, Manaswi Paraashar

Electron. Colloquium Comput. Complex., 2019

On Testing of Uniform Samplers.

Sourav Chakraborty, Kuldeep S. Meel

Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence, 2019

2018

Property Testing of Joint Distributions using Conditional Samples.

Rishiraj Bhattacharyya, Sourav Chakraborty

ACM Trans. Comput. Theory, 2018

Helly-Type Theorems in Property Testing.

Sourav Chakraborty, Rameshwar Pratap, Sasanka Roy, Shubhangi Saraf

Int. J. Comput. Geom. Appl., 2018

Improved bounds on Fourier entropy and Min-entropy.

Srinivasan Arunachalam, Sourav Chakraborty, Michal Koucký, Nitin Saurabh, Ronald de Wolf

Electron. Colloquium Comput. Complex., 2018

Two new results about quantum exact learning.

Srinivasan Arunachalam, Sourav Chakraborty, Troy Lee, Ronald de Wolf

CoRR, 2018

Fourier Entropy-Influence Conjecture for Random Linear Threshold Functions.

Sourav Chakraborty, Sushrut Karmalkar, Srijita Kundu, Satyanarayana V. Lokam, Nitin Saurabh

Proceedings of the LATIN 2018: Theoretical Informatics, 2018

2016

Upper bounds on Fourier entropy.

Sourav Chakraborty, Raghav Kulkarni, Satyanarayana V. Lokam, Nitin Saurabh

Theor. Comput. Sci., 2016

On the Power of Conditional Samples in Distribution Testing.

Sourav Chakraborty, Eldar Fischer, Yonatan Goldhirsh, Arie Matsliah

SIAM J. Comput., 2016

Testing whether the uniform distribution is a stationary distribution.

Sourav Chakraborty, Akshay Kamath, Rameshwar Pratap

Inf. Process. Lett., 2016

Characterization and recognition of proper tagged probe interval graphs.

Sourav Chakraborty, Shamik Ghosh, Sanchita Paul, Malay K. Sen

CoRR, 2016

2015

Maximal and Maximum Transitive Relation Contained in a Given Binary Relation.

Sourav Chakraborty, Shamik Ghosh, Nitesh Jha, Sasanka Roy

Proceedings of the Computing and Combinatorics - 21st International Conference, 2015

2014

Counting Popular Matchings in House Allocation Problems.

Rupam Acharyya, Sourav Chakraborty, Nitesh Jha

Proceedings of the Computer Science - Theory and Applications, 2014

2013

Nearly Tight Bounds for Testing Function Isomorphism.

Noga Alon, Eric Blais, Sourav Chakraborty, David García-Soriano, Arie Matsliah

SIAM J. Comput., 2013

Property Testing Bounds for Linear and Quadratic Functions via Parity Decision Trees.

Abhishek Bhrushundi, Sourav Chakraborty, Raghav Kulkarni

Electron. Colloquium Comput. Complex., 2013

Testing uniformity of stationary distribution.

Sourav Chakraborty, Akshay Kamath, Rameshwar Pratap

Proceedings of the 12th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, 2013

2012

Improved competitive ratio for the matroid secretary problem.

Sourav Chakraborty, Oded Lachish

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Junto-Symmetric Functions, Hypergraph Isomorphism and Crunching.

Sourav Chakraborty, Eldar Fischer, David García-Soriano, Arie Matsliah

Proceedings of the 27th Conference on Computational Complexity, 2012

2011

Hardness and algorithms for rainbow connection.

Sourav Chakraborty, Eldar Fischer, Arie Matsliah, Raphael Yuster

J. Comb. Optim., 2011

Cycle Detection, Order Finding and Discrete Log with Jumps.

Sourav Chakraborty, David García-Soriano, Arie Matsliah

Proceedings of the Innovations in Computer Science, 2011

Efficient Sample Extractors for Juntas with Applications.

Sourav Chakraborty, David García-Soriano, Arie Matsliah

Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

2010

Monotonicity Testing and Shortest-Path Routing on the Cube.

David García-Soriano, Arie Matsliah, Sourav Chakraborty, Jop Briët

Electron. Colloquium Comput. Complex., 2010

Nearly Tight Bounds for Testing Function Isomorphism.

Sourav Chakraborty, David García-Soriano, Arie Matsliah

Electron. Colloquium Comput. Complex., 2010

Query Complexity Lower Bounds for Reconstruction of Codes.

Sourav Chakraborty, Eldar Fischer, Arie Matsliah

Electron. Colloquium Comput. Complex., 2010

Market Equilibrium with Transaction Costs.

Sourav Chakraborty, Nikhil R. Devanur, Chinmay Karande

Proceedings of the Internet and Network Economics - 6th International Workshop, 2010

Two-phase Algorithms for the Parametric Shortest Path Problem.

Sourav Chakraborty, Eldar Fischer, Oded Lachish, Raphael Yuster

Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science, 2010

New Results on Quantum Property Testing.

Sourav Chakraborty, Eldar Fischer, Arie Matsliah, Ronald de Wolf

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2010

2009

An Online Multi-unit Auction with Improved Competitive Ratio.

Sourav Chakraborty, Nikhil R. Devanur

Proceedings of the Internet and Network Economics, 5th International Workshop, 2009

Hardness and Algorithms for Rainbow Connectivity.

Sourav Chakraborty, Eldar Fischer, Arie Matsliah, Raphael Yuster

Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science, 2009

2008

Property Testing of Equivalence under a Permutation Group Action.

Sourav Chakraborty, László Babai

Electron. Colloquium Comput. Complex., 2008

2007

Testing <i>st</i> -Connectivity.

Sourav Chakraborty, Eldar Fischer, Oded Lachish, Arie Matsliah, Ilan Newman

Proceedings of the Approximation, 2007

2006

Zero Error List-Decoding Capacity of the <i>q</i>/(<i>q</i>-1) Channel.

Sourav Chakraborty, Jaikumar Radhakrishnan, Nandakumar Raghunathan, Prashant Sasatte

Proceedings of the FSTTCS 2006: Foundations of Software Technology and Theoretical Computer Science, 2006

2005

On the Sensitivity of Cyclically-Invariant Boolean Functions

Sourav Chakraborty

Electron. Colloquium Comput. Complex., 2005

Bounds for Error Reduction with Few Quantum Queries.

Sourav Chakraborty, Jaikumar Radhakrishnan, Nandakumar Raghunathan

Proceedings of the Approximation, 2005