45 citations · 115 across the 24 of their papers we have counts for
Showing cs.CCShow all
2 papers · 1 filter
cs.CC2025
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.CC2017★ 5 cited
A Lower Bound for Nonadaptive, One-Sided Error Testing of Unateness of Boolean Functions over the Hypercube
Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor +2
A Boolean function is unate if, along each coordinate, the function is either nondecreasing or nonincreasing. In this note, we prove that any nonadapt…