Graphical Models Meet Heuristic Search: A Personal Journey into Automated Reasoning

Abstract: A natural intuition in AI is that smart agents should tackle hard problems by building on solutions to easier ones. This idea has inspired what's known as the tractable islands paradigm: focus on parts of a problem that are computationally manageable and use them as stepping stones toward solving the whole.

In this talk, I’ll focus on probabilistic reasoning with graphical models and give an overview of algorithms that follow this approach. I’ll introduce the Bucket Elimination, Mini-Bucket Elimination, and AND/OR search frameworks, and explain how they navigate the tradeoff between time and memory. I’ll then show how heuristics grounded in tractable islands can guide both heuristic search and Monte Carlo sampling, leading to anytime algorithms —solvers that provide increasingly accurate approximations over time, with guaranteed bounds, and converge to exact solutions if given enough time.

Bio: Rina Dechter is a Distinguished Professor of Computer Science at the University of California, Irvine. She holds a Ph.D. in computer science from UCLA (1985), an M.S. in applied mathematics from the Weizmann Institute (1975), and a B.S. in mathematics and statistics from the Hebrew University in Jerusalem (1973). Dechter’s research centers on computational aspects of automated reasoning and knowledge representation including search, constraint processing and probabilistic reasoning. She is the author of Constraint Processing published by Morgan Kaufmann (2003), and of Reasoning with Probabilistic and Deterministic Graphical Models: Exact Algorithms published by Morgan and Claypool Publishers (2013, second ed. 2019). She co-edited (with Hector Geffner and Joe Halpern) the ACM book Probabilistic and Causal Inference: The Works of Judea Pearl (2022).

She has authored and co-authored close to 200 research papers. Dechter was awarded the Presidential Young investigator award in 1991, is a Fellow of AAAI (1994) and of ACM (2013) and was a Radcliffe Fellow during 2005–2006. She received the Association of Constraint Programming (ACP) Research Excellence Award (2007). She is a Fellow of the American Association of the Advancement of Science (AAAS, 2022), has been elected as a member of the American Academy of Arts and Sciences in 2025, and is the winner of the IJCAI Research Excellence Award in 2025. She served as a co‐Editor‐in‐Chief of Artificial Intelligence from 2011 to 2018. She also served as a program chair or co-chair of several AI conferences (CP-2000, AAAI-2002, UAI-2006) and was the conference chair of IJCAI‐2022.