Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Erasure-Resilient Property Testing:
TR18-195 | 18th November 2018
Sofya Raskhodnikova, Noga Ron-Zewi, Nithin Varma

Erasures versus Errors in Local Decoding and Property Testing

We initiate the study of the role of erasures in local decoding and use our understanding to prove a separation between erasure-resilient and tolerant property testing. Local decoding in the presence of errors has been extensively studied, but has not been considered explicitly in the presence of erasures.

Motivated by ... more >>>

TR19-163 | 16th November 2019
Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Erik Waingarten

Approximating the Distance to Monotonicity of Boolean Functions

We design a nonadaptive algorithm that, given a Boolean function $f\colon \{0,1\}^n \to \{0,1\}$ which is $\alpha$-far from monotone, makes poly$(n, 1/\alpha)$ queries and returns an estimate that, with high probability, is an $\widetilde{O}(\sqrt{n})$-approximation to the distance of $f$ to monotonicity. Furthermore, we show that for any constant $\kappa > ... more >>>

TR20-190 | 29th November 2020
Amit Levi, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma

Erasure-Resilient Sublinear-Time Graph Algorithms

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 graph and work with a specified fraction of adversarial erasures in adjacency entries. We focus on two computational tasks: testing if a graph is connected ... more >>>

ISSN 1433-8092 | Imprint