Arrow Research search

Author name cluster

Andrei Bulatov

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.

8 papers
1 author row

Possible papers

8

AAAI Conference 2021 Conference Paper

Algebra of Modular Systems: Containment and Equivalence

  • Andrei Bulatov
  • Eugenia Ternovska

The Algebra of Modular System is a KR formalism that allows for combinations of modules written in multiple languages. Informally, a module represents a piece of knowledge. It can be given by a knowledge base, be an agent, an ASP, ILP, CP program, etc. Formally, a module is a class of structures over the same vocabulary. Modules are combined declaratively, using, essentially, operations of Codd’s relational algebra. In this paper, we address the problem of checking modular system containment, which we relate to a homomorphism problem. We prove that, for a large class of modular systems, the containment problem (and thus equivalence) is in the complexity class NP, and therefore is solvable by, e. g. , SAT solvers. We discuss conditions under which the problem is polynomial time solvable.

PDF Details

AAAI Conference 2021 Conference Paper

Satisfiability and Algorithms for Non-uniform Random k-SAT

  • Oleksii Omelchenko
  • Andrei Bulatov

Solving Satisfiability is at the core of a wide range of applications from Knowledge Representation to Logic Programming to Software and Hardware Verification. One of the models of Satisfiability, the Random Satisfiability problem, has received much attention in the literature both, as a useful benchmark for SAT solvers, and as an exciting mathematical object. In this paper we tackle a somewhat nonstandard type of Random Satisfiability, the one where instances are not chosen uniformly from a certain class of instances, but rather from a certain nontrivial distribution. More precisely, we use socalled Configuration Model, in which we start with a distribution of degrees (the number of occurrences) of a variable, sample the degree of each variable and then generate a random instance with the prescribed degrees. It has been proposed previously that by properly selecting the starting distribution (to be, say, power law or lognorm) one can approximate at least some aspect of ‘industrial’ instances of SAT. Here we suggest an algorithm that solves such problems for a wide range of degree distributions and obtain a necessary and a sufficient condition for the satisfiability of such formulas.

PDF Details

Highlights Conference 2018 Conference Abstract

The Complexity of Constraints: Dichotomies and Beyond

  • Andrei Bulatov

ABSTRACT. This talk is devoted to the recent results on the Dichotomy Conjecture for the Constraint Satisfaction Problem (CSP) posed by Feder and Vardi in 1993. We will briefly review the research leading up to the dichotomy theorem for the CSP, outline the solution algorithm, and discuss remaining open problems and future research directions.

Details