4 papers
Linear-Time Exact Computation of Influence Spread on Bounded-Pathwidth Graphs
Kengo Nakamura, Masaaki Nishino
Given a network and a set of vertices called seeds to initially inject information, influence spread is the expected number of vertices that eventually receive the information unde…
Variance Computation for Weighted Model Counting with Knowledge Compilation Approach
Kengo Nakamura, Masaaki Nishino, Norihito Yasuda
One of the most important queries in knowledge compilation is weighted model counting (WMC), which has been applied to probabilistic inference on various models, such as Bayesian n…
Tensor Decomposition Meets Knowledge Compilation: A Study Comparing Tensor Trains with OBDDs
Ryoma Onaka, Kengo Nakamura, Masaaki Nishino +1
A knowledge compilation map analyzes tractable operations in Boolean function representations and compares their succinctness. This enables the selection of appropriate representat…
Single Family Algebra Operation on BDDs and ZDDs Leads To Exponential Blow-Up
Kengo Nakamura, Masaaki Nishino, Shuhei Denzumi
Binary decision diagram (BDD) and zero-suppressed binary decision diagram (ZDD) are data structures to represent a family of (sub)sets compactly, and it can be used as succinct ind…