Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > TOLERANT PROPERTY TESTING:
Reports tagged with Tolerant Property Testing:
TR18-195 | 18th November 2018
Sofya Raskhodnikova, Noga Ron-Zewi, Nithin Varma

#### Erasures versus Errors in Local Decoding and Property Testing

Revisions: 1

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 >>>

TR20-149 | 29th September 2020
Oded Goldreich, Avi Wigderson

#### Robustly Self-Ordered Graphs: Constructions and Applications to Property Testing

Revisions: 2

A graph $G$ is called {\em self-ordered}\/ (a.k.a asymmetric) if the identity permutation is its only automorphism.
Equivalently, there is a unique isomorphism from $G$ to any graph that is isomorphic to $G$.
We say that $G=(V,E)$ is {\em robustly self-ordered}\/ if the size of the symmetric difference ... more >>>

TR21-004 | 10th January 2021
Vishnu Iyer, Avishay Tal, Michael Whitmeyer

#### Junta Distance Approximation with Sub-Exponential Queries

Leveraging tools of De, Mossel, and Neeman [FOCS, 2019], we show two different results pertaining to the tolerant testing of juntas. Given black-box access to a Boolean function $f:\{\pm1\}^{n} \to \{\pm1\}$ we give a poly$(k, \frac{1}{\varepsilon})$ query algorithm that distinguishes between functions that are $\gamma$-close to $k$-juntas and $(\gamma+\varepsilon)$-far from ... more >>>

TR21-005 | 13th January 2021
Anindya De, Elchanan Mossel, Joe Neeman

#### Robust testing of low-dimensional functions

A natural problem in high-dimensional inference is to decide if a classifier $f:\mathbb{R}^n \rightarrow \{-1,1\}$ depends on a small number of linear directions of its input data. Call a function $g: \mathbb{R}^n \rightarrow \{-1,1\}$, a linear $k$-junta if it is completely determined by some $k$-dimensional subspace of the input space. ... more >>>

ISSN 1433-8092 | Imprint