Publication Type

Conference Proceeding Article

Publication Date

7-2014

Abstract

In this paper, we describe a simple randomized algorithm that runs in polynomial time and solves connected row convex (CRC) constraints in distributed settings. CRC constraints generalize many known tractable classes of constraints like 2-SAT and implicational constraints. They can model problems in many domains including temporal reasoning and geometric reasoning, and generally speaking, play the role of "Gaussians" in the logical world. Our simple randomized algorithm for solving them in distributed settings, therefore, has a number of important applications. We support our claims through a theoretical analysis and empirical results.

Discipline

Computer Sciences | Theory and Algorithms

Publication

Proceedings of the Twenty-eighth AAAI Conference On Artificial Intelligence and the Twenty-sixth Innovative Applications of Artificial Intelligence Conference

Volume

3

First Page

2308

Last Page

2314

ISBN

9781577356790

Publisher

AI Access Foundation

City or Country

Quebec City

Creative Commons License

Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.

Additional URL

http://dl.acm.org/citation.cfm?id=2892872

Share

COinS