Search

A system of ℓ linear equations in p unknowns Mx = b is said to have the removal property if every set S ⊆ {1,...,n} which contains o(np − ℓ) solutions of Mx = b can be turned into a set S' containing no solution of Mx = b, by the removal of o(n) elements. Green [GAFA 2005] proved that a single homogenous linear equation always has the removal property, and conjectured that every set of homogenous linear equations has the removal property. In this paper we confirm Green΄s conjecture by showing that every set of linear equations (even non-homogenous) has the removal property. We also discuss some applications of our result in theoretical computer science, and in particular, use it to resolve a conjecture of Bhattacharyya, Chen, Sudan and Xie [4] related to algorithms for testing properties of boolean functions. [ABSTRACT FROM AUTHOR]

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 by a property and its testability. Particularly, they studied properties that were invariant under linear transformations of the domain and gave a characterization of testability in certain settings. However, the properties that they examined were also linear. This led us to investigate linear-invariant properties that are not necessarily linear. Here we describe some of the resulting works which consider natural linear-invariant properties, specifically properties that are described by forbidden patterns of values that a function can take, and show testability under various settings. [ABSTRACT FROM AUTHOR]

In property testing, the goal is to distinguish between objects that satisfy some desirable property and objects that are far from satisfying it, after examining only a small, random sample of the object in question. Although much of the literature has focused on properties of graphs, very recently several strong results on hypergraphs have appeared. We revisit a logical result obtained by Alon et al. [1] in the light of these recent results. The main result is the testability of all properties (of relational structures) expressible in sentences of Ramsey΄s class. [ABSTRACT FROM AUTHOR]

In property testing, the goal is to distinguish between structures that have some desired property and those that are far from having the property, after examining only a small, random sample of the structure. We focus on the classification of first-order sentences based on their quantifier prefixes and vocabulary into testable and untestable classes. This classification was initiated by Alon et al. [1], who showed that graph properties expressible with quantifier patterns ∅ * ∀ * are testable but that there is an untestable graph property expressible with quantifier pattern ∀ * ∅ *. In the present paper, their untestable example is simplified. In particular, it is shown that there is an untestable graph property expressible with each of the following quantifier patterns: ∀ ∅ ∀ ∅, ∀ ∅ ∀ 2, ∀ 2 ∅ ∀ and ∀ 3 ∅. [ABSTRACT FROM AUTHOR]

Given a directed graph G = (V,E) and an integer k ≥ 1, a k-transitive-closure-spanner (k-TC-spanner) of G is a directed graph H = (V, EH) that has (1) the same transitive-closure as G and (2) diameter at most k. Transitive-closure spanners are a common abstraction for applications in access control, property testing and data structures. We show a connection between 2-TC-spanners and local monotonicity reconstructors. A local monotonicity reconstructor, introduced by Saks and Seshadhri (SIAM Journal on Computing, 2010), is a randomized algorithm that, given access to an oracle for an almost monotone function f : [m]d →ℝ, can quickly evaluate a related function g : [m]d →ℝ which is guaranteed to be monotone. Furthermore, the reconstructor can be implemented in a distributed manner. We show that an efficient local monotonicity reconstructor implies a sparse 2-TC-spanner of the directed hypergrid (hypercube), providing a new technique for proving lower bounds for local monotonicity reconstructors. Our connection is, in fact, more general: an efficient local monotonicity reconstructor for functions on any partially ordered set (poset) implies a sparse 2-TC-spanner of the directed acyclic graph corresponding to the poset. We present tight upper and lower bounds on the size of the sparsest 2-TC-spanners of the directed hypercube and hypergrid. These bounds imply tighter lower bounds for local monotonicity reconstructors that nearly match the known upper bounds. [ABSTRACT FROM AUTHOR]

We take another step in the study of the testability of small-width OBDDs, initiated by Ron and Tsur (Random΄09). That is, we consider algorithms that, given oracle access to a function f:{0,1}n →{0,1}, need to determine whether f can be implemented by some restricted class of OBDDs or is far from any such function. Ron and Tsur showed that testing whether a function f:{0,1}n →{0,1} is implementable by a width-2 OBDD has query complexity Θ(logn). Thus, testing width-2 OBDD functions is significantly easier than learning such functions (which requires Ώ(n) queries). We show that such exponential gaps do not hold for several related classes. Specifically: 1 Testing whether f:{0,1}n →{0,1} is implementable by a width-4 OBDD requires ]> queries. 1 Testing whether f:GF(3)n→GF(3) is a linear function with 0-1 coefficients requires ]> queries. Note that this class of functions is a subset of the class of all linear functions over GF(3), and that each such linear function can be implemented by a width-3 OBDD. 1 There exists a subclass ]> of the linear functions from GF(2)n to GF(2) such that testing membership in ]> has query complexity Θ(n). Note that each linear function over GF(2) can be implemented by a width-2 OBDD. Recall that each of these classes has a proper learning algorithm of query complexity O(n). [ABSTRACT FROM AUTHOR]

A hypergraph dictatorship test is first introduced by Samorodnitsky and Trevisan and serves as a key component in their unique games based ]> 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 influences are o(1). Their test makes q ≥ 3 queries, has amortized query complexity ]> , but has an inherent loss of perfect completeness. In this paper we give an (adaptive) hypergraph dictatorship test that achieves both perfect completeness and amortized query complexity ]> . [ABSTRACT FROM AUTHOR]

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 Θ(q). Such results are proven in three standard domains often considered in property testing: generic functions, adjacency predicates describing (dense) graphs, and incidence functions describing bounded-degree graphs. While in two cases the proofs are quite straightforward, the techniques employed in the case of the dense graph model seem significantly more involved. Specifically, problems that arise and are treated in the latter case include (1) the preservation of distances between graph under a blow-up operation, and (2) the construction of monotone graph properties that have local structure. [ABSTRACT FROM AUTHOR]

The ˵richness″ of properties that are indistinguishable from first-order properties is investigated. Indistinguishability is a concept of equivalence among properties of combinatorial structures that is appropriate in the context of testability. All formulas in a restricted class of second-order logic are shown to be indistinguishable from first-order formulas. Arbitrarily hard properties, including RE-complete properties, that are indistinguishable from first-order formulas are shown to exist. Implications on the search for a logical characterization of the testable properties are discussed. [ABSTRACT FROM AUTHOR]