Seminars
View all Seminars | Download ICal for this eventTesting Self-Reducible Samplers
Series: Bangalore Theory Seminars
Speaker: Uddalok Sarkar, ISI Kolkata
Date/Time: Mar 07 16:00:00
Location: CSA Lecture Hall (Room No. 112, Ground Floor)
Abstract:
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 ????????????, ????, ??????? 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 talk, we will see a new testing algorithm that works for a broader class of samplers and can estimate the distance of a sampler from a known sampler (say, uniform sampler). Testing the identity of distributions is the heart of testing the correctness of samplers. This works main technical contribution is developing a new distance estimation algorithm for distributions over high-dimensional cubes using the recently proposed sub-cube conditioning sampling model. Given subcube conditioning access to an unknown distribution P and a known distribution Q defined over {0,1}^n, our algorithm ???????????????? estimates the variation distance between P and Q within an additive error using O(n^2) subcube conditional samples from P. Through this work, we bridge the gap between theoretical guarantees and practical validation, paving the way for more reliable randomized algorithms.
Microsoft Teams link:
Link
We are grateful to the Kirani family (Link and the Walmart Center for Tech Excellence (Link for generously supporting this seminar series
Hosts: Rameesh Paul, KVN Sreenivas, Rahul Madhavan, Debajyoti Kar