SCSourav Chakraborty

Sourav Chakraborty

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Sourav Chakraborty has a total of 56 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • On the Composition of Randomized Query Complexity and Approximate Degree

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

  • Open Access

    Representation Obliviousness and Pseudodeterminism in Streaming Algorithms

    by Michael Chen, Sourav Chakraborty, A. Pavan, N. V. Vinodchandran

    In this work, we study the notion of representation obliviousness in the context of pseudodeterministic streaming algorithms. A (randomized) streaming algorithm A is pseudodeterministic, if for every stream D, there is a ''canonical value'' g(D) so that with probability at least 2/3, A on input stream D outputs g(D). Intuitively, a randomized algorithm is representation oblivious if the output distribution of the algorithm does not depend on the representation of the input. We investigate this notion in the context of streaming algorithms, more specifically, distinct elements estimation (F 0 estimation) in data streams. In this context, representation obliviousness captures the idea that the output distribution of an algorithm for estimating F 0 should only depend on the set of distinct elements of the stream. This is a natural notion, as we note that standard streaming algorithms are representation-oblivious in this sense. We prove that any representation oblivious pseudodeterministic streaming algorithm for estimating F 0 must use Ω(n) space, where [n] is the universe. More generally, we prove that any representation oblivious pseudodeterministic t(n)-pass streaming algorithm requires Ω(n/t(n)) space. This lower bound matches the space requirement of the straightforward multi-pass deterministic algorithm that exactly computes F 0 .

  • Open Access

    Assessing the Quality of Binomial Samplers: A Statistical Distance Framework

    by Uddalok Sarkar, Sourav Chakraborty, Kuldeep S. Meel

    Randomized algorithms depend on accurate sampling from probability distributions, as their correctness and performance hinge on the quality of the generated samples. However, even for common distributions like Binomial, exact sampling is computationally challenging, leading standard library implementations to rely on heuristics. These heuristics, while efficient, suffer from approximation and system representation errors, causing deviations from the ideal distribution. Although seemingly minor, such deviations can accumulate in downstream applications requiring large-scale sampling, potentially undermining algorithmic guarantees. In this work, we propose statistical distance as a robust metric for analyzing the quality of Binomial samplers, quantifying deviations from the ideal distribution. We derive rigorous bounds on the statistical distance for standard implementations and demonstrate the practical utility of our framework by enhancing APSEst, a DNF model counter, with improved reliability and error guarantees. To support practical adoption, we propose an interface extension that allows users to control and monitor statistical distance via explicit input/output parameters. Our findings emphasize the critical need for thorough and systematic error analysis in sampler design. As the first work to focus exclusively on Binomial samplers, our approach lays the groundwork for extending rigorous analysis to other common distributions, opening avenues for more robust and reliable randomized algorithms.


  • Open Access

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

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

  • Open Access

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

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

    The Huge Object model of property testing [Goldreich and Ron, TheoretiCS 23] concerns properties of distributions supported on $\{0,1\}^n$, where $n$ is so large that even reading a single sampled string is unrealistic. Instead, query access is provided to the samples, and the efficiency of the algorithm is measured by the total number of queries that were made to them. Index-invariant properties under this model were defined in [Chakraborty et al., COLT 23], as a compromise between enduring the full intricacies of string testing when considering unconstrained properties, and giving up completely on the string structure when considering label-invariant properties. Index-invariant properties are those that are invariant through a consistent reordering of the bits of the involved strings. Here we provide an adaptation of Szemerédi's regularity method for this setting, and in particular show that if an index-invariant property admits an $ε$-test with a number of queries depending only on the proximity parameter $ε$, then it also admits a distance estimation algorithm whose number of queries depends only on the approximation parameter.


  • Open Access

    On characterization and recognition of proper tagged probe interval graphs

    by Sanchita Paul, Shamik Ghosh, Sourav Chakraboty, Malay Sen

    Interval graphs were used in the study of the human genome project by the molecular biologist Benzer. Later on probe interval graphs were introduced by Zhang as a generalization of interval graphs for the study of cosmid contig mapping of DNA. Further research in this area required more useful and cost-effective tools. The concept of tagged probe interval graphs is motivated from this point of view. In this paper, we consider a natural subclass of it, namely, the class of proper tagged probe interval graphs. In this paper, we present a characterization theorem and a linear time recognition algorithm for proper tagged probe interval graphs. Also, we discuss the interrelations between the classes of proper tagged probe interval graphs and tagged probe interval graphs with probe interval graphs and probe proper interval graphs.


  • A Scalable t-Wise Coverage Estimator: Algorithms and Applications

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

    Owing to the pervasiveness of software in our modern lives, software systems have evolved to be highly configurable. Combinatorial testing has emerged as a dominant paradigm for testing highly configurable systems. Often constraints are employed to define the environments where a given system is expected to work. Therefore, there has been a sustained interest in designing constraint-based test suite generation techniques. A significant goal of test suite generation techniques is to achieve t -wise coverage for higher values of t . Therefore, designing scalable techniques that can estimate t -wise coverage for a given set of tests and/or the estimation of maximum achievable t -wise coverage under a given set of constraints is of crucial importance. The existing estimation techniques face significant scalability hurdles. We designed scalable algorithms with mathematical guarantees to estimate (i) t-wise coverage for a given set of tests, and (ii) maximum t-wise coverage for a given set of constraints. In particular, ApproxCov takes in a test set $\mathcal{U}$ and returns an estimate of the t-wise coverage of $\mathcal{U}$ that is guaranteed to be within (1 ± ε)-factor of the ground truth with probability at least $1 - \delta$ for a given tolerance parameter ε and a confidence parameter $\delta$. A scalable framework ApproxMaxCov for a given formula F outputs an approximation which is guaranteed to be within (1 ± ε) factor of the maximum achievable t-wise coverage under F, with probability $\ge 1 - \delta$ for a given tolerance parameter ε and a confidence parameter $\delta$. Our comprehensive evaluation demonstrates that ApproxCov and ApproxMaxCov can handle benchmarks that are beyond the reach of current state-of-the-art approaches. In this paper we present proofs of correctness of ApproxCov, ApproxMaxCov, and of their generalizations.We show how the algorithms can improve the scalability of a test suite generator while maintaining its effectiveness. In addition, we compare several test suite generators on different feature combination sizes t.


  • Open Access

    On the Feasibility of Forgetting in Data Streams

    by A. Pavan, Sourav Chakraborty, N. V. Vinodchandran, Kuldeep S Meel

    In today's digital age, it is becoming increasingly prevalent to retain digital footprints in the cloud indefinitely. Nonetheless, there is a valid argument that entities should have the authority to decide whether their personal data remains within a specific database or is expunged. Indeed, nations across the globe are increasingly enacting legislation to uphold the "Right To Be Forgotten" for individuals. Investigating computational challenges, including the formalization and implementation of this notion, is crucial due to its relevance in the domains of data privacy and management. This work introduces a new streaming model: the 'Right to be Forgotten Data Streaming Model' (RFDS model). The main feature of this model is that any element in the stream has the right to have its history removed from the stream. Formally, the input is a stream of updates of the form (a, Δ) where Δ ∈ {+, ⊥} and a is an element from a universe U. When the update Δ=+ occurs, the frequency of a, denoted as f a , is incremented to f a +1. When the update Δ=⊥, occurs, f a is set to 0. This feature, which represents the forget request, distinguishes the present model from existing data streaming models. This work systematically investigates computational challenges that arise while incorporating the notion of the right to be forgotten. Our initial considerations reveal that even estimating F 1 (sum of the frequencies of elements) of the stream is a non-trivial problem in this model. Based on the initial investigations, we focus on a modified model which we call α-RFDS where we limit the number of forget operations to be at most α fraction. In this modified model, we focus on estimating F 0 (number of distinct elements) and F 1 . We present algorithms and establish almost-matching lower bounds on the space complexity for these computational tasks.


  • Open Access

    A faster FPRAS for #NFA

    by Kuldeep S. Meel, Sourav Chakraborty, Umang Mathur

    Given a non-deterministic finite automaton (NFA) A with m states, and a natural number n (presented in unary), the #NFA problem asks to determine the size of the set L(A,n) of words of length n accepted by A. While the corresponding decision problem of checking the emptiness of L(A,n) is solvable in polynomial time, the #NFA problem is known to be #P-hard. Recently, the long-standing open question --- whether there is an FPRAS (fully polynomial time randomized approximation scheme) for #NFA --- was resolved by Arenas, Croquevielle, Jayaram, and Riveros in [ACJR19]. The authors demonstrated the existence of a fully polynomial randomized approximation scheme with a time complexity of ~O(m 17 n 17 • 1/ε 14 • log (1/δ)), for a given tolerance ε and confidence parameter δ. Given the prohibitively high time complexity in terms of each of the input parameters, and considering the widespread application of approximate counting (and sampling) in various tasks in Computer Science, a natural question arises: is there a faster FPRAS for #NFA that can pave the way for the practical implementation of approximate #NFA tools? In this work, we answer this question in the positive. We demonstrate that significant improvements in time complexity are achievable, and propose an FPRAS for #NFA that is more efficient in terms of both time and sample complexity. A key ingredient in the FPRAS due to Arenas, Croquevielle, Jayaram, and Riveros [ACJR19] is inter-reducibility of sampling and counting, which necessitates a closer look at the more informative measure --- the number of samples maintained for each pair of state q and length i <= n. In particular, the scheme of [ACJR19] maintains O(m 7 /n 7 ε 7 ) samples per pair of state and length. In the FPRAS we propose, we systematically reduce the number of samples required for each state to be only poly-logarithmically dependent on m, with significantly less dependence on n and ε, maintaining only ~O(n 4 /ε 2 ) samples per state. Consequently, our FPRAS runs in time ~O((m 2 n 10 + m 3 n 6 ) • 1/ε 4 • log 2 (1/δ)). The FPRAS and its analysis use several novel insights. First, our FPRAS maintains a weaker invariant about the quality of the estimate of the number of samples for each state q and length i <= n. Second, our FPRAS only requires that the distribution of the samples maintained is close to uniform distribution only in total variation distance (instead of maximum norm). We believe our insights may lead to further reductions in time complexity and thus open up a promising avenue for future work towards the practical implementation of tools for approximate #NFA.