5 papers
Learning Bayesian and Markov Networks with an Unreliable Oracle
Juha Harviainen, Pekka Parviainen, Vidya Sagar Sharma
We study constraint-based structure learning of Markov networks and Bayesian networks in the presence of an unreliable conditional independence oracle that makes at most a bounded…
Faster Fixed Parameter Tractable Algorithms for Counting Markov Equivalence Classes with Special Skeletons
Vidya Sagar Sharma
The structure of Markov equivalence classes (MECs) of causal DAGs has been studied extensively. A natural question in this regard is to algorithmically find the number of MECs with…
A Fixed-Parameter Tractable Algorithm for Counting Markov Equivalence Classes with the same Skeleton
Vidya Sagar Sharma
Causal DAGs (also known as Bayesian networks) are a popular tool for encoding conditional dependencies between random variables. In a causal DAG, the random variables are modeled a…
Counting Markov Equivalent Directed Acyclic Graphs Consistent with Background Knowledge
Vidya Sagar Sharma
A polynomial-time exact algorithm for counting the number of directed acyclic graphs in a Markov equivalence class was recently given by Wienöbst, Bannach, and Liśkiewicz (AAAI 202…
The PSPACE-hardness of understanding neural circuits
Vidya Sagar Sharma, Piyush Srivastava
In neuroscience, an important aspect of understanding the function of a neural circuit is to determine which, if any, of the neurons in the circuit are vital for the biological beh…