The tag has no wiki summary.

learn more… | top users | synonyms

2
votes
0answers
47 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 ...
3
votes
1answer
108 views

What is the reason for using a “Lines-Oracle” in the PCP Theorem?

I'm trying to understand the proof of the PCP Theorem in "Complexity and Approximation" by G. Ausiello et al. and came across the low degree test which is used to check if a function $f$ given as ...
2
votes
1answer
66 views

Distance of arbitrary vectors to Hadamard code

Let $n$ be a positive integer and $N = 2^n$. The Hadamrd code of "block length" $N$ can be generated using the inner product $f_u(x) = \langle u,x \rangle$ mod $2$ for all $u \in \{0,1\}^n$. It is ...
10
votes
2answers
438 views

Lower bound on estimating $\sum_{k=1}^n a_k$ for non-increasing $(a_k)_k$

I'd like to know (related to this other question) if lower bounds were known for the following testing problem: one is given query access to a sequence of non-negative numbers $a_n \geq \dots\geq a_1$ ...
2
votes
0answers
153 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 ...
1
vote
1answer
88 views

Hitting set of very restricted linear forms

We say that $f\in\mathbb{Z}[x_{1},\dots,x_{n}]$ is a {-1,0,1}-linear form if $f=\sum_{i\in S}x_{i}-\sum_{i\in T}x_{i}$ where $S,T\subseteq[n]$. A hitting set $H\subseteq\mathbb{Z}^{n}$ for ...
2
votes
1answer
145 views

Determining the number of clusters using property testing algorithm

We say a set of $n$ points in $R^d$ are $k$-clusterable, if all points are covered by k unit balls. We have a property testing algorithm (see section 5 of paper) which consider a promise version of ...
2
votes
0answers
83 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 ...
7
votes
1answer
395 views

Is testing easier/harder than learning?

How is the Property testing is related to PAC model of learning? More precisely, Let we have given a property tester, $\mathcal{A}$, for the (concept) class of function $\mathcal{F_n}$ which ...
9
votes
4answers
444 views

Lower bound for testing closeness in $L_2$ norm?

I was wondering if there was any lower bound (in terms of sample complexity) known for the following problem: Given sample oracle access to two unknown distributions $D_1$, $D_2$ on $\{1,\dots,n\}$, ...
7
votes
4answers
211 views

What is the state of the art in theory of “Software transformations preserving behavior”?

I am interested in the field that could perhaps be referred to as "Automated Refactory" or "Preservation of Software Properties" after a transformation/change/refactory. Saying we have an ...
14
votes
2answers
584 views

Testing for positivity instead of equality

Alice and Bob have n-bit strings, and want to figure out if they're equal while doing little communication. The standard randomized solution is to treat the n-bit strings as polynomials of degree $n$ ...
16
votes
2answers
477 views

Robustness of splitting a junta

We say that a Boolean function $f: \{0,1\}^n \to \{0,1\}$ is a $k$-junta if $f$ has at most $k$ influencing variables. Let $f: \{0,1\}^n \to \{0,1\}$ be a $2k$-junta. Denote the variables of $f$ by ...
5
votes
1answer
119 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 ...
10
votes
0answers
178 views

Are there distribution properties which are “maximally” hard to test?

A distribution testing algorithm for a distribution property P (which is just some subset of all distributions over [n]) is allowed access to samples according to some distribution D, and is required ...
22
votes
1answer
424 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 ...
8
votes
0answers
166 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 ...
2
votes
0answers
94 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 ...
5
votes
0answers
240 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 ...
6
votes
3answers
225 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 ...
17
votes
1answer
414 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 ...
9
votes
2answers
228 views

Property Testing for Independent Sets

Suppose we're given a graph $G$ and parameters $k,\epsilon$. Are there ranges of values for $k$ (or is it doable for all $k$) for which it is possible to test whether $G$ is $\epsilon$-far from having ...
7
votes
1answer
255 views

Property testing of triangular properties

Several years ago I worked a few days with a collaborator on property testing of triangular property. We end up with a disappointing result that I am sharing here and for which I am asking if a better ...
14
votes
1answer
451 views

Sensitivity of Graph Properties

In [1], Turan shows that the sensitivity (called "critical complexity" in the paper) of a graph property is strictly greater than $\lfloor {1\over 4} m \rfloor$ where $m$ is the number of vertices in ...
18
votes
2answers
301 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:{0,1}^n -> R to distinguish between two cases: 1) f is a member of some ...