Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > PROPERTY TESTING:
Reports tagged with Property Testing:
TR99-017 | 4th June 1999
Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, Alex Samorodnitsky

#### Improved Testing Algorithms for Monotonicity.

Revisions: 1

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

TR00-020 | 27th March 2000
Oded Goldreich, Dana Ron

#### On Testing Expansion in Bounded-Degree Graphs

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

TR00-083 | 18th September 2000
Eldar Fischer

#### Testing graphs for colorability properties

Revisions: 1

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

TR01-008 | 6th November 2000
Eldar Fischer

#### On the strength of comparisons in property testing

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

TR01-010 | 25th January 2001
Oded Goldreich, Luca Trevisan

#### Three Theorems regarding Testing Graph Properties.

Revisions: 1

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

TR01-051 | 4th May 2001
Sophie Laplante, Richard Lassaigne, Frederic Magniez, Sylvain Peyronnet, Michel de Rougemont

#### Probabilistic abstraction for model checking: An approach based on property testing

Revisions: 1

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

TR01-063 | 5th August 2001
Michal Parnas, Dana Ron, Alex Samorodnitsky

#### Proclaiming Dictators and Juntas or Testing Boolean Formulae

Revisions: 1

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

TR02-064 | 14th November 2002
Andrej Bogdanov, Luca Trevisan

#### Lower Bounds for Testing Bipartiteness in Dense Graphs

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

TR03-006 | 23rd January 2003

#### 3CNF Properties are Hard to Test

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

TR03-076 | 8th September 2003
Michael Langberg

#### Testing the independence number of hypergraphs

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

TR04-010 | 26th January 2004
Michal Parnas, Dana Ron, Ronitt Rubinfeld

#### Tolerant Property Testing and Distance Approximation

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

TR04-052 | 14th June 2004
Michael Ben Or, Don Coppersmith, Michael Luby, Ronitt Rubinfeld

#### Non-Abelian Homomorphism Testing, and Distributions Close to their Self-Convolutions

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

TR04-068 | 13th August 2004
Nir Ailon, Bernard Chazelle

#### Information Theory in Property Testing and Monotonicity Testing in Higher Dimension

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

TR04-096 | 4th November 2004
Eldar Fischer, Frederic Magniez, Michel de Rougemont

#### Property and Equivalence Testing on Strings

Revisions: 1

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

TR05-014 | 30th January 2005
Oded Goldreich

#### Short Locally Testable Codes and Proofs (Survey)

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

TR05-018 | 6th February 2005
Oded Goldreich

#### On Promise Problems (a survey in memory of Shimon Even [1935-2004])

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

TR05-019 | 9th February 2005
Venkatesan Guruswami, Atri Rudra

#### Tolerant Locally Testable Codes

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

TR05-085 | 5th August 2005
Asaf Shapira, Noga Alon

#### Homomorphisms in Graph Property Testing - A Survey

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

TR06-053 | 6th April 2006
Eldar Fischer, Orly Yahalom

#### Testing Convexity Properties of Tree Colorings

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

TR07-015 | 1st March 2007
Oded Goldreich, Or Sheffet

#### On the randomness complexity of property testing

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

TR07-057 | 11th July 2007
Oded Goldreich

#### On the Average-Case Complexity of Property Testing

Revisions: 1

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

TR07-060 | 11th July 2007
Tali Kaufman, Madhu Sudan

#### Sparse Random Linear Codes are Locally Decodable and Testable

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

TR07-076 | 25th July 2007
Satyen Kale, C. Seshadhri

#### Testing Expansion in Bounded Degree Graphs

Revisions: 1

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

TR07-077 | 7th August 2007
Ilias Diakonikolas, Homin Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco Servedio, Andrew Wan

#### Testing for Concise Representations

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

TR07-128 | 10th November 2007
Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco Servedio

#### Testing Halfspaces

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 &#8901; x - &#952;). 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 >>>

TR07-135 | 26th December 2007
Paul Valiant, Paul Valiant

#### Testing Symmetric Properties of Distributions

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

TR08-012 | 20th November 2007
Arnab Bhattacharyya

#### A Note on the Distance to Monotonicity of Boolean Functions

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

TR08-033 | 21st March 2008
Elena Grigorescu, Tali Kaufman, Madhu Sudan

#### 2-Transitivity is Insufficient for Local Testability

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

TR08-039 | 7th April 2008
Oded Goldreich, Dana Ron

#### Algorithmic Aspects of Property Testing in the Dense Graphs Model

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

TR08-040 | 3rd April 2008
Sourav Chakraborty, Laszlo Babai

