5 papers
Testing Connectedness and Edge Connectedness
Diptaksho Palit, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova +1
We revisit the classical problem of testing connectedness of graphs represented in the adjacency lists model and obtain optimal bounds. Specifically, we show that -tes…
Query Complexity of Testing Structured Parenthesis Languages
Tim Jackman, Diptaksho Palit, Sofya Raskhodnikova
We study the query complexity of testing membership in structured string languages, focusing on Dyck languages and natural generalizations. A tester receives query access to a word…
Testing k-submodularity
Themistoklis Haris, Diptaksho Palit
We initiate the study of property testing for -submodular functions, a higher-dimensional analogue of submodular functions defined on partial partitions of a ground set. While $…
Relative-error unateness testing
Xi Chen, Diptaksho Palit, Kabir Peshawaria +3
The model of relative-error property testing of Boolean functions has been the subject of significant recent research effort [CDH+24][CPPS25a][CPPS25b] In this paper we consider th…
Computational Complexity in Property Testing
Renato Ferreira Pinto, Diptaksho Palit, Sofya Raskhodnikova
We initiate a systematic study of the computational complexity of property testing, focusing on the relationship between query and time complexity. While traditional work in proper…