BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Hubie Chen

Hubie Chen appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Computational ComplexityLogic in Computer ScienceArtificial IntelligenceDatabasesData Structures and Algorithmsmath.LOComputer Science and Game Theorymath.RA

Catalog footprint

What is connected

21works
8topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

21 published item(s)

preprint2020arXiv

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

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.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Sparsification Lower Bounds for List $H$-Coloring

We investigate the List $H$-Coloring problem, the generalization of graph coloring that asks whether an input graph $G$ admits a homomorphism to the undirected graph $H$ (possibly with loops), such that each vertex $v \in V(G)$ is mapped to a vertex on its list $L(v) \subseteq V(H)$. An important result by Feder, Hell, and Huang [JGT 2003] states that List $H$-Coloring is polynomial-time solvable if $H$ is a so-called bi-arc graph, and NP-complete otherwise. We investigate the NP-complete cases of the problem from the perspective of polynomial-time sparsification: can an $n$-vertex instance be efficiently reduced to an equivalent instance of bitsize $O(n^{2-\varepsilon})$ for some $\varepsilon > 0$? We prove that if $H$ is not a bi-arc graph, then List $H$-Coloring does not admit such a sparsification algorithm unless $NP \subseteq coNP/poly$. Our proofs combine techniques from kernelization lower bounds with a study of the structure of graphs $H$ which are not bi-arc graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Counting Answers to Existential Positive Queries: A Complexity Classification

Existential positive formulas form a fragment of first-order logic that includes and is semantically equivalent to unions of conjunctive queries, one of the most important and well-studied classes of queries in database theory. We consider the complexity of counting the number of answers to existential positive formulas on finite structures and give a trichotomy theorem on query classes, in the setting of bounded arity. This theorem generalizes and unifies several known results on the complexity of conjunctive queries and unions of conjunctive queries.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

One Hierarchy Spawns Another: Graph Deconstructions and the Complexity Classification of Conjunctive Queries

We study the problem of conjunctive query evaluation relative to a class of queries; this problem is formulated here as the relational homomorphism problem relative to a class of structures A, wherein each instance must be a pair of structures such that the first structure is an element of A. We present a comprehensive complexity classification of these problems, which strongly links graph-theoretic properties of A to the complexity of the corresponding homomorphism problem. In particular, we define a binary relation on graph classes, which is a preorder, and completely describe the resulting hierarchy given by this relation. This relation is defined in terms of a notion which we call graph deconstruction and which is a variant of the well-known notion of tree decomposition. We then use this hierarchy of graph classes to infer a complexity hierarchy of homomorphism problems which is comprehensive up to a computationally very weak notion of reduction, namely, a parameterized version of quantifier-free first-order reduction. In doing so, we obtain a significantly refined complexity classification of homomorphism problems, as well as a unifying, modular, and conceptually clean treatment of existing complexity classifications. We then present and develop the theory of Ehrenfeucht-Fraisse-style pebble games which solve the homomorphism problems where the cores of the structures in A have bounded tree depth. Finally, we use our framework to classify the complexity of model checking existential sentences having bounded quantifier rank.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Proof Complexity Modulo the Polynomial Hierarchy: Understanding Alternation as a Source of Hardness

We present and study a framework in which one can present alternation-based lower bounds on proof length in proof systems for quantified Boolean formulas. A key notion in this framework is that of proof system ensemble, which is (essentially) a sequence of proof systems where, for each, proof checking can be performed in the polynomial hierarchy. We introduce a proof system ensemble called relaxing QU-res which is based on the established proof system QU-resolution. Our main results include an exponential separation of the tree-like and general versions of relaxing QU-res, and an exponential lower bound for relaxing QU-res; these are analogs of classical results in propositional proof complexity.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Testing Assignments to Constraint Satisfaction Problems

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 works 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 $\exists$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 $\exists$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 $\exists$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 \geq 2$, and no Maltsev polymorphism then $\exists$CSP(A) is not constant-query testable (even with two-sided error) but is sublinear-query testable with one-sided error. (iii) Else, testing $\exists$CSP(A) with one-sided error requires a linear number of queries.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

A Trichotomy in the Complexity of Counting Answers to Conjunctive Queries