#### Property Testing of Equivalence under a Permutation Group Action

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

TR08-041 | 10th April 2008
Oded Goldreich, Dana Ron

#### On Proximity Oblivious Testing

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

TR08-088 | 13th September 2008
Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie

#### Testing Linear-Invariant Non-Linear Properties

Revisions: 1

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

TR08-097 | 14th November 2008
Oded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg

#### Hierarchy Theorems for Property Testing

Revisions: 1

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

TR08-098 | 12th November 2008
Victor Chen

#### A Hypergraph Dictatorship Test with Perfect Completeness

Revisions: 1

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

TR09-086 | 2nd October 2009
Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, David Zuckerman

#### Optimal testing of Reed-Muller codes

Revisions: 1

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

TR09-115 | 13th November 2009
Swastik Kopparty, Shubhangi Saraf

#### Local list-decoding and testing of random linear codes from high-error

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

TR09-126 | 26th November 2009
Eli Ben-Sasson, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan, Michael Viderman

#### Locally Testable Codes Require Redundant Testers

Revisions: 3

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

TR09-129 | 30th November 2009
Boaz Barak, Moritz Hardt, Thomas Holenstein, David Steurer

#### Subsampling Semidefinite Programs and Max-Cut on the Sphere

Revisions: 1

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

TR10-051 | 26th March 2010

#### Invariance in Property Testing

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

TR10-082 | 11th May 2010
Oded Goldreich

#### Introduction to Testing Graph Properties

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

TR10-093 | 3rd June 2010
Sourav Chakraborty, David García Soriano, Arie Matsliah

#### Nearly Tight Bounds for Testing Function Isomorphism

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

TR10-116 | 21st July 2010
Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie

#### Testing linear-invariant non-linear properties: A short report

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

TR10-136 | 26th August 2010
Arnab Bhattacharyya, Elena Grigorescu, Jakob Nordström, Ning Xie

#### Separations of Matroid Freeness Properties

Revisions: 1

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

TR10-156 | 24th October 2010
Victor Chen, Madhu Sudan, Ning Xie

#### Property Testing via Set-Theoretic Operations

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

TR10-157 | 24th October 2010
Reut Levi, Dana Ron, Ronitt Rubinfeld

#### Testing Properties of Collections of Distributions

Revisions: 1

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

TR10-179 | 18th November 2010
Gregory Valiant, Paul Valiant

#### A CLT and tight lower bounds for estimating entropy

Revisions: 1

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

TR10-180 | 18th November 2010
Gregory Valiant, Paul Valiant

#### Estimating the unseen: A sublinear-sample canonical estimator of distributions

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

TR11-005 | 20th January 2011

#### Testing Linear Properties: Some general themes

Revisions: 1

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

TR11-013 | 3rd February 2011
Ronitt Rubinfeld, Asaf Shapira

#### Sublinear Time Algorithms

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.

more >>>

TR11-041 | 24th March 2011
Dana Ron, Gilad Tsur

#### Testing Computability by Width-Two OBDDs

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

TR11-057 | 15th April 2011

#### Testing and Reconstruction of Lipschitz Functions with Applications to Data Privacy

Revisions: 2

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

TR11-059 | 15th April 2011

#### Optimal testing of multivariate polynomials over small prime fields

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

TR11-075 | 6th May 2011
Arnab Bhattacharyya, Elena Grigorescu, Prasad Raghavendra, Asaf Shapira

#### Testing Odd-Cycle-Freeness in Boolean Functions

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

TR11-079 | 9th May 2011
Eli Ben-Sasson, Elena Grigorescu, Ghid Maatouk, Amir Shpilka, Madhu Sudan

#### On Sums of Locally Testable Affine Invariant Properties

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

TR11-101 | 26th July 2011
Angsheng Li, Yicheng Pan, Pan Peng

#### Testing Conductance in General Graphs

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

TR12-030 | 4th April 2012
C. Seshadhri, Deeparnab Chakrabarty

#### Optimal bounds for monotonicity and Lipschitz testing over the hypercube

Revisions: 2

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

TR12-031 | 4th April 2012
Tom Gur, Omer Tamuz

#### Testing Booleanity and the Uncertainty Principle

Revisions: 1

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

TR12-046 | 24th April 2012
Madhu Sudan, Noga Ron-Zewi

#### A new upper bound on the query complexity for testing generalized Reed-Muller codes

Revisions: 1

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

TR12-048 | 25th April 2012
Alan Guo, Madhu Sudan

#### Some closure features of locally testable affine-invariant properties

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

