# Tagged Questions

The tag has no usage guidance.

105 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 ...
117 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 ...
100 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 ...
471 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$ ...
168 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 ...
99 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 ...
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 ...
89 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 ...
404 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 ...
478 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\}$, ...
215 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 ...
601 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$ ...
483 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 ...
124 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 ...
179 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 ...
432 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 ...
171 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 ...
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 ...
255 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 ...
233 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 ...
178 views

### Invariance in Property Testing

A property is said to be invariant under a permutation $\pi$ if permuting the data points by this permutation leaves the property unchanged. Invariance under permutations seems to help with property ...
421 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 ...
233 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 ...
262 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 ...
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 ...