Property Testing with Incomplete or Manipulated Inputs

Explore property testing techniques for scenarios involving incomplete or manipulated inputs in this 44-minute lecture by Sofya Raskhodnikova. Delve into the model of testing with online adversaries, which extends the concept of tolerant testers. Examine how sublinear-time algorithms interact with online adversarial erasure or corruption oracles, and understand the complexity of fundamental computational tasks in this context. Compare this model to offline property testing approaches and gain insights from joint research works on the subject. Learn about the challenges and strategies for property testing when faced with adversarial input manipulation in this advanced computer science talk from the Simons Institute's Workshop on Local Algorithms.

Property Testing with Incomplete or Manipulated Inputs