Sourav Chakraborty

Orcid: 0000-0001-9518-6204

Affiliations:
  • Indian Statistical Institute, Kolkata, India
  • Chennai Mathematical Institute, Chennai, India (former)


According to our database1, Sourav Chakraborty authored at least 62 papers between 2005 and 2024.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
Testing Self-Reducible Samplers.
Proceedings of the Thirty-Eighth AAAI Conference on Artificial Intelligence, 2024

2023
Separations between Combinatorial Measures for Transitive Functions.
Electron. Colloquium Comput. Complex., 2023

On the Composition of Randomized Query Complexity and Approximate Degree.
Electron. Colloquium Comput. Complex., 2023

A faster FPRAS for #NFA.
CoRR, 2023

Tight Lower Bound on Equivalence Testing in Conditional Sampling Model.
CoRR, 2023

On Simple Expectations and Observations of Intelligent Agents: A Complexity Study.
Proceedings of the 20th International Conference on Principles of Knowledge Representation and Reasoning, 2023

Engineering an Efficient Approximate DNF-Counter.
Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, 2023

Approximate Model Counting: Is SAT Oracle More Powerful Than NP Oracle?
Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

Testing of Horn Samplers.
Proceedings of the International Conference on Artificial Intelligence and Statistics, 2023

2022
Certificate games.
Electron. Colloquium Comput. Complex., 2022

Testing of Index-Invariant Properties in the Huge Object Model.
Electron. Colloquium Comput. Complex., 2022

The balanced connected subgraph problem.
Discret. Appl. Math., 2022

Colorful Helly Theorem for Piercing Boxes with Two Points.
CoRR, 2022

Disjointness through the Lens of Vapnik-Chervonenkis Dimension: Sparsity and Beyond.
Comput. Complex., 2022

Symmetry and Quantum Query-To-Communication Simulation.
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.
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.
Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, 2022

A Scalable t-wise Coverage Estimator.
Proceedings of the 44th IEEE/ACM 44th International Conference on Software Engineering, 2022

Distinct Elements in Streams: An Algorithm for the (Text) Book.
Proceedings of the 30th Annual European Symposium on Algorithms, 2022

On Quantitative Testing of Samplers.
Proceedings of the 28th International Conference on Principles and Practice of Constraint Programming, 2022

Exploring the Gap Between Tolerant and Non-Tolerant Distribution Testing.
Proceedings of the Approximation, 2022

2021
Two new results about quantum exact learning.
Quantum, 2021

Estimating the Size of Union of Sets in Streaming Models.
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.
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.
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.
Proceedings of the Approximation, 2021

2020
Estimation of Graph Isomorphism Distance in the Query World.
Electron. Colloquium Comput. Complex., 2020

On Testing of Samplers.
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.
Electron. Colloquium Comput. Complex., 2019

On Testing of Uniform Samplers.
Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence, 2019

2018
Property Testing of Joint Distributions using Conditional Samples.
ACM Trans. Comput. Theory, 2018

Helly-Type Theorems in Property Testing.
Int. J. Comput. Geom. Appl., 2018

Improved bounds on Fourier entropy and Min-entropy.
Electron. Colloquium Comput. Complex., 2018

Two new results about quantum exact learning.
CoRR, 2018

Fourier Entropy-Influence Conjecture for Random Linear Threshold Functions.
Proceedings of the LATIN 2018: Theoretical Informatics, 2018

2016
Upper bounds on Fourier entropy.
Theor. Comput. Sci., 2016

Testing whether the uniform distribution is a stationary distribution.
Inf. Process. Lett., 2016

Characterization and recognition of proper tagged probe interval graphs.
CoRR, 2016

2015
Maximal and Maximum Transitive Relation Contained in a Given Binary Relation.
Proceedings of the Computing and Combinatorics - 21st International Conference, 2015

2014
Query Complexity Lower Bounds for Reconstruction of Codes.
Theory Comput., 2014

Counting Popular Matchings in House Allocation Problems.
Proceedings of the Computer Science - Theory and Applications, 2014

2013
Nearly Tight Bounds for Testing Function Isomorphism.
SIAM J. Comput., 2013

Property Testing Bounds for Linear and Quadratic Functions via Parity Decision Trees.
Electron. Colloquium Comput. Complex., 2013

Testing uniformity of stationary distribution.
Proceedings of the 12th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, 2013

2012
On the Power of Conditional Samples in Distribution Testing.
Electron. Colloquium Comput. Complex., 2012

Monotonicity testing and shortest-path routing on the cube.
Comb., 2012

Improved competitive ratio for the matroid secretary problem.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Junto-Symmetric Functions, Hypergraph Isomorphism and Crunching.
Proceedings of the 27th Conference on Computational Complexity, 2012

2011
Hardness and algorithms for rainbow connection.
J. Comb. Optim., 2011

On the sensitivity of cyclically-invariant Boolean functions.
Discret. Math. Theor. Comput. Sci., 2011

Cycle Detection, Order Finding and Discrete Log with Jumps.
Proceedings of the Innovations in Computer Science, 2011

Efficient Sample Extractors for Juntas with Applications.
Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

2010
Nearly Tight Bounds for Testing Function Isomorphism.
Electron. Colloquium Comput. Complex., 2010

Market Equilibrium with Transaction Costs.
Proceedings of the Internet and Network Economics - 6th International Workshop, 2010

Two-phase Algorithms for the Parametric Shortest Path Problem.
Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science, 2010

New Results on Quantum Property Testing.
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.
Proceedings of the Internet and Network Economics, 5th International Workshop, 2009

Hardness and Algorithms for Rainbow Connectivity.
Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science, 2009

2008
Property Testing of Equivalence under a Permutation Group Action.
Electron. Colloquium Comput. Complex., 2008

2007
Testing <i>st</i> -Connectivity.
Proceedings of the Approximation, 2007

2006
Zero Error List-Decoding Capacity of the <i>q</i>/(<i>q</i>-1) Channel.
Proceedings of the FSTTCS 2006: Foundations of Software Technology and Theoretical Computer Science, 2006

2005
Bounds for Error Reduction with Few Quantum Queries.
Proceedings of the Approximation, 2005


  Loading...