Hubie Chen

IJCAI Conference 2020 Conference Paper

Semantic Width and the Fixed-Parameter Tractability of Constraint Satisfaction Problems

• Hubie Chen
• Georg Gottlob
• Matthias Lanzinger
• Reinhard Pichler

Constraint satisfaction problems (CSPs) are an important formal framework for the uniform treatment of various prominent AI tasks, e. g. , coloring or scheduling problems. Solving CSPs is, in general, known to be NP-complete and fixed-parameter intractable when parameterized by their constraint scopes. We give a characterization of those classes of CSPs for which the problem becomes fixed-parameter tractable. Our characterization significantly increases the utility of the CSP framework by making it possible to decide the fixed-parameter tractability of problems via their CSP formulations. We further extend our characterization to the evaluation of unions of conjunctive queries, a fundamental problem in databases. Furthermore, we provide some new insight on the frontier of PTIME solvability of CSPs. In particular, we observe that bounded fractional hypertree width is more general than bounded hypertree width only for classes that exhibit a certain type of exponential growth. The presented work resolves a long-standing open problem and yields powerful new tools for complexity research in AI and database theory.

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 )

Highlights Conference 2016 Conference Abstract

A Dual to a Classical Graph Homomorphism Theorem of Lovász

• Hubie Chen
• Stefan Mengel

Homomorphism between finite structures are a classical object of study considered in many areas including structural graph theory, constraint satisfaction and database theory. A classical result by Lovász states that every structure B is uniquely characterized (up to isomorphism) by the number of homomorphisms from other structures to B. In this talk I will I will give a dual version of this result that roughly says that every structure is uniquely described by the number of homomorphisms it has to other graphs.

CSL Conference 2016 Conference Paper

Quantified Constraint Satisfaction on Monoids

• Hubie Chen
• Peter Mayr 0001

We contribute to a research program that aims to classify, for each finite structure, the computational complexity of the quantified constraint satisfaction problem on the structure. Employing an established algebraic viewpoint to studying this problem family, whereby this classification program can be phrased as a classification of algebras, we give a complete classification of all finite monoids.

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.

TIME Conference 2012 Conference Paper

Guarded Ord-Horn: A Tractable Fragment of Quantified Constraint Satisfaction

• Hubie Chen
• Michal Wrona

The first-order theory of dense linear orders without endpoints is well-known to be PSPACE-complete. We present polynomial-time tractability results for fragments of this theory which are defined by syntactic restriction, in particular, our fragments can be described using the framework of quantified constraint satisfaction over Ord-Horn clauses.

TCS Journal 2010 Journal Article

Peek arc consistency

• Manuel Bodirsky
• Hubie Chen

TCS Journal 2009 Journal Article

Maximal infinite-valued constraint languages

• Manuel Bodirsky
• Hubie Chen
• Jan Kára
• Timo von Oertzen

ICAPS Conference 2008 Conference Paper

Causal Graphs and Structurally Restricted Planning

• Hubie Chen
• Omer Giménez

The causal graph is a directed graph that describes the variable dependencies present in a planning instance. A number of papers have studied the causal graph in both practical and theoretical settings. In this work, we systematically study the complexity of planning restricted by the causal graph. In particular, any set of causal graphs gives rise to a subcase of the planning problem. We give a complete classification theorem on causal graphs, showing that a set of graphs is either polynomial-time tractable, or is not polynomial-time tractable unless an established complexity-theoretic assumption fails; our theorem describes which graph sets correspond to each of the two cases. We also give a classification theorem for the case of reversible planning, and discuss the general direction of structurally restricted planning.

ICAPS Conference 2007 Conference Paper

Act Local, Think Global: Width Notions for Tractable Planning

• Hubie Chen
• Omer Giménez

Many of the benchmark domains in AI planning are tractable on an individual basis. In this paper, we seek a theoretical, domain-independent explanation for their tractability. We present a family of structural conditions that both imply tractability and capture some of the established benchmark domains. These structural conditions are, roughly speaking, based on measures of how many variables need to be changed in order to move a state closer to a goal state.

