Questions tagged [property-testing]

The tag has no usage guidance.

7 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
7
votes
0answers
182 views

Testing the degree of a vertex

Let's say we have a graph $G$ with $n$ vertices. Given $\epsilon>0$ and a specific vertex $v$, consider the problem of deciding whether $\mathrm{deg}(v) < \frac{\epsilon}{3}n$ or $\mathrm{deg}(v)...
5
votes
0answers
178 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 ...
5
votes
0answers
288 views

Sublinear time algorithm for maximum degree node

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 ...
3
votes
0answers
213 views

Testing sortedness of a normalized list of $n$ numbers

It is known that testing whether a list of $n$ arbitrary real numbers is $\varepsilon$-close of being sorted (in Hamming distance) has query complexity $\Theta(\log n)$ [1]. It is also easy to show ...
2
votes
0answers
113 views

Universal constant for bivariate testing

In the seminal paper of Polishchuk and Spielman where they give a construction of nearly linear sized $PCP$ for an $NP$ problem, one of the key ingredients is a low-degree test for bivariate ...
2
votes
0answers
103 views

Hardness vs testability ?

How does hardness plays role in testability? Intuitively, it seems that for the problems which have exact efficient algorithm, there is more hope to get constant query (or, relatively a small number ...
2
votes
0answers
95 views

Catching the complexity of determining some recursively defined property

I am currently working on some property defined in the following way. Let $S$ be a set of positive integers. We say that $S$ has the property $P$ iff one of the following two conditions holds. This ...