SCS Guest Seminar: Sourav Chakraborty

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

Speaker:  Sourav Chakraborty, Professor, Indian Statistical Institute

Abstract: 

The problem of testing whether an input satisfies a given property can be significantly easier than estimating the input’s distance from having that property. However, for certain classes of properties, these tasks may be quite similar.

One of the newer models for testing distribution properties is the huge object model, introduced by Goldreich and Ron in 2023. In this talk, we investigate the query complexity of testing index-invariant properties within this model. We adapt Szemerédi’s regularity method to this setting and prove that, for index-invariant properties, constant query testability implies constant-query estimability.

This talk is based on the following works:

1. “Testing vs Estimation for Index-Invariant Properties in the Huge Object

Model,” joint work with Eldar Fischer, Arijit Ghosh, Amit Levi, Gopinath Mishra,

and Sayantan Sen, STOC 2025.

2. “Testing of Index-Invariant Properties in the Huge Object Model,” joint work

with Eldar Fischer, Arijit Ghosh, Gopinath Mishra, and Sayantan Sen, COLT 2023

Bio:

Sourav Chakraborty is a Professor in the Advanced Computing and Microelectronics Unit (ACMU) of the Computer and Communication Sciences Division (CCSD) at the Indian Statistical Institute (ISI), Kolkata, India. Before joining ISI in July 2018, he was a faculty member at the Chennai Mathematical Institute, India, from September 2010. He completed his PhD in Computer Science in June 2008 at the University of Chicago under the supervision of Prof. László Babai and did postdoctoral stints at Technion, Israel, and CWI, Amsterdam.