9 citations · 12 across the 6 of their papers we have counts for
12 papers
Near-optimal quantum query lower bounds on bipartiteness and expansion testing in the bounded-degree graph model
Chandrima Kayal, Sayantan Sen, Dániel Szabó
In this work, we study bipartiteness and expansion testing, two canonical problems in graph property testing in the bounded-degree model through the lens of quantum query complexit…
Private Graph Property Testing
Hendrik Fichtenberger, Abigail Gentle, Tamalika Mukherjee +1
Graph property testing asks whether a massive graph satisfies a given property, or is far from doing so, using only a sublinear number of queries to the graph. Since property teste…
Instance Dependent Testing of Samplers using Interval Conditioning
Rishiraj Bhattacharyya, Sourav Chakraborty, Yash Pote +2
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. Pro…
Testing vs Estimation for Index-Invariant Properties in the Huge Object Model
Sourav Chakraborty, Eldar Fischer, Arijit Ghosh +3
The Huge Object model of property testing [Goldreich and Ron, TheoretiCS 23] concerns properties of distributions supported on , where is so large that even reading…
Quantum property testing in sparse directed graphs
Simon Apers, Frédéric Magniez, Sayantan Sen +1
We initiate the study of quantum property testing in sparse directed graphs, and more particularly in the unidirectional model, where the algorithm is allowed to query only the out…
Near Uniform Triangle Sampling Over Adjacency List Graph Streams
Arijit Bishnu, Arijit Ghosh, Gopinath Mishra +1
Triangle counting and sampling are two fundamental problems for streaming algorithms. Arguably, designing sampling algorithms is more challenging than their counting variants. It m…
Testing Self-Reducible Samplers
Rishiraj Bhattacharyya, Sourav Chakraborty, Yash Pote +2
Samplers are the backbone of the implementations of any randomised algorithm. Unfortunately, obtaining an efficient algorithm to test the correctness of samplers is very hard to fi…
A (simple) classical algorithm for estimating Betti numbers
Simon Apers, Sander Gribling, Sayantan Sen +1
We describe a simple algorithm for estimating the -th normalized Betti number of a simplicial complex over elements using the path integral Monte Carlo method. For a general…
Testing of Index-Invariant Properties in the Huge Object Model
Sourav Chakraborty, Eldar Fischer, Arijit Ghosh +2
The study of distribution testing has become ubiquitous in the area of property testing, both for its theoretical appeal, as well as for its applications in other fields of Compute…
Tolerant Bipartiteness Testing in Dense Graphs
Arijit Ghosh, Gopinath Mishra, Rahul Raychaudhury +1
Bipartite testing has been a central problem in the area of property testing since its inception in the seminal work of Goldreich, Goldwasser and Ron [FOCS'96 and JACM'98]. Though…
Exploring the Gap between Tolerant and Non-tolerant Distribution Testing
Sourav Chakraborty, Eldar Fischer, Arijit Ghosh +2
The framework of distribution testing is currently ubiquitous in the field of property testing. In this model, the input is a probability distribution accessible via independently…
A Faster Algorithm for Max Cut in Dense Graphs
Arijit Ghosh, Gopinath Mishra, Rahul Raychaudhury +1
We design an algorithm for approximating the size of \emph{Max Cut} in dense graphs. Given a proximity parameter , our algorithm approximates the size of \em…