We design a nonadaptive algorithm that, given oracle access to a function which is‐far from
monotone, makes poly queries and returns an estimate that, with high probability, is an …

Estimating the length of the longest increasing subsequence (LIS) in an array is a problem of
fundamental importance. Despite the significance of the LIS estimation problem and the …

We show that there exist properties that are maximally hard for testing, while still admitting
PCPPs with a proof size very close to linear. Specifically, for every fixed $\ell $, we construct …

We initiate the study of sublinear-time algorithms that access their input via an online
adversarial erasure oracle. After answering each query to the input object, such an oracle …

In the t-online-erasure model in property testing, an adversary is allowed to erase t values of
a queried function for each query the tester makes. This model was recently formulated by …

The online manipulation-resilient testing model, proposed by Kalemaj, Raskhodnikova and
Varma (ITCS 2022 and Theory of Computing 2023), studies property testing in situations …

We investigate sublinear-time algorithms that take partially erased graphs represented by
adjacency lists as input. Our algorithms make degree and neighbor queries to the input …

We study property testing with incomplete or noisy inputs. The models we consider allow for
adversarial manipulation of the input, but differ in whether the manipulation can be done …

In this work, we study the problem of approximating the distance to subsequence-freeness in
the sample-based distribution-free model. For a given subsequence (word) w= w 1… wk, a …

We initiate a systematic study of tolerant testers of image properties or, equivalently,
algorithms that approximate the distance from a given image to the desired property. Image …