Conjunctive queries are basic and heavily studied database queries; in relational algebra, they are the select-project-join queries. In this article, we study the fundamental problem of counting, given a conjunctive query and a relational database, the number of answers to the query on the database. In particular, we study the complexity of this problem relative to sets of conjunctive queries. We present a trichotomy theorem, which shows essentially that this problem on a set of conjunctive queries is either tractable, equivalent to the parameterized CLIQUE problem, or as hard as the parameterized counting CLIQUE problem; the criteria describing which of these situations occurs is simply stated, in terms of graph-theoretic conditions.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Parameter Compilation

In resolving instances of a computational problem, if multiple instances of interest share a feature in common, it may be fruitful to compile this feature into a format that allows for more efficient resolution, even if the compilation is relatively expensive. In this article, we introduce a formal framework for classifying problems according to their compilability. The basic object in our framework is that of a parameterized problem, which here is a language along with a parameterization---a map which provides, for each instance, a so-called parameter on which compilation may be performed. Our framework is positioned within the paradigm of parameterized complexity, and our notions are relatable to established concepts in the theory of parameterized complexity. Indeed, we view our framework as playing a unifying role, integrating together parameterized complexity and compilability theory.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

An Algebraic Hardness Criterion for Surjective Constraint Satisfaction

The constraint satisfaction problem (CSP) on a relational structure B is to decide, given a set of constraints on variables where the relations come from B, whether or not there is a assignment to the variables satisfying all of the constraints; the surjective CSP is the variant where one decides the existence of a surjective satisfying assignment onto the universe of B. We present an algebraic condition on the polymorphism clone of B and prove that it is sufficient for the hardness of the surjective CSP on a finite structure B, in the sense that this problem admits a reduction from a certain fixed-structure CSP. To our knowledge, this is the first result that allows one to use algebraic information from a relational structure B to infer information on the complexity hardness of surjective constraint satisfaction on B. A corollary of our result is that, on any finite non-trivial structure having only essentially unary polymorphisms, surjective constraint satisfaction is NP-complete.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Beyond Q-Resolution and Prenex Form: A Proof System for Quantified Constraint Satisfaction

We consider the quantified constraint satisfaction problem (QCSP) which is to decide, given a structure and a first-order sentence (not assumed here to be in prenex form) built from conjunction and quantification, whether or not the sentence is true on the structure. We present a proof system for certifying the falsity of QCSP instances and develop its basic theory; for instance, we provide an algorithmic interpretation of its behavior. Our proof system places the established Q-resolution proof system in a broader context, and also allows us to derive QCSP tractability results.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

The Tractability Frontier of Graph-Like First-Order Query Sets

We study first-order model checking, by which we refer to the problem of deciding whether or not a given first-order sentence is satisfied by a given finite structure. In particular, we aim to understand on which sets of sentences this problem is tractable, in the sense of parameterized complexity theory. To this end, we define the notion of a graph-like sentence set, which definition is inspired by previous work on first-order model checking wherein the permitted connectives and quantifiers were restricted. Our main theorem is the complete tractability classification of such graph-like sentence sets, which is (to our knowledge) the first complexity classification theorem concerning a class of sentences that has no restriction on the connectives and quantifiers. To present and prove our classification, we introduce and develop a novel complexity-theoretic framework which is built on parameterized complexity and includes new notions of reduction.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

An Algebraic Preservation Theorem for Aleph-Zero Categorical Quantified Constraint Satisfaction

We prove an algebraic preservation theorem for positive Horn definability in aleph-zero categorical structures. In particular, we define and study a construction which we call the periodic power of a structure, and define a periomorphism of a structure to be a homomorphism from the periodic power of the structure to the structure itself. Our preservation theorem states that, over an aleph-zero categorical structure, a relation is positive Horn definable if and only if it is preserved by all periomorphisms of the structure. We give applications of this theorem, including a new proof of the known complexity classification of quantified constraint satisfaction on equality templates.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space Complexity

