Error-Correcting and Verifiable Parallel Inference in Graphical Models


  • Negin Karimi Aalto University
  • Petteri Kaski Aalto University
  • Mikko Koivisto University of Helsinki



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.




How to Cite

Karimi, N., Kaski, P., & Koivisto, M. (2020). Error-Correcting and Verifiable Parallel Inference in Graphical Models. Proceedings of the AAAI Conference on Artificial Intelligence, 34(06), 10194-10201.



AAAI Technical Track: Reasoning under Uncertainty