Author name cluster

Matthew Valeriote

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

2 author rows

JMLR Journal 2019 Journal Article

Learnability of Solutions to Conjunctive Queries

Hubie Chen
Matthew Valeriote

The problem of learning the solution space of an unknown formula has been studied in multiple embodiments in computational learning theory. In this article, we study a family of such learning problems; this family contains, for each relational structure, the problem of learning the solution space of an unknown conjunctive query evaluated on the structure. A progression of results aimed to classify the learnability of each of the problems in this family, and thus far a culmination thereof was a positive learnability result generalizing all previous ones. This article completes the classification program towards which this progression of results strived, by presenting a negative learnability result that complements the mentioned positive learnability result. In addition, a further negative learnability result is exhibited, which indicates a dichotomy within the problems to which the first negative result applies. In order to obtain our negative results, we make use of universal-algebraic concepts. [abs] [ pdf ][ bib ] &copy JMLR 2019. ( edit, beta )

PDF Details

FOCS Conference 2016 Conference Paper

Testing Assignments to Constraint Satisfaction Problems

Hubie Chen
Matthew Valeriote
Yuichi Yoshida

For a finite relational structure A, let CSP(A) denote the CSP instances whose constraint relations are taken from A. The resulting family of problems CSP(A) has been considered heavily in a variety of computational contexts. In this article, we consider this family from the perspective of property testing: given an instance of a CSP and query access to an assignment, one wants to decide whether the assignment satisfies the instance, or is far from so doing. While previous work on this scenario studied concrete templates or restricted classes of structures, this article presents comprehensive classification theorems. Our first contribution is a dichotomy theorem completely characterizing the structures A such that CSP(A) is constant-query testable: (i) If A has a majority polymorphism and a Maltsev polymorphism, then CSP(A) is constant-query testable with one-sided error. (ii) Else, testing CSP(A) requires a super-constant number of queries. Let ∃CSP(A) denote the extension of CSP(A) to instances which may include existentially quantified variables. Our second contribution is to classify all structures A in terms of the number of queries needed to test assignments to instances of ∃CSP(A), with one-sided error. More specifically, we show the following trichotomy (i) If A has a majority polymorphism and a Maltsev polymorphism, then ∃CSP(A) is constant-query testable with one-sided error. (ii) Else, if A has a (k + 1)-ary near-unanimity polymorphism for some k ≥ 2, and no Maltsev polymorphism then ∃CSP(A) is not constant-query testable (even with two-sided error) but is sublinear-query testable with one-sided error. (iii) Else, testing ∃CSP(A) with one-sided error requires a linear number of queries.

Details

I&C Journal 2013 Journal Article

Generic expression hardness results for primitive positive formula comparison

Simone Bova
Hubie Chen
Matthew Valeriote

We study the expression complexity of two basic problems involving the comparison of primitive positive formulas: equivalence and containment. In particular, we study the complexity of these problems relative to finite relational structures. We present two generic hardness results for the studied problems, and discuss evidence that they are optimal and yield, for each of the problems, a complexity trichotomy.

Details DOI