3 papers
cs.DS2026
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 $…
cs.CC2026
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…
cs.CC2025
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…