We perform a fundamental investigation of the complexity of conjunctive query evaluation from the perspective of parameterized complexity. We classify sets of boolean conjunctive queries according to the complexity of this problem. Previous work showed that a set of conjunctive queries is fixed-parameter tractable precisely when the set is equivalent to a set of queries having bounded treewidth. We present a fine classification of query sets up to parameterized logarithmic space reduction. We show that, in the bounded treewidth regime, there are three complexity degrees and that the properties that determine the degree of a query set are bounded pathwidth and bounded tree depth. We also engage in a study of the two higher degrees via logarithmic space machine characterizations and complete problems. Our work yields a significantly richer perspective on the complexity of conjunctive queries and, at the same time, suggests new avenues of research in parameterized complexity.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Generic Expression Hardness Results for Primitive Positive Formula Comparison

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.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Meditations on Quantified Constraint Satisfaction

The quantified constraint satisfaction problem (QCSP) is the problem of deciding, given a structure and a first-order prenex sentence whose quantifier-free part is the conjunction of atoms, whether or not the sentence holds on the structure. One obtains a family of problems by defining, for each structure B, the problem QCSP(B) to be the QCSP where the structure is fixed to be B. In this article, we offer a viewpoint on the research program of understanding the complexity of the problems QCSP(B) on finite structures. In particular, we propose and discuss a group of conjectures; throughout, we attempt to place the conjectures in relation to existing results and to emphasize open issues and potential research directions.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

On the Complexity of Existential Positive Queries

We systematically investigate the complexity of model checking the existential positive fragment of first-order logic. In particular, for a set of existential positive sentences, we consider model checking where the sentence is restricted to fall into the set; a natural question is then to classify which sentence sets are tractable and which are intractable. With respect to fixed-parameter tractability, we give a general theorem that reduces this classification question to the corresponding question for primitive positive logic, for a variety of representations of structures. This general theorem allows us to deduce that an existential positive sentence set having bounded arity is fixed-parameter tractable if and only if each sentence is equivalent to one in bounded-variable logic. We then use the lens of classical complexity to study these fixed-parameter tractable sentence sets. We show that such a set can be NP-complete, and consider the length needed by a translation from sentences in such a set to bounded-variable logic; we prove superpolynomial lower bounds on this length using the theory of compilability, obtaining an interesting type of formula size lower bound. Overall, the tools, concepts, and results of this article set the stage for the future consideration of the complexity of model checking on more expressive logics.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Peek Arc Consistency

This paper studies peek arc consistency, a reasoning technique that extends the well-known arc consistency technique for constraint satisfaction. In contrast to other more costly extensions of arc consistency that have been studied in the literature, peek arc consistency requires only linear space and quadratic time and can be parallelized in a straightforward way such that it runs in linear time with a linear number of processors. We demonstrate that for various constraint languages, peek arc consistency gives a polynomial-time decision procedure for the constraint satisfaction problem. We also present an algebraic characterization of those constraint languages that can be solved by peek arc consistency, and study the robustness of the algorithm.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Arc Consistency and Friends

A natural and established way to restrict the constraint satisfaction problem is to fix the relations that can be used to pose constraints; such a family of relations is called a constraint language. In this article, we study arc consistency, a heavily investigated inference method, and three extensions thereof from the perspective of constraint languages. We conduct a comparison of the studied methods on the basis of which constraint languages they solve, and we present new polynomial-time tractability results for singleton arc consistency, the most powerful method studied.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Bounded Rationality, Strategy Simplification, and Equilibrium

It is frequently suggested that predictions made by game theory could be improved by considering computational restrictions when modeling agents. Under the supposition that players in a game may desire to balance maximization of payoff with minimization of strategy complexity, Rubinstein and co-authors studied forms of Nash equilibrium where strategies are maximally simplified in that no strategy can be further simplified without sacrificing payoff. Inspired by this line of work, we introduce a notion of equilibrium whereby strategies are also maximally simplified, but with respect to a simplification procedure that is more careful in that a player will not simplify if the simplification incents other players to deviate. We study such equilibria in two-player machine games in which players choose finite automata that succinctly represent strategies for repeated games; in this context, we present techniques for establishing that an outcome is at equilibrium and present results on the structure of equilibria.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

The reducts of equality up to primitive positive interdefinability

We initiate the study of reducts of relational structures up to primitive positive interdefinability: After providing the tools for such a study, we apply these tools in order to obtain a classification of the reducts of the logic of equality. It turns out that there exists a continuum of such reducts. Equivalently, expressed in the language of universal algebra, we classify those locally closed clones over a countable domain which contain all permutations of the domain.

0 citations0 reviewsNo code linkedOpen access