Author name cluster

Sayantan Sen

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

2 author rows

AAAI Conference 2026 Conference Paper

Instance Dependent Testing of Samplers Using Interval Conditioning

Rishiraj Bhattacharyya
Sourav Chakraborty
Yash Pote
Uddalok Sarkar
Sayantan Sen

Sampling algorithms play a pivotal role in probabilistic AI. However, verifying if a sampler program indeed samples from the claimed distribution is a notoriously hard problem. Provably correct testers like Barbarik,Teq,Flash, Cubeprobe for testing of different kinds of samplers were proposed only in the last few years. All these testers focus on the worst-case efficiency, and do not support verification of samplers over infinite domains, a case occurring frequently in Astronomy, Finance, Network Security etc. In this work, we design the first tester of samplers with instance-dependent efficiency, allowing us to test samplers over natural numbers. Our tests are developed via a novel distance estimation algorithm between an unknown and a known probability distribution using an 'interval conditioning' framework. The core technical contribution is a new connection with probability mass estimation of a continuous distribution. The practical gains are also substantial—our experiments establish up to 1000× speedup over state-of-the-art testers.

PDF Details DOI

NeurIPS Conference 2025 Conference Paper

Distribution Learning Meets Graph Structure Sampling

Arnab Bhattacharyya
Sutanu Gayen
Philips George John
Sayantan Sen
N. V. Vinodchandran

This work establishes a novel link between the problem of PAC-learning high-dimensional graphical models and the task of (efficient) counting and sampling of graph structures, using an online learning framework. The problem of efficiently counting and sampling graphical structures, such as spanning trees and acyclic orientations, has been a vibrant area of research in algorithms. We show that this rich algorithmic foundation can be leveraged to develop new algorithms for learning high-dimensional graphical models. We present the first efficient algorithm for (both realizable and agnostic) learning of Bayes nets with a chordal skeleton. In particular, we present an algorithm that, given integers $k, d > 0$, error parameter $\varepsilon > 0$, an undirected chordal graph $G$ on $n$ vertices, and sample access to a distribution $P^\ast$ on $[k]^n$; (1) returns a Bayes net $\widehat{P}$ with skeleton $G$ and indegree $d$, whose KL-divergence from $P^\ast$ is at most $\varepsilon$ more than the optimal KL-divergence between $P^\ast$ and any Bayes net with skeleton $G$ and indegree $d$, (2) uses $\widetilde{O}(n^3k^{d+1}/\varepsilon^2)$ samples from $P^\ast$ and runs in time $\mathrm{poly}(n, k, \varepsilon^{-1})$ for constant $d$. Prior results in this spirit were for only for trees ($d=1$, tree skeleton) via Chow-Liu, and in the realizable setting for polytrees (arbitrary $d$ but tree skeleton). Thus, our result significantly extends the state-of-the-art in learning Bayes net distributions. We also establish new results for learning tree and polytree distributions.

PDF Details

STOC Conference 2025 Conference Paper

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

Sourav Chakraborty 0001
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.

Details

AAAI Conference 2024 Conference Paper

Testing Self-Reducible Samplers

Rishiraj Bhattacharyya
Sourav Chakraborty
Yash Pote
Uddalok Sarkar
Sayantan Sen

Samplers are the backbone of the implementations of any randomized algorithm. Unfortunately, obtaining an efficient algorithm to test the correctness of samplers is very hard to find. Recently, in a series of works, testers like Barbarik, Teq, Flash for testing of some particular kinds of samplers, like CNF-samplers and Horn-samplers, were obtained. However, their techniques have a significant limitation because one can not expect to use their methods to test for other samplers, such as perfect matching samplers or samplers for sampling linear extensions in posets. In this paper, we present a new testing algorithm that works for such samplers and can estimate the distance of a new sampler from a known sampler (say, the uniform sampler). Testing the identity of distributions is the heart of testing the correctness of samplers. This paper's main technical contribution is developing a new distance estimation algorithm for distributions over high-dimensional cubes using the recently proposed subcube conditioning sampling model. Given subcube conditioning access to an unknown distribution P, and a known distribution Q defined over an n-dimensional Boolean hypercube, our algorithm CubeProbeEst estimates the variation distance between P and Q within additive error using subcube conditional samples from P. Following the testing-via-learning paradigm, we also get a tester that distinguishes between the cases when P and Q are close or far in variation distance with high probability using subcube conditional samples. This estimation algorithm CubeProbeEst in the subcube conditioning sampling model helps us to design the first tester for self-reducible samplers. The correctness of the tester is formally proved. Moreover, we implement CubeProbeEst to test the quality of three samplers for sampling linear extensions in posets.

PDF Details DOI