On the Number of Conditional Independence Tests in Constraint-based Causal Discovery

ArXi:2603.21844v1 Announce Type: cross Learning causal relations from observational data is a fundamental problem with wide-ranging applications across many fields. Constraint-based methods infer the underlying causal structure by performing conditional independence tests. However, existing algorithms such as the prominent PC algorithm need to perform a large number of independence tests, which in the worst case is exponential in the maximum degree of the causal graph.