Sayantan Sen

Hi, I am Sayantan Sen. I am currently a Research Fellow (postdoc) at School of Computing, National University of Singapore, advised by Prof. Arnab Bhattacharyya. I finished my PhD at Indian Statistical Institute where I was fortunate to be advised by Prof. Sourav Chakraborty.  I obtained my Master's degree from Chennai Mathematical Institute (CMI), India. Before that, I obtained my bachelor's degree from Jadavpur University, India.

Research Interest

My field of research lies broadly in Theoretical Computer Science, more specifically in Randomized Algorithm. I am currently working in Property Testing, where the main focus is to design efficient sampling and query algorithms for various distribution and graph problems.

Publication  [dblp] [google scholar]

1. Testing Self-Reducible Samplers [arxiv]

      Joint work with Rishiraj Bhattacharyya, Sourav Chakraborty, Yash Pote and Uddalok Sarkar

     To appear in the 38th Annual AAAI Conference on Artificial Intelligence (AAAI), 2024.

2. Testing of Index-Invariant Properties in the Huge Object Model [arxiv] [eccc] [conference version]

      Joint work with Sourav Chakraborty, Eldar Fischer, Arijit Ghosh and Gopinath Mishra

     Conference on Learning Theory (COLT), 2023.

     Featured in Oded Goldreich's Choices.

3. A (simple) classical algorithm for estimating Betti numbers [arxiv] [journal version]

Joint work with Simon Apers, Sander Gribling and Dániel Szabó

     Quantum 1202, Volume 7, 2023.

     Quantum Computing Theory in Practice (QCTiP), 2023.

4. Testing of Horn Samplers [Conference version]

Joint work with Ansuman Banerjee, Shayak Chakraborty, Sourav Chakraborty, Kuldeep S. Meel and Uddalok Sarkar

International Conference on Artificial Intelligence and Statistics (AISTATS), 2023.

5. Exploring the Gap between Tolerant and Non-tolerant Distribution Testing [arxiv] [conference version]

Joint work with Sourav Chakraborty, Eldar Fischer, Arijit Ghosh and Gopinath Mishra

International Conference on Randomization and Computation (RANDOM), 2022. [Conference Talk]

     Highlights of Algorithms (HALG), 2023.

6. Tolerant Bipartiteness Testing in Dense Graphs [arxiv] [conference version]

     Joint work with Arijit Ghosh, Gopinath Mishra and Rahul Raychaudhury

     International Colloquium on Automata, Languages and Programming (ICALP), 2022. 

     Highlights of Algorithms (HALG), 2023.

7.  Interplay between Graph Isomorphism and Earth Mover’s Distance in the Query and Communication Worlds [eccc][conference version]

         Joint work with Sourav Chakraborty, Arijit Ghosh and Gopinath Mishra

       International Conference on Randomization and Computation (RANDOM), 2021. [Conference Talk] 

       Highlights of Algorithms (HALG), 2022.

My PhD. Thesis: Sample and Query Complexities of Some Estimation Problems

Talks

1. Interplay between Graph Isomorphism and Earth Mover’s Distance in the Query and Communication Worlds

          Presented at Not-so-local local algorithms,  an online talk series on sublinear algorithm.

          Talk at Highlights of Algorithms (HALG), 2022.

         Poster at Workshop on Local Algorithms, 2021.

2.  Tolerant Bipartiteness Testing in Dense Graphs

Talk at ICALP, 2022.

Talk at IRIF Seminar, 2022.

Talk at University of Sydney Theory Seminar, 2023.

Poster Presentation at Highlights of Algorithms (HALG), 2023.

3. Exploring the Gap between Tolerant and Non-tolerant Distribution Testing

Talk at Indian Institute of Science (IISc) Theory Seminar, 2022.

Talk at RANDOM, 2022.

Poster Presentation at Highlights of Algorithms (HALG), 2023.

4. Testing of Index-Invariant Properties in the Huge Object Model

Talk at COLT, 2023.

5. A Tale of Distribution Testing

Talk at IIT Kanpur Seminar, 2023.

Talk at IIT Kharagpur Seminar, 2023.