Phase Transition Behavior of Cardinality and XOR Constraints

Pote, Yash and Joshi, Saurabh and Meel, Kuldeep S (2019) Phase Transition Behavior of Cardinality and XOR Constraints. International Joint Conferences on Artificial Intelligence.

[img]
Preview
Text
ijcai19pjm.pdf

Download (587kB) | Preview

Abstract

The runtime performance of modern SAT solvers is deeply connected to the phase transition behavior of CNF formulas. While CNF solving has witnessed significant runtime improvement over the past two decades, the same does not hold for several other classes such as the conjunction of cardinality and XOR constraints, denoted as CARD-XOR formulas. The problem of determining satisfiability of CARDXOR formulas is a fundamental problem with wide variety of applications ranging from discrete integration in the field of artificial intelligence to maximum likelihood decoding in coding theory. The runtime behavior of random CARD-XOR formulas is unexplored in prior work. In this paper, we present the first rigorous empirical study to characterize the runtime behavior of 1-CARD-XOR formulas. We show empirical evidence of a surprising phase-transition that follows a non-linear tradeoff between CARD and XOR constraints.

[error in script]
IITH Creators:
IITH CreatorsORCiD
Joshi, SaurabhUNSPECIFIED
Item Type: Article
Subjects: Computer science
Divisions: Department of Computer Science & Engineering
Depositing User: Team Library
Date Deposited: 22 Jul 2019 06:28
Last Modified: 22 Jul 2019 06:28
URI: http://raiith.iith.ac.in/id/eprint/5758
Publisher URL:
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 5758 Statistics for this ePrint Item