TCS Journal 2007 Journal Article

Learning intersection-closed classes with signatures

• Andrei Bulatov
• Hubie Chen
• Víctor Dalmau

CSL Conference 2007 Conference Paper

Qualitative Temporal and Spatial Reasoning Revisited

• Manuel Bodirsky
• Hubie Chen

Abstract Establishing local consistency is one of the main algorithmic techniques in temporal and spatial reasoning. In this area, one of the central questions for the various proposed temporal and spatial constraint languages is whether local consistency implies global consistency. Showing that a constraint language Γ has this “local-to-global” property implies polynomial-time tractability of the constraint language, and has further pleasant algorithmic consequences. In the present paper, we study the “local-to-global” property by making use of a recently established connection of this property with universal algebra. Specifically, the connection shows that this property is equivalent to the presence of a so-called quasi near-unanimity polymorphism of the constraint language. We obtain new algorithmic results and give very concise proofs of previously known theorems. Our results concern well-known and heavily studied formalisms such as the point algebra and its extensions, Allen’s interval algebra, and the spatial reasoning language RCC-5.

CSL Conference 2006 Conference Paper

Collapsibility in Infinite-Domain Quantified Constraint Satisfaction

• Manuel Bodirsky
• Hubie Chen

Abstract In this article, we study the quantified constraint satisfaction problem (QCSP) over infinite domains. We develop a technique called collapsibility that allows one to give strong complexity upper bounds on the QCSP. This technique makes use of both logical and universal-algebraic ideas. We give applications illustrating the use of our technique.

IJCAI Conference 2005 Conference Paper

A Model for Generating Random Quantified Boolean Formulas

• Hubie Chen
• Yannet

The quantified boolean formula (QBF) problem is a powerful generalization of the boolean satisfiability (SAT) problem where variables can be both universally and existentially quantified. Inspired by the fruitfulness of the established model for generating random SAT instances, we define and study a general model for generating random QBF instances. We exhibit experimental results showing that our model bears certain desirable similarities to the random SAT model, as well as a number of theoretical results concerning our model.

CSL Conference 2005 Conference Paper

From Pebble Games to Tractability: An Ambidextrous Consistency Algorithm for Quantified Constraint Satisfaction

• Hubie Chen
• Víctor Dalmau

Abstract The constraint satisfaction problem (CSP) and quantified constraint satisfaction problem (QCSP) are common frameworks for the modelling of computational problems. Although they are intractable in general, a rich line of research has identified restricted cases of these problems that are tractable in polynomial time. Remarkably, many tractable cases of the CSP that have been identified are solvable by a single algorithm, which we call here the consistency algorithm. In this paper, we give a natural extension of the consistency algorithm to the QCSP setting, by making use of connections between the consistency algorithm and certain two-person pebble games. Surprisingly, we demonstrate a variety of tractability results using the algorithm, revealing unified structure among apparently different cases of the QCSP.

TCS Journal 2004 Journal Article

A coalgebraic approach to Kleene algebra with tests

• Hubie Chen
• Riccardo Pucella

AAAI Conference 2004 Conference Paper

Collapsibility and Consistency in Quantified Constraint Satisfaction

• Hubie Chen

The concept of consistency has pervaded studies of the constraint satisfaction problem. We introduce two concepts, which are inspired by consistency, for the more general framework of the quantified constraint satisfaction problem (QCSP). We use these concepts to derive, in a uniform fashion, proofs of polynomial-time tractability and corresponding algorithms for certain cases of the QCSP where the types of allowed relations are restricted. We not only unify existing tractability results and algorithms, but also identify new classes of tractable QCSPs.

SAT Conference 2004 Conference Paper

Looking Algebraically at Tractable Quantified Boolean Formulas

• Hubie Chen
• Víctor Dalmau

We make use of the algebraic theory that has been used to study the complexity of constraint satisfaction problems, to investigate tractable quantified boolean formulas. We present a pair of results: the first is a new and simple algebraic proof of the tractability of quantified 2-satisfiability; the second is a purely algebraic characterization of models for quantified Horn formulas that were given by Büning, Subramani, and Zhao, and described proof-theoretically.

