Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
Revisiting Causal Discovery from a Complexity-Theoretic Perspective
Authors: Robert Ganian, Viktoriia Korchemna, Stefan Szeider
IJCAI 2024 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | This paper investigates the complex relationship between the graph structure and the efficiency of constraint-based causal discovery algorithms. Our main contributions include (i) a near-tight characterization of which causal graphs admit a small d-separating set for each pair of vertices and thus can potentially be efficiently recovered by a constraintbased causal discovery algorithm, (ii) the explicit construction of a sequence of causal graphs on which the influential PC algorithm might need exponential time, although there is a small d-separating set between every pair of variables, and (iii) the formulation of a new causal discovery algorithm which achieves fixed-parameter running time by considering the maximum number of edge-disjoint paths between variables in the (undirected) super-structure as the parameter. A distinguishing feature of our investigation is that it is carried out within a more fine-grained model which more faithfully captures the infeasibility of performing accurate independence tests for large sets of conditioning variables. |
| Researcher Affiliation | Academia | Robert Ganian , Viktoriia Korchemna , Stefan Szeider Algorithms and Complexity Group, TU Wien, Vienna, Austria EMAIL |
| Pseudocode | Yes | The PC algorithm... This phase consists of the following sequence of procedures [Glymour et al., 2019]: 1. Construct a complete undirected graph over the provided set of variables. 2. Eliminate edges between variables that are either unconditionally independent or are known to be independent due to expert knowledge (non-adjacent in the super-structure). 3. For each pair of variables {X, Y } having an edge between them, and for each variable Z with an edge connected to either of them, eliminate the edge between X and Y if X is conditionally independent of Y given Z. 4. For each pair of variables {X, Y } having an edge between them, and for each pair of variables {Z, W} with edges both connected to X or both connected to Y , eliminate the edge between X and Y if X Y | {Z, W}. 5. Continue checking independencies conditional on subsets of variables of size 3, . . . , i until there are no more adjacent pairs X, Y , such that there is a subset of variables of size i such that all of the variables in the subset are adjacent to X or all adjacent to Y . |
| Open Source Code | No | The paper does not provide any link or explicit statement about the availability of source code for the methodology described. |
| Open Datasets | No | This is a theoretical paper focusing on complexity analysis and algorithm design, not empirical evaluation on datasets. Therefore, no public dataset access information is provided. |
| Dataset Splits | No | This is a theoretical paper and does not involve empirical experiments with dataset splits for training, validation, or testing. |
| Hardware Specification | No | This is a theoretical paper focusing on algorithm design and complexity analysis. It does not describe any empirical experiments or the hardware used to run them. |
| Software Dependencies | No | This is a theoretical paper and does not describe empirical experiments or specific software dependencies with version numbers for reproducibility. |
| Experiment Setup | No | This is a theoretical paper and does not provide details on an experimental setup, hyperparameters, or training configurations. |