# Questions tagged [property-testing]

The tag has no usage guidance.

34 questions
Filter by
Sorted by
Tagged with
478 views

### Natural, untestable graph properties

In graph property testing, an algorithm queries a target graph for the presence or absence of edges and needs to determine whether the target either has a certain property or is $\epsilon$-far from ...
407 views

### Property testing in other metrics?

There is a large literature on "property testing" -- the problem of making a small number of black box queries to a function $f\colon\{0,1\}^n \to R$ to distinguish between two cases: $f$ is a ...
480 views

### Using the extra power of the negative adversary method

The negative adversary method ($ADV^\pm$) is an SDP that characterizes quantum query complexity. It is a generalization of the widely used adversary method ($ADV$), and overcomes the two barriers that ...
782 views

254 views

### Asymmetry in Property Testing Definition

Property Testing refers to the problem of making a small number of queries to determine whether $x$ is in some language $L$ or whether it is far away from being in $L$. More precisely we want to ...
132 views

### Testing low degree bivariate polynomials

Let $d,q \in \mathbb{N}$, and let $f:\mathrm{GF}(q) \to \mathrm{GF}(q)$ be a univariate polynomial. In this case, it is possible to test whether $f$ is of degree at most $d$ (or whether $f$ is at ...
186 views

### Generalization of Element Distinctness

In the element distinctness problem, one has query access to an arbitrary multiset of $n$ elements and must decide whether they are all distinct. From a property testing point of view, the question is:...
Here is a quick algorithmic problem: given a graph $G=(V,E)$ such that for each two distinct nodes $u,v \in V$ there's exactly one directed edge between them, and a probability $p$, such that each ...