MFCS Conference 2004 Conference Paper

Optimization, Games, and Quantified Constraint Satisfaction

• Hubie Chen
• Martin Pál

Abstract Optimization problems considered in the literature generally assume a passive environment that does not react to the actions of an agent. In this paper, we introduce and study a class of optimization problems in which the environment plays an active, adversarial role and responds dynamically to the actions of an agent; this class of problems is based on the framework of quantified constraint satisfaction. We formalize a new notion of approximation algorithm for these optimization problems, and consider certain restricted versions of the general problem obtained by restricting the types of constraints that may appear. Our main result is a dichotomy theorem classifying exactly those restricted versions having a constant factor approximation algorithm.

ECAI Conference 2004 Conference Paper

Quantified Constraint Satisfaction and Bounded Treewidth

• Hubie Chen

IJCAI Conference 2003 Conference Paper

A Theory of Average-Case Compilability in Knowledge Representation

• Hubie Chen

Compilability is a fundamental property of knowledge representation formalisms which captures how succinctly information can be expressed. Although many results concerning compilability have been obtained, they are all "worst-case" results. We develop a theory of average-case compilability which allows for the formal comparison and classification of knowledge representation formalisms "on average. "

SAT Conference 2003 Conference Paper

An Algorithm for SAT Above the Threshold

• Hubie Chen

Abstract We study algorithms for finding satisfying assignments of randomly generated 3-SAT formula. In particular, we consider distributions of highly constrained formulas (that is, “above the threshold” formulas) restricted to satisfiable instances. We obtain positive algorithmic results, showing that such formulas can be solved in low exponential time.

MFCS Conference 2003 Conference Paper

Arithmetic Constant-Depth Circuit Complexity Classes

• Hubie Chen

Abstract The boolean circuit complexity classes AC 0 ⊆ AC 0 [ m ] ⊆ TC 0 ⊆ NC 1 have been studied intensely. Other than NC 1, they are defined by constant-depth circuits of polynomial size and unbounded fan-in over some set of allowed gates. One reason for interest in these classes is that they contain the boundary marking the limits of current lower bound technology: such technology exists for AC 0 and some of the classes AC 0 [ m ], while the other classes AC 0 [ m ] as well as TC 0 lack such technology. Continuing a line of research originating from Valiant’s work on the counting class \(\ensuremath{\sharp} P\), the arithmetic circuit complexity classes \(\ensuremath{\sharp} AC^0\) and \(\ensuremath{\sharp} NC^1\) have recently been studied. In this paper, we define and investigate the classes \(\ensuremath{\sharp} AC^0[m]\) and \(\ensuremath{\sharp} TC^0\), new arithmetic circuit complexity classes that are defined by constant-depth circuits and are analogues of the classes AC 0 [ m ] and TC 0.

IJCAI Conference 2003 Conference Paper

Inverse Circumscription

• Hubie Chen

Inverse (or identification) problems involve decid­ ing whether or not an explicitly given set of data points have an implicit description, for instance, in the form of a constraint network. Such prob­ lems provide insight into the relationships among various representations of knowledge, which may have differing computational properties. This pa­ per formalizes and studies the inverse circumscription problem, which (roughly speaking) is to de­ cide, given a set of models, if there exists a formula whose circumscription describes the input set.

MFCS Conference 2003 Conference Paper

Inverse NP Problems

• Hubie Chen

Abstract One characterization of the class NP is as the class of all languages for which there exists a polynomial-time verifier with the following properties: for every member of the language, there exists a polynomially-sized proof causing the verifier to accept; and, for every non-member, there is no proof causing the verifier to accept. Relative to a particular verifier, every member x of the language induces a set of proofs, namely, the set of proofs causing the verifier to accept x. This paper studies the complexity of deciding, given a set Π of proofs, whether or not there exists some x inducing Π (relative to a particular verifier). We call this decision problem the inverse problem for the verifier. We introduce a new notion of reduction suited for inverse problems, and use it to classify as coNP-complete the inverse problems for the “natural” verifiers of many NP-complete problems.