Lucas Bordeaux

UAI Conference 2016 Conference Paper

Political Dimensionality Estimation Using a Probabilistic Graphical Model

• Yoad Lewenberg
• Yoram Bachrach
• Lucas Bordeaux
• Pushmeet Kohli

This paper attempts to move beyond the left-right characterization of political ideologies. We propose a trait based probabilistic model for estimating the manifold of political opinion. We demonstrate the efficacy of our model on two novel and large scale datasets of public opinion. Our experiments show that although the political spectrum is richer than a simple left-right structure, peoples’ opinions on seemingly unrelated political issues are very correlated, so fewer than 10 dimensions are enough to represent peoples’ entire political opinion.

KR Conference 2012 Conference Paper

On Unit-Refutation Complete Formulae with Existentially Quantified Variables

• Lucas Bordeaux
• Mikolas Janota
• Joao Marques-Silva
• Pierre Marquis

Unit resolution is the restriction of the well-known resolution rule where at least one of the two clauses resolved upon is a unit clause, i. e., a clause containing a single literal. A CNF formula α is unit-refutation complete if all clauses δ that are implied by α can be proved by refutation using a unit-resolution proof, i. e., there exists a finite sequence of clauses δ1,..., δn = ⊥, where each δi is a clause of α, or the complementary literal of a literal of δ, or is obtained by unit resolution from two previous clauses of the sequence. Hence, for a unit-refutation complete α, whether a clause δ is implied by α or not is decided by determining whether performing unit resolution on α ∧ ¬δ leads to the empty clause. We analyze, along the lines of the knowledge compilation map, both the tractability and the succinctness of the propositional language URC-C of unit-refutation complete propositional formulae, as well as its disjunctive closure URC-C[∨, ∃], and a superset of URC-C where variables can be existentially quantified and unitrefutation completeness concerns only consequences built up from free variables.

SoCS Conference 2010 Conference Paper

Adaptive K-Parallel Best-First Search: A Simple but Efficient Algorithm for Multi-Core Domain-Independent Planning

• Vincent Vidal 0001
• Lucas Bordeaux
• Youssef Hamadi

Motivated by the recent hardware evolution towards multi-core machines, we investigate parallel planning techniques in a shared-memory environment. We consider, more specifically, parallel versions of a best-first search algorithm that run K threads, each expanding the next best node from the open list. We show that the proposed technique has a number of advantages. First, it is (reasonably) simple: we show how the algorithm can be obtained from a sequential version mostly by adding parallel annotations. Second, we conduct an extensive empirical study that shows that this approach is quite effective. It is also dynamic in the sense that the number of nodes expanded in parallel is adapted during the search. Overall we show that the approach is promising for parallel domain-independent, suboptimal planning.

IJCAI Conference 2009 Conference Paper

• Lucas Bordeaux
• Youssef Hamadi
• Horst Samulowitz

SAT Conference 2008 Conference Paper

A Generalized Framework for Conflict Analysis

• Gilles Audemard
• Lucas Bordeaux
• Youssef Hamadi
• Saïd Jabbour
• Lakhdar Saïs

Abstract This paper presents an extension of Conflict Driven Clauses Learning (CDCL). It relies on an extended notion of implication graph containing additional arcs, called inverse arcs. These are obtained by taking into account the satisfied clauses of the formula, which are usually ignored by conflict analysis. This extension captures more conveniently the whole propagation process, and opens new perspectives for CDCL-based approaches. Among other benefits, our extension leads to a new conflict analysis scheme that exploits the additional arcs to back-jump to higher levels. Experimental results show that the integration of our generalized conflict analysis scheme within two state-of-the-art solvers improves their performance.

AAAI Conference 2005 Conference Paper

CSP Properties for Quantified Constraints: Definitions and Complexity

• Lucas Bordeaux

Quantified constraints and Quantified Boolean Formulae are typically much more difficult to reason with than classical constraints, because quantifier alternation makes the simple, classical notion of solution inappropriate. As a consequence, even such essential CSP properties as consistency or substitutability are not completely understood in the quantified case. In this paper, we show that most of the properties which are used by solvers for CSP can be generalized to Quantified CSP. We propose a systematic study of the relations which hold between these properties, as well as complexity results regarding the decision of these properties. Finally, and since these problems are typically intractable, we generalise the approach used in CSP and propose weakenings of these notions based on locality, which allow for a tractable, albeit incomplete detecting of these properties.

LPAR Conference 2004 Conference Paper

Exploiting Fixable, Removable, and Implied Values in Constraint Satisfaction Problems

• Lucas Bordeaux
• Marco Cadoli
• Toni Mancini

Abstract Complete algorithms for constraint solving typically exploit properties like (in)consistency or interchangeability, which they detect by means of incomplete yet effective algorithms and use to reduce the search space. In this paper, we study a wide range of properties which includes most of the ones used by existing CSP algorithms as well as some which have not yet been considered in the literature, and we investigate their use in CSP solving. We clarify the relationships between these notions and characterise the complexity of the problem of checking them. Following the CSP approach, we then determine a number of relaxations (for instance local versions) which provide sufficient conditions whose detection is tractable. This work is a first step towards a comprehensive framework for CSP properties, and it also shows that new notions still remain to be exploited.