25 citations · 48 across the 16 of their papers we have counts for
4 papers · 1 filter
Homomorphism Testing with Resilience to Online Manipulations
Esty Kelman, Uri Meir, Debanuj Nayak +1
A central challenge in property testing is verifying algebraic structure with minimal access to data. A landmark result addressing this challenge, the linearity test of Blum, Luby,…
Fast Agnostic Learners in the Plane
Talya Eden, Ludmila Glinskih, Sofya Raskhodnikova
We investigate the computational efficiency of agnostic learning for several fundamental geometric concept classes in the plane. While the sample complexity of agnostic learning is…
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…
Privately Evaluating Untrusted Black-Box Functions
Ephraim Linder, Sofya Raskhodnikova, Adam Smith +1
We provide tools for sharing sensitive data when the data curator does not know in advance what questions an (untrusted) analyst might ask about the data. The analyst can specify a…