Error-Correcting and Verifiable Parallel Inference in Graphical Models

Negin Karimi, Petteri Kaski, Mikko Koivisto

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review


We present a novel framework for parallel exact inference in graphical models. Our framework supports error-correction during inference and enables fast verification that the result of inference is correct, with probabilistic soundness. The computational complexity of inference essentially matches the cost of w-cutset conditioning, a known generalization of Pearl's classical loop-cutset conditioning for inference. Verifying the result for correctness can be done with as little as essentially the square root of the cost of inference. Our main technical contribution amounts to designing a low-degree polynomial extension of the cutset approach, and then reducing to a univariate polynomial employing techniques recently developed for noninteractive probabilistic proof systems.
Original languageEnglish
Title of host publicationProceedings of the AAAI Conference on Artificial Intelligence
Place of PublicationPalo Alto, CA, USA
Number of pages10201
Volume34 (06)
ISBN (Print)978-1-57735-835-0
Publication statusPublished - 3 Apr 2020
MoE publication typeA4 Article in a conference publication
EventAAAI Conference on Artificial Intelligence - New York, United States
Duration: 7 Feb 202012 Feb 2020
Conference number: 34

Publication series

NameProceedings of the AAAI Conference on Artificial Intelligence
PublisherAAAI Press, Palo Alto, CA, USA
ISSN (Print)2159-5399
ISSN (Electronic)2374-3468


ConferenceAAAI Conference on Artificial Intelligence
Abbreviated titleAAAI
Country/TerritoryUnited States
CityNew York
Internet address


Dive into the research topics of 'Error-Correcting and Verifiable Parallel Inference in Graphical Models'. Together they form a unique fingerprint.

Cite this