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…