Export
Research Overview
David B. Smith focuses on probabilistic inference, statistical relational models, and computational complexity in graphical models. His trajectory spans the development of hybrid inference rules for junction trees to bounding the cost of search-based lifted inference algorithms. The most recent work in the evidence addresses the computation of order statistics and approximation algorithms for probabilistic graphical models.
Research Trajectory
Smith’s documented research trajectory begins with foundational work in probabilistic inference, specifically examining the mathematical rules that govern probability calculations in complex models. In 2013, as first author, he investigated alternatives to the widely used sum rule for probabilistic inference. This research culminated in The Inclusion-Exclusion Rule and its Application to the Junction Tree Algorithm. Recognizing that the inclusion-exclusion rule requires access to marginal rather than joint probability values, Smith developed a novel representation of joint distributions to accommodate this approach. Furthermore, this work introduced the inclusion-exclusion-sum (IES) rule—a hybrid method designed to combine the strengths of both traditional rules—and applied it to junction trees to optimize inference tasks.
By 2015, Smith’s focus expanded to statistical relational models (SRMs) and the specific challenges of lifted inference. Lifted inference algorithms aim to reduce computational complexity by exploiting symmetries within relational representations, often using systematic search or importance sampling. However, these algorithms traditionally relied on inference-blind representations of the search space, making it difficult to estimate computational costs in advance. In Bounding the Cost of Search-Based Lifted Inference, Smith led the development of a principled approach to efficiently pre-compute tight upper bounds on the exact cost of inference before running the algorithms to completion, thereby improving the predictability and efficiency of search-based methods.
Continuing his focus on the algorithmic and computational limits of graphical models, Smith’s subsequent work addressed the extraction of specific statistical rankings from probabilistic frameworks. In 2017, he was the lead author on Order Statistics for Probabilistic Graphical Models. This research formalized the problem of computing r-th order statistics—finding an assignment that holds a specific rank r within a model. Smith and his co-authors demonstrated that this problem is NP-hard even in highly restricted scenarios, such as zero-treewidth models with no edges, via a reduction from the partition problem. To navigate this complexity, the research introduced a pseudo-polynomial time approximation algorithm for zero-treewidth models and successfully generalized it to arbitrary graphical models using tree decompositions.
Current Directions
The most recent paper in the evidence is from 2017, indicating a focus on the intersection of computational complexity and approximate reasoning in probabilistic graphical models. Based on this latest work, Smith’s research directions emphasize understanding the theoretical hardness of extracting ranked assignments (order statistics) from complex distributions. Rather than relying solely on exact inference, these recent efforts investigate pseudo-polynomial time approximation algorithms and structural generalizations, such as tree decompositions, to make otherwise intractable probabilistic queries computationally feasible.
Profile updated
Loading new papers…
Other researchers whose papers cluster into the same research directions — a proxy for overlapping technical interests and shared intellectual neighborhoods.
See something wrong? Report a mistake