Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, Alex Samorodnitsky

We present improved algorithms for testing monotonicity of functions.

Namely, given the ability to query an unknown function $f$, where

$\Sigma$ and $\Xi$ are finite ordered sets, the test always accepts a

monotone $f$, and rejects $f$ with high probability if it is $\e$-far

from being monotone (i.e., every ...
more >>>

Oded Goldreich, Dana Ron

We consider testing graph expansion in the bounded-degree graph model.

Specifically, we refer to algorithms for testing whether the graph

has a second eigenvalue bounded above by a given threshold

or is far from any graph with such (or related) property.

We present a natural algorithm aimed ... more >>>

Eldar Fischer

Let $P$ be a property of graphs. An $\epsilon$-test for $P$ is a

randomized algorithm which, given the ability to make queries whether

a desired pair of vertices of an input graph $G$ with $n$ vertices are

adjacent or not, distinguishes, with high probability, between the

case of $G$ satisfying ...
more >>>

Eldar Fischer

An $\epsilon$-test for a property $P$ of functions from

${\cal D}=\{1,\ldots,d\}$ to the positive integers is a randomized

algorithm, which makes queries on the value of an input function at

specified locations, and distinguishes with high probability between the

case of the function satisfying $P$, and the case that it ...
more >>>

Oded Goldreich, Luca Trevisan

Property testing is a relaxation of decision problems

in which it is required to distinguish {\sc yes}-instances

(i.e., objects having a predetermined property) from instances

that are far from any {\sc yes}-instance.

We presents three theorems regarding testing graph

properties in the adjacency matrix representation. ...
more >>>

Sophie Laplante, Richard Lassaigne, Frederic Magniez, Sylvain Peyronnet, Michel de Rougemont

In model checking, program correctness on all inputs is verified

by considering the transition system underlying a given program.

In practice, the system can be intractably large.

In property testing, a property of a single input is verified

by looking at a small subset of that input.

We ...
more >>>

Michal Parnas, Dana Ron, Alex Samorodnitsky

We consider the problem of determining whether a given

function f : {0,1}^n -> {0,1} belongs to a certain class

of Boolean functions F or whether it is far from the class.

More precisely, given query access to the function f and given

a distance parameter epsilon, we would ...
more >>>

Andrej Bogdanov, Luca Trevisan

We consider the problem of testing bipartiteness in the adjacency

matrix model. The best known algorithm, due to Alon and Krivelevich,

distinguishes between bipartite graphs and graphs that are

$\epsilon$-far from bipartite using $O((1/\epsilon^2)polylog(1/epsilon)$

queries. We show that this is optimal for non-adaptive algorithms,

up to the ...
more >>>

Eli Ben-Sasson, Prahladh Harsha, Sofya Raskhodnikova

For a boolean formula \phi on n variables, the associated property

P_\phi is the collection of n-bit strings that satisfy \phi. We prove

that there are 3CNF properties that require a linear number of queries,

even for adaptive tests. This contrasts with 2CNF properties

that are testable with O(\sqrt{n}) ...
more >>>

Michael Langberg

A $k$-uniform hypergraph $G$ of size $n$ is said to be $\varepsilon$-far from having an independent set of size $\rho n$ if one must remove at least $\varepsilon n^k$ edges of $G$ in order for the remaining hypergraph to have an independent set of size $\rho n$. In this work, ... more >>>

Michal Parnas, Dana Ron, Ronitt Rubinfeld

A standard property testing algorithm is required to determine

with high probability whether a given object has property

P or whether it is \epsilon-far from having P, for any given

distance parameter \epsilon. An object is said to be \epsilon-far

from having ...
more >>>

Michael Ben Or, Don Coppersmith, Michael Luby, Ronitt Rubinfeld

In this paper, we study two questions related to

the problem of testing whether a function is close to a homomorphism.

For two finite groups $G,H$ (not necessarily Abelian),

an arbitrary map $f:G \rightarrow H$, and a parameter $0 < \epsilon <1$,

say that $f$ is $\epsilon$-close to a homomorphism ...
more >>>

Nir Ailon, Bernard Chazelle

In general property testing, we are given oracle access to a function $f$, and we wish to randomly test if the function satisfies a given property $P$, or it is $\epsilon$-far from having that property. In a more general setting, the domain on which the function is defined is equipped ... more >>>

Eldar Fischer, Frederic Magniez, Michel de Rougemont

Using a new statistical embedding of words which has similarities with the Parikh mapping, we first construct a tolerant tester for the equality of two words, whose complexity is independent of the string size, where the distance between inputs is measured by the normalized edit distance with moves. As a ... more >>>

Oded Goldreich

We survey known results regarding locally testable codes

and locally testable proofs (known as PCPs),

with emphasis on the length of these constructs.

Locally testability refers to approximately testing

large objects based on a very small number of probes,

each retrieving a single bit in the ...
more >>>

Oded Goldreich

The notion of promise problems was introduced and initially studied

by Even, Selman and Yacobi

(Information and Control, Vol.~61, pages 159-173, 1984).

In this article we survey some of the applications that this

notion has found in the twenty years that elapsed.

These include the notion ...
more >>>

Venkatesan Guruswami, Atri Rudra

An error-correcting code is said to be {\em locally testable} if it has an

efficient spot-checking procedure that can distinguish codewords

from strings that are far from every codeword, looking at very few

locations of the input in doing so. Locally testable codes (LTCs) have

generated ...
more >>>

Asaf Shapira, Noga Alon

Property-testers are fast randomized algorithms for distinguishing

between graphs (and other combinatorial structures) satisfying a

certain property, from those that are far from satisfying it. In

many cases one can design property-testers whose running time is in

fact {\em independent} of the size of the input. In this paper we

more >>>

Eldar Fischer, Orly Yahalom

A coloring of a graph is {\it convex} if it

induces a partition of the vertices into connected subgraphs.

Besides being an interesting property from a theoretical point of

view, tests for convexity have applications in various areas

involving large graphs. Our results concern the important subcase

of testing for ...
more >>>

Oded Goldreich, Or Sheffet

We initiate a general study of the randomness complexity of

property testing, aimed at reducing the randomness complexity of

testers without (significantly) increasing their query complexity.

One concrete motovation for this study is provided by the

observation that the product of the randomness and query complexity

of a tester determine ...
more >>>

Oded Goldreich

Motivated by a recent study of Zimand (22nd CCC, 2007),

we consider the average-case complexity of property testing

(focusing, for clarity, on testing properties of Boolean strings).

We make two observations:

1) In the context of average-case analysis with respect to

the uniform distribution (on all strings of ...
more >>>

Tali Kaufman, Madhu Sudan

We show that random sparse binary linear codes are locally testable and locally decodable (under any linear encoding) with constant queries (with probability tending to one). By sparse, we mean that the code should have only polynomially many codewords. Our results are the first to show that local decodability and ... more >>>

Satyen Kale, C. Seshadhri

We consider the problem of testing graph expansion in the bounded degree model. We give a property tester that given a graph with degree bound $d$, an expansion bound $\alpha$, and a parameter $\epsilon > 0$, accepts the graph with high probability if its expansion is more than $\alpha$, and ... more >>>

Ilias Diakonikolas, Homin Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco Servedio, Andrew Wan

We describe a general method for testing whether a function on n input variables has a concise representation. The approach combines ideas from the junta test of Fischer et al. with ideas from learning theory, and yields property testers that make poly(s/epsilon) queries (independent of n) for Boolean function classes ... more >>>

Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco Servedio

This paper addresses the problem of testing whether a Boolean-valued function f is a halfspace, i.e. a function of the form f(x)=sgn(w ⋅ x - θ). We consider halfspaces over the continuous domain R^n (endowed with the standard multivariate Gaussian distribution) as well as halfspaces over the Boolean cube {-1,1}^n ... more >>>

Paul Valiant, Paul Valiant

We introduce the notion of a Canonical Tester for a class of properties, that is, a tester strong and

general enough that ``a property is testable if and only if the

Canonical Tester tests it''. We construct a Canonical Tester

for the class of symmetric properties of one or two

more >>>

Arnab Bhattacharyya

Given a boolean function, let epsilon_M(f) denote the smallest distance between f and a monotone function on {0,1}^n. Let delta_M(f) denote the fraction of hypercube edges where f violates monotonicity. We give an alternative proof of the tight bound: delta_M(f) >= 2/n eps_M(f) for any boolean function f. This was ... more >>>

Elena Grigorescu, Tali Kaufman, Madhu Sudan

A basic goal in Property Testing is to identify a

minimal set of features that make a property testable.

For the case when the property to be tested is membership

in a binary linear error-correcting code, Alon et al.~\cite{AKKLR}

had conjectured that the presence of a {\em single} low weight

more >>>

Oded Goldreich, Dana Ron

In this paper we consider two refined questions regarding

the query complexity of testing graph properties

in the adjacency matrix model.

The first question refers to the relation between adaptive

and non-adaptive testers, whereas the second question refers to

testability within complexity that

is inversely proportional to ...
more >>>

Sourav Chakraborty, Laszlo Babai

For a permutation group $G$ acting on the set $\Omega$

we say that two strings $x,y\,:\,\Omega\to\boole$

are {\em $G$-isomorphic} if they are equivalent under

the action of $G$, \ie, if for some $\pi\in G$ we have

$x(i^{\pi})=y(i)$ for all $i\in\Omega$.

Cyclic Shift, Graph Isomorphism ...
more >>>

Oded Goldreich, Dana Ron

We initiate a systematic study of a special type of property testers.

These testers consist of repeating a basic test

for a number of times that depends on the proximity parameters,

whereas the basic test is oblivious of the proximity parameter.

We refer to such basic ...
more >>>

Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie

We consider the task of testing properties of Boolean functions that

are invariant under linear transformations of the Boolean cube. Previous

work in property testing, including the linearity test and the test

for Reed-Muller codes, has mostly focused on such tasks for linear

properties. The one exception is a test ...
more >>>

Oded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg

Referring to the query complexity of property testing,

we prove the existence of a rich hierarchy of corresponding

complexity classes. That is, for any relevant function $q$,

we prove the existence of properties that have testing

complexity Theta(q).

Such results are proven in three standard

domains often considered in property ...
more >>>

Victor Chen

A hypergraph dictatorship test is first introduced by Samorodnitsky

and Trevisan and serves as a key component in

their unique games based $\PCP$ construction. Such a test has oracle

access to a collection of functions and determines whether all the

functions are the same dictatorship, or all their low degree ...
more >>>

Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, David Zuckerman

We consider the problem of testing if a given function

$f : \F_2^n \rightarrow \F_2$ is close to any degree $d$ polynomial

in $n$ variables, also known as the Reed-Muller testing problem.

Alon et al.~\cite{AKKLR} proposed and analyzed a natural

$2^{d+1}$-query test for this property and showed that it accepts

more >>>

Swastik Kopparty, Shubhangi Saraf

In this paper, we give surprisingly efficient algorithms for list-decoding and testing

{\em random} linear codes. Our main result is that random sparse linear codes are locally testable and locally list-decodable

in the {\em high-error} regime with only a {\em constant} number of queries.

More precisely, we show that ...
more >>>

Eli Ben-Sasson, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan, Michael Viderman

Locally testable codes (LTCs) are error-correcting codes for which membership, in the code, of a given word can be tested by examining it in very few locations. Most known constructions of locally testable codes are linear codes, and give error-correcting codes

whose duals have (superlinearly) {\em many} small weight ...
more >>>

Boaz Barak, Moritz Hardt, Thomas Holenstein, David Steurer

We study the question of whether the value of mathematical programs such as

linear and semidefinite programming hierarchies on a graph $G$, is preserved

when taking a small random subgraph $G'$ of $G$. We show that the value of the

Goemans-Williamson (1995) semidefinite program (SDP) for \maxcut of $G'$ is

more >>>

Madhu Sudan

Property testing considers the task of testing rapidly (in particular, with very few samples into the data), if some massive data satisfies some given property, or is far from satisfying the property. For ``global properties'', i.e., properties that really depend somewhat on every piece of the data, one could ask ... more >>>

Oded Goldreich

The aim of this article is to introduce the reader to the study

of testing graph properties, while focusing on the main models

and issues involved. No attempt is made to provide a

comprehensive survey of this study, and specific results

are often mentioned merely as illustrations of general ...
more >>>

Sourav Chakraborty, David García Soriano, Arie Matsliah

In this paper we study the problem of testing structural equivalence (isomorphism) between a pair of Boolean

functions $f,g:\zo^n \to \zo$. Our main focus is on the most studied case, where one of the functions is given (explicitly), and the other function can be queried.

We prove that for every ... more >>>

Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie

The rich collection of successes in property testing raises a natural question: Why are so many different properties turning out to be locally testable? Are there some broad "features" of properties that make them testable? Kaufman and Sudan (STOC 2008) proposed the study of the relationship between the invariances satisfied ... more >>>

Arnab Bhattacharyya, Elena Grigorescu, Jakob Nordström, Ning Xie

Properties of Boolean functions on the hypercube that are invariant

with respect to linear transformations of the domain are among some of

the most well-studied properties in the context of property testing.

In this paper, we study a particular natural class of linear-invariant

properties, called matroid freeness properties. These properties ...
more >>>

Victor Chen, Madhu Sudan, Ning Xie

Given two testable properties $\mathcal{P}_{1}$ and $\mathcal{P}_{2}$, under what conditions are the union, intersection or set-difference

of these two properties also testable?

We initiate a systematic study of these basic set-theoretic operations in the context of property

testing. As an application, we give a conceptually different proof that linearity is ...
more >>>

Reut Levi, Dana Ron, Ronitt Rubinfeld

We propose a framework for studying property testing of collections of distributions,

where the number of distributions in the collection is a parameter of the problem.

Previous work on property testing of distributions considered

single distributions or pairs of distributions. We suggest two models that differ

in the way the ...
more >>>

Gregory Valiant, Paul Valiant

We prove two new multivariate central limit theorems; the first relates the sum of independent distributions to the multivariate Gaussian of corresponding mean and covariance, under the earthmover distance matric (also known as the Wasserstein metric). We leverage this central limit theorem to prove a stronger but more specific central ... more >>>

Gregory Valiant, Paul Valiant

We introduce a new approach to characterizing the unobserved portion of a distribution, which provides sublinear-sample additive estimators for a class of properties that includes entropy and distribution support size. Together with the lower bounds proven in the companion paper [29], this settles the longstanding question of the sample complexities ... more >>>

Madhu Sudan

The last two decades have seen enormous progress in the development of sublinear-time algorithms --- i.e., algorithms that examine/reveal properties of ``data'' in less time than it would take to read all of the data. A large, and important, subclass of such properties turn out to be ``linear''. In particular, ... more >>>

Ronitt Rubinfeld, Asaf Shapira

Sublinear time algorithms represent a new paradigm

in computing, where an algorithm must give some sort

of an answer after inspecting only a very small portion

of the input. We discuss the types of answers that

one can hope to achieve in this setting.

Dana Ron, Gilad Tsur

Property testing is concerned with deciding whether an object

(e.g. a graph or a function) has a certain property or is ``far''

(for a prespecified distance measure) from every object with

that property. In this work we consider the property of being

computable by a read-once ...
more >>>

Madhav Jha, Sofya Raskhodnikova

A function $f : D \to R$ has Lipschitz constant $c$ if $d_R(f(x),f(y)) \leq c\cdot d_D(x,y)$ for all $x,y$ in $D$, where $d_R$ and $d_D$ denote the distance functions on the range and domain of $f$, respectively. We say a function is Lipschitz if it has Lipschitz constant 1. (Note ... more >>>

Elad Haramaty, Amir Shpilka, Madhu Sudan

We consider the problem of testing if a given function $f : \F_q^n \rightarrow \F_q$ is close to a $n$-variate degree $d$ polynomial over the finite field $\F_q$ of $q$ elements. The natural, low-query, test for this property would be to pick the smallest dimension $t = t_{q,d}\approx d/q$ such ... more >>>

Arnab Bhattacharyya, Elena Grigorescu, Prasad Raghavendra, Asaf Shapira

Call a function $f: \mathbb{F}_2^n \to \{0,1\}$ odd-cycle-free if there are no $x_1, \dots, x_k \in \mathbb{F}_2^n$ with $k$ an odd integer such that $f(x_1) = \cdots = f(x_k) = 1$ and $x_1 + \cdots + x_k = 0$. We show that one can distinguish odd-cycle-free functions from those $\epsilon$-far ... more >>>

Eli Ben-Sasson, Elena Grigorescu, Ghid Maatouk, Amir Shpilka, Madhu Sudan

Affine-invariant properties are an abstract class of properties that generalize some

central algebraic ones, such as linearity and low-degree-ness, that have been

studied extensively in the context of property testing. Affine invariant properties

consider functions mapping a big field $\mathbb{F}_{q^n}$ to the subfield $\mathbb{F}_q$ and include all

properties that form ...
more >>>

Angsheng Li, Yicheng Pan, Pan Peng

In this paper, we study the problem of testing the conductance of a

given graph in the general graph model. Given distance parameter

$\varepsilon$ and any constant $\sigma>0$, there exists a tester

whose running time is $\mathcal{O}(\frac{m^{(1+\sigma)/2}\cdot\log

n\cdot\log\frac{1}{\varepsilon}}{\varepsilon\cdot\Phi^2})$, where

$n$ is the number of vertices and $m$ is the number ...
more >>>

C. Seshadhri, Deeparnab Chakrabarty

The problem of monotonicity testing of the boolean hypercube is a classic well-studied, yet unsolved

question in property testing. We are given query access to $f:\{0,1\}^n \mapsto R$

(for some ordered range $R$). The boolean hypercube ${\cal B}^n$ has a natural partial order, denoted by $\prec$ (defined by the product ...
more >>>

Tom Gur, Omer Tamuz

Let $f:\{-1,1\}^n \to \mathbb{R}$ be a real function on the hypercube, given

by its discrete Fourier expansion, or, equivalently, represented as

a multilinear polynomial. We say that it is Boolean if its image is

in $\{-1,1\}$.

We show that every function on the hypercube with a ... more >>>

Madhu Sudan, Noga Ron-Zewi

Over a finite field $\F_q$ the $(n,d,q)$-Reed-Muller code is the code given by evaluations of $n$-variate polynomials of total degree at most $d$ on all points (of $\F_q^n$). The task of testing if a function $f:\F_q^n \to \F_q$ is close to a codeword of an $(n,d,q)$-Reed-Muller code has been of ... more >>>

Alan Guo, Madhu Sudan

We prove that the class of locally testable affine-invariant properties is closed under sums, intersections and "lifts". The sum and intersection are two natural operations on linear spaces of functions, where the sum of two properties is simply their sum as a vector space. The "lift" is a less natural ... more >>>

Arnab Bhattacharyya, Yuichi Yoshida

Given an instance $\mathcal{I}$ of a CSP, a tester for $\mathcal{I}$ distinguishes assignments satisfying $\mathcal{I}$ from those which are far from any assignment satisfying $\mathcal{I}$. The efficiency of a tester is measured by its query complexity, the number of variable assignments queried by the algorithm. In this paper, we characterize ... more >>>

C. Seshadhri, Deeparnab Chakrabarty

Given oracle access to a Boolean function $f:\{0,1\}^n \mapsto \{0,1\}$, we design a randomized tester that takes as input a parameter $\eps>0$, and outputs {\sf Yes} if the function is monotone, and outputs {\sf No} with probability $>2/3$, if the function is $\eps$-far from monotone. That is, $f$ needs to ... more >>>

Eric Blais, Sofya Raskhodnikova, Grigory Yaroslavtsev

We introduce strong, and in many cases optimal, lower bounds for the number of queries required to nonadaptively test three fundamental properties of functions $ f : [n]^d \rightarrow \mathbb R$ on the hypergrid: monotonicity, convexity, and the Lipschitz property.

Our lower bounds also apply to the more restricted setting ...
more >>>

Lior Gishboliner, Asaf Shapira

A graph property P is said to be testable if one can check if a graph is close or far from satisfying P using few random local inspections. Property P is said to be non-deterministically testable if one can supply a "certificate" to the fact that a graph satisfies P ... more >>>

Oded Goldreich

We consider three types of multiple input problems in the context of property testing.

Specifically, for a property $\Pi\subseteq\{0,1\}^n$, a proximity parameter $\epsilon$, and an integer $m$, we consider the following problems:

\begin{enumerate}

\item Direct $m$-Sum Problem for $\Pi$ and $\epsilon$:

Given a sequence of $m$ inputs, output a sequence ...
more >>>

Oded Goldreich

A couple of years ago, Blais, Brody, and Matulef put forward a methodology for proving lower bounds on the query complexity

of property testing via communication complexity. They provided a restricted formulation of their methodology

(via ``simple combining operators'')

and also hinted towards a more general formulation, which we spell ...
more >>>

Tom Gur, Ron Rothblum

We initiate a study of non-interactive proofs of proximity. These proof-systems consist of a verifier that wishes to ascertain the validity of a given statement, using a short (sublinear length) explicitly given proof, and a sublinear number of queries to its input. Since the verifier cannot even read the entire ... more >>>

Eldar Fischer, Yonatan Goldhirsh, Oded Lachish

For a property $P$ and a sub-property $P'$, we say that $P$ is $P'$-partially testable with $q$ queries if there exists an algorithm that distinguishes, with high probability, inputs in $P'$ from inputs $\epsilon$-far from $P$ by using $q$ queries. There are natural properties that require many queries to test, ... more >>>

Abhishek Bhrushundi

A bent function is a Boolean function all of whose Fourier coefficients are equal in absolute value. These functions have been extensively studied in cryptography and play an important role in cryptanalysis and design of cryptographic systems.

We study bent functions in the framework of property testing. In particular, we ...
more >>>

Dana Ron, Rocco Servedio

A signed majority function is a linear threshold function $f : \{+1,1\}^n \to \{+1,1\}$ of the form

$f(x)={\rm sign}(\sum_{i=1}^n \sigma_i x_i)$ where each $\sigma_i \in \{+1,-1\}.$ Signed majority functions are a highly symmetrical subclass of the class of all linear threshold functions, which are functions of the form ${\rm ...
more >>>

Oded Goldreich, Dana Ron

The standard definition of property testing endows the tester with the ability to make arbitrary queries to ``elements''

of the tested object.

In contrast, sample-based testers only obtain independently distributed elements (a.k.a. labeled samples) of the tested object.

While sample-based testers were defined by

Goldreich, Goldwasser, and Ron ({\em JACM}\/ ...
more >>>

Abhishek Bhrushundi, Sourav Chakraborty, Raghav Kulkarni

In this paper, we study linear and quadratic Boolean functions in the context of property testing. We do this by observing that the query complexity of testing properties of linear and quadratic functions can be characterized in terms of the complexity in another model of computation called parity decision trees. ... more >>>

Peyman Afshani, Kevin Matulef, Bryan Wilkinson

We define a new property testing model for algorithms that do not have arbitrary query access to the input, but must instead traverse it in a manner that respects the underlying data structure in which it is stored. In particular, we consider the case when the underlying data structure is ... more >>>

Clement Canonne, Ronitt Rubinfeld

In this paper, we analyze and study a hybrid model for testing and learning probability distributions. Here, in addition to samples, the testing algorithm is provided with one of two different types of oracles to the unknown distribution $D$ over $[n]$. More precisely, we define both the dual and extended ... more >>>

Oded Goldreich, Dana Ron

We initiate a study of learning and testing dynamic environments,

focusing on environment that evolve according to a fixed local rule.

The (proper) learning task consists of obtaining the initial configuration

of the environment, whereas for non-proper learning it suffices to predict

its future values. The testing task consists of ...
more >>>

Venkatesan Guruswami, Madhu Sudan, Ameya Velingker, Carol Wang

Locally testable codes (LTCs) of constant distance that allow the tester to make a linear number of queries have become the focus of attention recently, due to their elegant connections to hardness of approximation. In particular, the binary Reed-Muller code of block length $N$ and distance $d$ is known to ... more >>>

Roei Tell

We provide an alternative proof for a known result stating that $\Omega(k)$ queries are needed to test $k$-sparse linear Boolean functions. Similar to the approach of Blais and Kane (2012), we reduce the proof to the analysis of Hamming weights of vectors in affi ne subspaces of the Boolean hypercube. ... more >>>

Roei Tell

A few years ago, Blais, Brody, and Matulef (2012) presented a methodology for proving lower bounds for property testing problems by reducing them from problems in communication complexity. Recently, Bhrushundi, Chakraborty, and Kulkarni (2014) showed that some reductions of this type can be deconstructed to two separate reductions, from communication ... more >>>

Jayadev Acharya, Clement Canonne, Gautam Kamath

A recent model for property testing of probability distributions enables tremendous savings in the sample complexity of testing algorithms, by allowing them to condition the sampling on subsets of the domain.

In particular, Canonne et al. showed that, in this setting, testing identity of an unknown distribution $D$ (i.e., ...
more >>>

Subhash Khot, Dor Minzer, Muli Safra

We show a directed and robust analogue of a boolean isoperimetric type theorem of Talagrand. As an application, we

give a monotonicity testing algorithm that makes $\tilde{O}(\sqrt{n}/\epsilon^2)$ non-adaptive queries to a function

$f:\{0,1\}^n \mapsto \{0,1\}$, always accepts a monotone function and rejects a function that is $\epsilon$-far from

being monotone ...
more >>>

Oded Goldreich, Tom Gur, Ron Rothblum

Proofs of proximity are probabilistic proof systems in which the verifier only queries a sub-linear number of input bits, and soundness only means that, with high probability, the input is close to an accepting input. In their minimal form, called Merlin-Arthur proofs of proximity (MAP), the verifier receives, in addition ... more >>>

Clement Canonne

The field of property testing originated in work on program checking, and has evolved into an established and very active research area. In this work, we survey the developments of one of its most recent and prolific offspring, distribution testing. This subfield, at the junction of property testing and Statistics, ... more >>>

Roei Tell

For a set $\Pi$ in a metric space and $\delta>0$, denote by $\mathcal{F}_\delta(\Pi)$ the set of elements that are $\delta$-far from $\Pi$. In property testing, a $\delta$-tester for $\Pi$ is required to accept inputs from $\Pi$ and reject inputs from $\mathcal{F}_\delta(\Pi)$. A natural dual problem is the problem of $\delta$-testing ... more >>>

Arnab Bhattacharyya, Abhishek Bhowmick

Higher-order Fourier analysis, developed over prime fields, has been recently used in different areas of computer science, including list decoding, algorithmic decomposition and testing. We extend the tools of higher-order Fourier analysis to analyze functions over general fields. Using these new tools, we revisit the results in the above areas.

... more >>>Nathanaël François, Frederic Magniez, Olivier Serre, Michel de Rougemont

In the context of language recognition, we demonstrate the superiority of streaming property testers against streaming algorithms and property testers, when they are not combined. Initiated by Feigenbaum et al, a streaming property tester is a streaming algorithm recognizing a language under the property testing approximation: it must distinguish inputs ... more >>>

Tim Roughgarden

This document collects the lecture notes from my course ``Communication Complexity (for Algorithm Designers),'' taught at

Stanford in the winter quarter of 2015. The two primary goals of the course are:

1. Learn several canonical problems that have proved the most useful for proving lower bounds (Disjointness, Index, Gap-Hamming, etc.). ... more >>>

Guy Kindler

The first part of this thesis strengthens the low-error PCP

characterization of NP, coming closer to the upper limit of the

conjecture of~\cite{BGLR}.

In the second part we show that a boolean function over

$n$ variables can be tested for the property of depending ...
more >>>

Oded Goldreich

Inspired by Diakonikolas and Kane (2016), we reduce the class of problems consisting of testing whether an unknown distribution over $[n]$ equals a fixed distribution to this very problem when the fixed distribution is uniform over $[n]$. Our reduction preserves the parameters of the problem, which are $n$ and the ... more >>>

Roei Tell

A tolerant tester with one-sided error for a property is a tester that accepts every input that is close to the property, with probability 1, and rejects every input that is far from the property, with positive probability. In this note we show that such testers require a linear number ... more >>>

Ilias Diakonikolas, Daniel Kane

We study problems in distribution property testing:

Given sample access to one or more unknown discrete distributions,

we want to determine whether they have some global property or are $\epsilon$-far

from having the property in $\ell_1$ distance (equivalently, total variation distance, or ``statistical distance'').

In this work, we give a ...
more >>>

Eric Blais, Clement Canonne, Talya Eden, Amit Levi, Dana Ron

The function $f\colon \{-1,1\}^n \to \{-1,1\}$ is a $k$-junta if it depends on at most $k$ of its variables. We consider the problem of tolerant testing of $k$-juntas, where the testing algorithm must accept any function that is $\epsilon$-close to some $k$-junta and reject any function that is $\epsilon'$-far from ... more >>>

Karthekeyan Chandrasekaran, Mahdi Cheraghchi, Venkata Gandikota, Elena Grigorescu

Motivated by the structural analogies between point lattices and linear error-correcting codes, and by the mature theory on locally testable codes, we initiate a systematic study of local testing for membership in lattices. Testing membership in lattices is also motivated in practice, by applications to integer programming, error detection in ... more >>>

Subhash Khot, Igor Shinkar

We present an adaptive tester for the unateness property of Boolean functions. Given a function $f:\{0,1\}^n \to \{0,1\}$ the tester makes $O(n \log(n)/\epsilon)$ adaptive queries to the function. The tester always accepts a unate function, and rejects with probability at least 0.9 any function that is $\epsilon$-far from being unate.

more >>>

Clement Canonne, Elena Grigorescu, Siyao Guo, Akash Kumar, Karl Wimmer

A Boolean $k$-monotone function defined over a finite poset domain ${\cal D}$ alternates between the values $0$ and $1$ at most $k$ times on any ascending chain in ${\cal D}$. Therefore, $k$-monotone functions are natural generalizations of the classical monotone functions, which are the $1$-monotone functions.

Motivated by the ... more >>>

Eric Blais, Clement Canonne, Tom Gur

We present a new methodology for proving distribution testing lower bounds, establishing a connection between distribution testing and the simultaneous message passing (SMP) communication model. Extending the framework of Blais, Brody, and Matulef [BBM12], we show a simple way to reduce (private-coin) SMP problems to distribution testing problems. This method ... more >>>

Eric Blais, Yuichi Yoshida

We characterize the set of properties of Boolean-valued functions on a finite domain $\mathcal{X}$ that are testable with a constant number of samples.

Specifically, we show that a property $\mathcal{P}$ is testable with a constant number of samples if and only if it is (essentially) a $k$-part symmetric property ...
more >>>

Constantinos Daskalakis, Nishanth Dikkala, Gautam Kamath

Given samples from an unknown multivariate distribution $p$, is it possible to distinguish whether $p$ is the product of its marginals versus $p$ being far from every product distribution? Similarly, is it possible to distinguish whether $p$ equals a given distribution $q$ versus $p$ and $q$ being far from each ... more >>>

Clement Canonne, Tom Gur

Adaptivity is known to play a crucial role in property testing. In particular, there exist properties for which there is an exponential gap between the power of \emph{adaptive} testing algorithms, wherein each query may be determined by the answers received to prior queries, and their \emph{non-adaptive} counterparts, in which all ... more >>>

Noga Alon, Omri Ben-Eliezer, Eldar Fischer

We consider properties of edge-colored vertex-ordered graphs, i.e., graphs with a totally ordered vertex set and a finite set of possible edge colors. We show that any hereditary property of such graphs is strongly testable, i.e., testable with a constant number of queries.

We also explain how the proof can ...
more >>>

Clement Canonne, Ilias Diakonikolas, Alistair Stewart

We study the general problem of testing whether an unknown discrete distribution belongs to a given family of distributions. More specifically, given a class of distributions $\mathcal{P}$ and sample access to an unknown distribution $\mathbf{P}$, we want to distinguish (with high probability) between the case that $\mathbf{P} \in \mathcal{P}$ and ... more >>>

Irit Dinur, Inbal Livni Navon

Given a function $f:[N]^k\rightarrow[M]^k$, the Z-test is a three query test for checking if a function $f$ is a direct product, namely if there are functions $g_1,\dots g_k:[N]\to[M]$ such that $f(x_1,\ldots,x_k)=(g_1(x_1),\dots g_k(x_k))$ for every input $x\in [N]^k$.

This test was introduced by Impagliazzo et. al. (SICOMP 2012), who ...
more >>>

Joshua Brakensiek, Venkatesan Guruswami

We give a family of dictatorship tests with perfect completeness and low-soundness for 2-to-2 constraints. The associated 2-to-2 conjecture has been the basis of some previous inapproximability results with perfect completeness. However, evidence towards the conjecture in the form of integrality gaps even against weak semidefinite programs has been elusive. ... more >>>

Alessandro Chiesa, Tom Gur

Distribution testing is an area of property testing that studies algorithms that receive few samples from a probability distribution D and decide whether D has a certain property or is far (in total variation distance) from all distributions with that property. Most natural properties of distributions, however, require a large ... more >>>

Hadley Black, Deeparnab Chakrabarty, C. Seshadhri

We study monotonicity testing of Boolean functions over the hypergrid $[n]^d$ and design a non-adaptive tester with $1$-sided error whose query complexity is $\tilde{O}(d^{5/6})\cdot \text{poly}(\log n,1/\epsilon)$. Previous to our work, the best known testers had query complexity linear in $d$ but independent of $n$. We improve upon these testers as ... more >>>

Irit Dinur, Yuval Filmus, Prahladh Harsha

Agreement tests are a generalization of low degree tests that capture a local-to-global phenomenon, which forms the combinatorial backbone of most PCP constructions. In an agreement test, a function is given by an ensemble of local restrictions. The agreement test checks that the restrictions agree when they overlap, and the ... more >>>

Constantinos Daskalakis, Gautam Kamath, John Wright

Given samples from an unknown distribution $p$ and a description of a distribution $q$, are $p$ and $q$ close or far? This question of "identity testing" has received significant attention in the case of testing whether $p$ and $q$ are equal or far in total variation distance. However, in recent ... more >>>

Omri Ben-Eliezer, Eldar Fischer

One of the main challenges in property testing is to characterize those properties that are testable with a constant number of queries. For unordered structures such as graphs and hypergraphs this task has been mostly settled. However, for ordered structures such as strings, images, and ordered graphs, the characterization problem ... more >>>

Oded Goldreich, Dana Ron

We initiate a study of testing properties of graphs that are presented as subgraphs of a fixed (or an explicitly given) graph.

The tester is given free access to a base graph $G=([\n],E)$, and oracle access to a function $f:E\to\{0,1\}$ that represents a subgraph of $G$.

The tester is ...
more >>>

Irit Dinur, Oded Goldreich, Tom Gur

We show that every set in $\cal P$ is strongly testable under a suitable encoding. By ``strongly testable'' we mean having a (proximity oblivious) tester that makes a constant number of queries and rejects with probability that is proportional to the distance of the tested object from the property. By ... more >>>

Alessandro Chiesa, Peter Manohar, Igor Shinkar

Non-signaling strategies are collections of distributions with certain non-local correlations. They have been studied in Physics as a strict generalization of quantum strategies to understand the power and limitations of Nature's apparent non-locality. Recently, they have received attention in Theoretical Computer Science due to connections to Complexity and Cryptography.

We ... more >>>

Jayadev Acharya, Clement Canonne, Himanshu Tyagi

Independent samples from an unknown probability distribution $\mathbf{p}$ on a domain of size $k$ are distributed across $n$ players, with each player holding one sample. Each player can communicate $\ell$ bits to a central referee in a simultaneous message passing (SMP) model of communication to help the referee infer a ... more >>>

Tom Gur, Ron D. Rothblum, Yang P. Liu

Non-interactive proofs of proximity allow a sublinear-time verifier to check that

a given input is close to the language, given access to a short proof. Two natural

variants of such proof systems are MA-proofs of Proximity (MAP), in which the proof

is a function of the input only, and AM-proofs ...
more >>>

Amit Levi, Erik Waingarten

We introduce a new model for testing graph properties which we call the \emph{rejection sampling model}. We show that testing bipartiteness of $n$-nodes graphs using rejection sampling queries requires complexity $\widetilde{\Omega}(n^2)$. Via reductions from the rejection sampling model, we give three new lower bounds for tolerant testing of Boolean functions ... more >>>

Oded Goldreich

Focusing on property testing tasks that have query complexity that is independent of the size of the tested object (i.e., depends on the proximity parameter only), we prove the existence of a rich hierarchy of the corresponding complexity classes.

That is, for essentially any function $q:(0,1]\to\N$, we prove the existence ...
more >>>

Akash Kumar, C. Seshadhri, Andrew Stolman

Let $G$ be an undirected, bounded degree graph with $n$ vertices. Fix a finite graph $H$, and suppose one must remove $\varepsilon n$ edges from $G$ to make it $H$-minor free (for some small constant $\varepsilon > 0$).

We give an $n^{1/2+o(1)}$-time randomized procedure that, with high probability, finds an ...
more >>>

Oded Goldreich

The standard models of testing graph properties postulate that the vertex-set consists of $\{1,2,...,n\}$, where $n$ is a natural number that is given explicitly to the tester.

Here we suggest more flexible models by postulating that the tester is given access to samples the arbitrary vertex-set; that is, the vertex-set ...
more >>>

Gautam Kamath, Christos Tzamos

We investigate distribution testing with access to non-adaptive conditional samples.

In the conditional sampling model, the algorithm is given the following access to a distribution: it submits a query set $S$ to an oracle, which returns a sample from the distribution conditioned on being from $S$.

In the non-adaptive setting, ...
more >>>

Akash Kumar, C. Seshadhri, Andrew Stolman

with $n$ vertices. Fix a finite graph $H$, and suppose one must remove $\varepsilon n$ edges from $G$ to make it $H$-minor free (for some small constant $\varepsilon > 0$). We give an $n^{1/2+o(1)}$-time randomized procedure that, with high probability, finds an ...
more >>>

Oded Goldreich

Prior studies of testing graph properties presume that the tester can obtain uniformly distributed vertices in the tested graph (in addition to obtaining answers to the some type of graph-queries).

Here we envision settings in which it is only feasible to obtain random vertices drawn according to an arbitrary distribution ...
more >>>

Hadley Black, Deeparnab Chakrabarty, C. Seshadhri

Testing monotonicity of Boolean functions over the hypergrid, $f:[n]^d \to \{0,1\}$, is a classic problem in property testing. When the range is real-valued, there are $\Theta(d\log n)$-query testers and this is tight. In contrast, the Boolean range qualitatively differs in two ways:

(1) Independence of $n$: There are testers ...
more >>>

Sofya Raskhodnikova, Noga Ron-Zewi, Nithin Varma

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

Omri Ben-Eliezer

We study testing of local properties in one-dimensional and multi-dimensional arrays. A property of $d$-dimensional arrays $f:[n]^d \to \Sigma$ is $k$-local if it can be defined by a family of $k \times \ldots \times k$ forbidden consecutive patterns. This definition captures numerous interesting properties. For example, monotonicity, Lipschitz continuity and ... more >>>

Akash Kumar, C. Seshadhri, Andrew Stolman

Let $G$ be a graph with $n$ vertices and maximum degree $d$. Fix some minor-closed property $\mathcal{P}$ (such as planarity).

We say that $G$ is $\varepsilon$-far from $\mathcal{P}$ if one has to remove $\varepsilon dn$ edges to make it have $\mathcal{P}$.

The problem of property testing $\mathcal{P}$ was introduced in ...
more >>>

Jayadev Acharya, Clement Canonne, Yanjun Han, Ziteng Sun, Himanshu Tyagi

We study goodness-of-fit of discrete distributions in the distributed setting, where samples are divided between multiple users who can only release a limited amount of information about their samples due to various information constraints. Recently, a subset of the authors showed that having access to a common random seed (i.e., ... more >>>

Oded Goldreich

We consider two versions of the problem of testing graph isomorphism in the bounded-degree graph model: A version in which one graph is fixed, and a version in which the input consists of two graphs.

We essentially determine the query complexity of these testing problems in the special case of ...
more >>>

Roy Gotlib, Tali Kaufman

In this work, using methods from high dimensional expansion, we show that the property of $k$-direct-sum is testable for odd values of $k$ . Previous work of Kaufman and Lubotzky could inherently deal only with the case that $k$ is even, using a reduction to linearity testing.

Interestingly, our work ...
more >>>

Clement Canonne, Xi Chen, Gautam Kamath, Amit Levi, Erik Waingarten

We give a nearly-optimal algorithm for testing uniformity of distributions supported on $\{-1,1\}^n$, which makes $\tilde O (\sqrt{n}/\varepsilon^2)$ queries to a subcube conditional sampling oracle (Bhattacharyya and Chakraborty (2018)). The key technical component is a natural notion of random restriction for distributions on $\{-1,1\}^n$, and a quantitative analysis of how ... more >>>

Shafi Goldwasser, Guy Rothblum, Jonathan Shafer, Amir Yehudayoff

We consider the following question: using a source of labeled data and interaction with an untrusted prover, what is the complexity of verifying that a given hypothesis is "approximately correct"? We study interactive proof systems for PAC verification, where a verifier that interacts with a prover is required to accept ... more >>>

Clement Canonne, Karl Wimmer

Motivated by the question of data quantization and "binning," we revisit the problem of identity testing of discrete probability distributions. Identity testing (a.k.a. one-sample testing), a fundamental and by now well-understood problem in distribution testing, asks, given a reference distribution (model) $\mathbf{q}$ and samples from an unknown distribution $\mathbf{p}$, both ... more >>>

Oded Goldreich, Dana Ron

We consider the query complexity of three versions of the problem of testing monomials and affine (and linear) subspaces with one-sided error, and obtain the following results:

\begin{itemize}

\item The general problem, in which the arity of the monomial (resp., co-dimension of the subspace) is not specified, has ...
more >>>

Oded Goldreich

We show that testing Hamiltonicity in the bounded-degree graph model requires a linear number of queries. This refers to both the path and the cycle versions of the problem, and similar results hold also for the directed analogues.

In addition, we present an alternative proof for the known fact that ...
more >>>

Oded Goldreich, Avi Wigderson

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

Marcel Dall'Agnol, Tom Gur, Oded Lachish

We prove a general structural theorem for a wide family of local algorithms, which includes property testers, local decoders, and PCPs of proximity. Namely, we show that the structure of every algorithm that makes $q$ adaptive queries and satisfies a natural robustness condition admits a sample-based algorithm with $n^{1- 1/O(q^2 ... more >>>

Oded Goldreich, Avi Wigderson

We study the relation between the query complexity of adaptive and non-adaptive testers in the dense graph model.

It has been known for a couple of decades that the query complexity of non-adaptive testers is at most quadratic in the query complexity of adaptive testers.

We show that ...
more >>>

Andrej Bogdanov, Gautam Prakriya

A function $f(x_1, \dots, x_n)$ from a product domain $\mathcal{D}_1 \times \cdots \times \mathcal{D}_n$ to an abelian group $\mathcal{G}$ is a direct sum if it is of the form $f_1(x_1) + \cdots + f_n(x_n)$. We present a new 4-query direct sum test with optimal (up to constant factors) soundness error. ... more >>>

Hadley Black, Iden Kalemaj, Sofya Raskhodnikova

We generalize the celebrated isoperimetric inequality of Khot, Minzer, and Safra (SICOMP 2018) for Boolean functions to the case of real-valued functions $f \colon \{0,1\}^d\to\mathbb{R}$. Our main tool in the proof of the generalized inequality is a new Boolean decomposition that represents every real-valued function $f$ over an arbitrary partially ... more >>>

Vishnu Iyer, Avishay Tal, Michael Whitmeyer

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

Oded Goldreich

We study two notions that refers to asymmetric graphs, which we view as graphs having a unique ordering that can be reconstructed by looking at an unlabeled version of the graph.

A {\em local self-ordering} procedure for a graph $G$ is given oracle access to an arbitrary isomorphic copy of ... more >>>

Marcel Dall'Agnol, Tom Gur, Subhayan Roy Moulik, Justin Thaler

We initiate the systematic study of QMA algorithms in the setting of property testing, to which we refer as QMA proofs of proximity (QMAPs). These are quantum query algorithms that receive explicit access to a sublinear-size untrusted proof and are required to accept inputs having a property $\Pi$ and reject ... more >>>

Oded Goldreich

We briefly discuss a few open problems in the study of various models of testing graph properties, focusing on the query complexity of the various tasks. In the dense graph model, we discuss several open problems, including:

* Determining the complexity of testing triangle-freeness.

* Characterizing the class of properties ...
more >>>

Oded Goldreich, Dana Ron

A distribution is called $m$-grained if each element appears with probability that is an integer multiple of $1/m$.

We prove that, for any constant $c<1$, testing whether a distribution over $[\Theta(m)]$ is $m$-grained requires $\Omega(m^c)$ samples.

Oded Goldreich, Dana Ron

We initiate a study of a new model of property testing that is a hybrid of testing properties of distributions and testing properties of strings.

Specifically, the new model refers to testing properties of distributions, but these are distributions over huge objects (i.e., very long strings).

Accordingly, the ...
more >>>