TR12-103 | 16th August 2012
Arnab Bhattacharyya, Yuichi Yoshida

#### Testing Assignments of Boolean CSPs

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

TR13-029 | 19th February 2013
C. Seshadhri, Deeparnab Chakrabarty

#### A {\huge ${o(n)}$} monotonicity tester for Boolean functions over the hypercube

Revisions: 1

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

TR13-036 | 13th March 2013
Eric Blais, Sofya Raskhodnikova, Grigory Yaroslavtsev

#### Lower Bounds for Testing Properties of Functions on Hypergrid Domains

Revisions: 1

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

TR13-059 | 9th April 2013
Lior Gishboliner, Asaf Shapira

#### Deterministic vs Non-deterministic Graph Property Testing

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

TR13-067 | 2nd May 2013
Oded Goldreich

#### On Multiple Input Problems in Property Testing

Revisions: 1

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

TR13-073 | 14th May 2013
Oded Goldreich

#### On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing

Revisions: 2

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

TR13-078 | 28th May 2013
Tom Gur, Ron Rothblum

#### Non-Interactive Proofs of Proximity

Revisions: 1

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

TR13-082 | 6th June 2013
Eldar Fischer, Yonatan Goldhirsh, Oded Lachish

#### Some properties are not even partially testable

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

TR13-089 | 17th June 2013
Abhishek Bhrushundi

#### On testing bent functions

Revisions: 1

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

TR13-096 | 25th June 2013
Dana Ron, Rocco Servedio

#### Exponentially improved algorithms and lower bounds for testing signed majorities

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 >>> TR13-109 | 11th August 2013 Oded Goldreich, Dana Ron #### On Sample-Based Testers Revisions: 1 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 >>> TR13-142 | 11th October 2013 Abhishek Bhrushundi, Sourav Chakraborty, Raghav Kulkarni #### Property Testing Bounds for Linear and Quadratic Functions via Parity Decision Trees Revisions: 2 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 >>> TR13-187 | 27th December 2013 Peyman Afshani, Kevin Matulef, Bryan Wilkinson #### Property Testing on Linked Lists Revisions: 1 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 >>> TR14-021 | 18th February 2014 Clement Canonne, Ronitt Rubinfeld #### Testing probability distributions underlying aggregated data 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 >>> TR14-029 | 4th March 2014 Oded Goldreich, Dana Ron #### On Learning and Testing Dynamic Environments Revisions: 3 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 >>> TR14-067 | 4th May 2014 Venkatesan Guruswami, Madhu Sudan, Ameya Velingker, Carol Wang #### Limitations on Testable Affine-Invariant Codes in the High-Rate Regime 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 >>> TR14-114 | 27th August 2014 Roei Tell #### An Alternative Proof of an$\Omega(k)$Lower Bound for Testing$k$-linear Boolean Functions 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 >>> TR14-115 | 27th August 2014 Roei Tell #### Deconstructions of Reductions from Communication Complexity to Property Testing using Generalized Parity Decision Trees Revisions: 1 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 >>> TR14-156 | 26th November 2014 Jayadev Acharya, Clement Canonne, Gautam Kamath #### A Chasm Between Identity and Equivalence Testing with Conditional Queries Revisions: 2 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 >>> TR15-011 | 22nd January 2015 Subhash Khot, Dor Minzer, Muli Safra #### On Monotonicity Testing and Boolean Isoperimetric type Theorems 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 >>> TR15-024 | 16th February 2015 Oded Goldreich, Tom Gur, Ron Rothblum #### Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs 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 >>> TR15-063 | 15th April 2015 Clement Canonne #### A Survey on Distribution Testing: Your Data is Big. But is it Blue? Revisions: 1 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 >>> TR15-072 | 23rd April 2015 Roei Tell #### On Being Far from Far and on Dual Problems in Property Testing Revisions: 4 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 >>> TR15-077 | 4th May 2015 Arnab Bhattacharyya, Abhishek Bhowmick #### Using higher-order Fourier analysis over general fields 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 >>> TR15-104 | 13th May 2015 Nathanaël François, Frederic Magniez, Olivier Serre, Michel de Rougemont #### Streaming Property Testing of Visibly Pushdown Languages Revisions: 2 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 >>> TR15-156 | 21st September 2015 Tim Roughgarden #### Communication Complexity (for Algorithm Designers) 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 >>> TR16-007 | 23rd January 2016 Guy Kindler #### Property Testing, PCP, andJuntas Revisions: 1 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 >>> TR16-015 | 4th February 2016 Oded Goldreich #### The uniform distribution is complete with respect to testing identity to a fixed distribution Revisions: 3 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 >>> TR16-032 | 10th March 2016 Roei Tell #### A Note on Tolerant Testing with One-Sided Error 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 >>> TR16-074 | 9th May 2016 Ilias Diakonikolas, Daniel Kane #### A New Approach for Testing Properties of Discrete Distributions 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 >>> TR16-105 | 13th July 2016 Eric Blais, Clement Canonne, Talya Eden, Amit Levi, Dana Ron #### Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism Revisions: 1 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 >>> TR16-125 | 31st July 2016 Karthekeyan Chandrasekaran, Mahdi Cheraghchi, Venkata Gandikota, Elena Grigorescu #### Local Testing for Membership in Lattices 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 >>> TR16-126 | 8th August 2016 Subhash Khot, Igor Shinkar #### An$\widetilde{O}(n)$Queries Adaptive Tester for Unateness 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 >>> TR16-136 | 31st August 2016 Clement Canonne, Elena Grigorescu, Siyao Guo, Akash Kumar, Karl Wimmer #### Testing k-Monotonicity Revisions: 1 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 >>> TR16-168 | 2nd November 2016 Eric Blais, Clement Canonne, Tom Gur #### Alice and Bob Show Distribution Testing Lower Bounds (They don't talk to each other anymore.) Revisions: 1 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 >>> TR16-201 | 19th December 2016 Eric Blais, Yuichi Yoshida #### A Characterization of Constant-Sample Testable Properties 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 >>> TR17-006 | 15th December 2016 Constantinos Daskalakis, Nishanth Dikkala, Gautam Kamath #### Testing Ising Models Revisions: 2 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 >>> TR17-029 | 18th February 2017 Clement Canonne, Tom Gur #### An Adaptivity Hierarchy Theorem for Property Testing Revisions: 1 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 >>> TR17-058 | 7th April 2017 Noga Alon, Omri Ben-Eliezer, Eldar Fischer #### Testing hereditary properties of ordered graphs and matrices Revisions: 1 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 >>> TR17-075 | 29th April 2017 Clement Canonne, Ilias Diakonikolas, Alistair Stewart #### Fourier-Based Testing for Families of Distributions Revisions: 1 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 >>> TR17-096 | 30th May 2017 Irit Dinur, Inbal Livni Navon #### Exponentially Small Soundness for the Direct Product Z-test 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 >>> TR17-141 | 19th September 2017 Joshua Brakensiek, Venkatesan Guruswami #### A Family of Dictatorship Tests with Perfect Completeness for 2-to-2 Label Cover 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 >>> TR17-155 | 13th October 2017 Alessandro Chiesa, Tom Gur #### Proofs of Proximity for Distribution Testing Revisions: 1 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 >>> TR17-159 | 28th October 2017 Hadley Black, Deeparnab Chakrabarty, C. Seshadhri #### A$o(d) \cdot \text{polylog}~n$Monotonicity Tester for Boolean Functions over the Hypergrid$[n]^d$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 >>> TR17-181 | 26th November 2017 Irit Dinur, Yuval Filmus, Prahladh Harsha #### Agreement tests on graphs and hypergraphs Revisions: 1 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 >>> TR18-002 | 31st December 2017 Constantinos Daskalakis, Gautam Kamath, John Wright #### Which Distribution Distances are Sublinearly Testable? 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 >>> TR18-021 | 30th January 2018 Omri Ben-Eliezer, Eldar Fischer #### Earthmover Resilience and Testing in Ordered Structures 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 >>> TR18-045 | 6th March 2018 Oded Goldreich, Dana Ron #### The Subgraph Testing Model Revisions: 2 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 >>> TR18-050 | 15th March 2018 Irit Dinur, Oded Goldreich, Tom Gur #### Every set in P is strongly testable under a suitable encoding 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 >>> TR18-067 | 9th April 2018 Alessandro Chiesa, Peter Manohar, Igor Shinkar #### Testing Linearity against Non-Signaling Strategies Revisions: 1 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 >>> TR18-079 | 19th April 2018 Jayadev Acharya, Clement Canonne, Himanshu Tyagi #### Distributed Simulation and Distributed Inference Revisions: 1 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 >>> TR18-083 | 25th April 2018 Tom Gur, Ron D. Rothblum, Yang P. Liu #### An Exponential Separation Between MA and AM Proofs of Proximity Revisions: 2 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 >>> TR18-094 | 2nd May 2018 Amit Levi, Erik Waingarten #### Lower Bounds for Tolerant Junta and Unateness Testing via Rejection Sampling of Graphs 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 >>> TR18-098 | 17th May 2018 Oded Goldreich #### Hierarchy Theorems for Testing Properties in Size-Oblivious Query Complexity Revisions: 1 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 >>> TR18-101 | 20th May 2018 Akash Kumar, C. Seshadhri, Andrew Stolman #### Finding forbidden minors in sublinear time: a$O(n^{1/2+o(1)})$-query one-sided tester for minor closed properties on bounded degree graphs 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 >>> TR18-104 | 29th May 2018 Oded Goldreich #### Flexible models for testing graph properties Revisions: 1 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 >>> TR18-131 | 17th July 2018 Gautam Kamath, Christos Tzamos #### Anaconda: A Non-Adaptive Conditional Sampling Algorithm for Distribution Testing 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 >>> TR18-148 | 25th August 2018 Akash Kumar, C. Seshadhri, Andrew Stolman #### Finding forbidden minors in sublinear time: a$n^{1/2+o(1)}$-query one-sided tester for minor closed properties on bounded degree graphs 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 >>> TR18-171 | 10th October 2018 Oded Goldreich #### Testing Graphs in Vertex-Distribution-Free Models Revisions: 1 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 >>> TR18-187 | 4th November 2018 Hadley Black, Deeparnab Chakrabarty, C. Seshadhri #### Domain Reduction for Monotonicity Testing: A$o(d)$Tester for Boolean Functions on Hypergrids Revisions: 4 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 >>> TR18-195 | 18th November 2018 Sofya Raskhodnikova, Noga Ron-Zewi, Nithin Varma #### Erasures versus Errors in Local Decoding and Property Testing 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 >>> TR18-196 | 19th November 2018 Omri Ben-Eliezer #### Testing local properties of arrays 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 >>> TR19-046 | 1st April 2019 Akash Kumar, C. Seshadhri, Andrew Stolman #### andom walks and forbidden minors II: A$\poly(d\eps^{-1})$-query tester for minor-closed properties of bounded degree graphs Revisions: 1 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 >>> TR19-098 | 20th July 2019 Jayadev Acharya, Clement Canonne, Yanjun Han, Ziteng Sun, Himanshu Tyagi #### Domain Compression and its Application to Randomness-Optimal Distributed Goodness-of-Fit 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 >>> TR19-102 | 10th August 2019 Oded Goldreich #### Testing Isomorphism in the Bounded-Degree Graph Model Revisions: 1 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 >>> TR19-124 | 28th August 2019 Roy Gotlib, Tali Kaufman #### Testing Odd Direct Sums Using High Dimensional Expanders 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 >>> TR19-165 | 18th November 2019 Clement Canonne, Xi Chen, Gautam Kamath, Amit Levi, Erik Waingarten #### Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning 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 >>> TR20-058 | 24th April 2020 Shafi Goldwasser, Guy Rothblum, Jonathan Shafer, Amir Yehudayoff #### Interactive Proofs for Verifying Machine Learning Revisions: 1 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 >>> TR20-062 | 29th April 2020 Clement Canonne, Karl Wimmer #### Testing Data Binnings 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 >>> TR20-068 | 3rd May 2020 Oded Goldreich, Dana Ron #### One-Sided Error Testing of Monomials and Affine Subspaces Revisions: 1 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 >>> TR20-109 | 19th July 2020 Oded Goldreich #### On Testing Hamiltonicity in the Bounded Degree Graph Model 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 >>> TR20-149 | 29th September 2020 Oded Goldreich, Avi Wigderson #### Robustly Self-Ordered Graphs: Constructions and Applications to Property Testing Revisions: 2 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 >>> TR20-154 | 10th October 2020 Marcel Dall'Agnol, Tom Gur, Oded Lachish #### A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Privacy 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 >>>

TR20-160 | 2nd November 2020
Oded Goldreich, Avi Wigderson

#### Non-adaptive vs Adaptive Queries in the Dense Graph Testing Model

Revisions: 1

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

TR20-164 | 9th November 2020
Andrej Bogdanov, Gautam Prakriya

#### Direct Sum and Partitionability Testing over General Groups

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

TR20-174 | 18th November 2020

#### Isoperimetric Inequalities for Real-Valued Functions with Applications to Monotonicity Testing

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

TR21-004 | 10th January 2021
Vishnu Iyer, Avishay Tal, Michael Whitmeyer

#### Junta Distance Approximation with Sub-Exponential Queries

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

ISSN 1433-8092 | Imprint