Structural-equations models (SEMs) are perhaps the most commonly used framework for modeling causality, but they do not capture all domains of interest. For example, dynamical systems that evolve in continuous time are an important class of domains that are not (naturally) captured by SEMs. A wide variety of approaches have been proposed to fill the gap, including dynamical structural causal models (Bongers, Blom and Mooij 2018), causal constraints models (Blom, Bongers and Mooij 2019), and counterfactual resimulation (Laurent, Yang, and Fontana 2018). These models complement common-sense causal interpretations of specific dynamical systems, such as systems of ODEs. All these approaches look quite different from each other and from SEMs. They are hard to compare, and concepts developed for one approach may not make sense for another. But they are capturing the same notion of causality as SEMs do, in the sense that interventions map to outcomes. We propose a class of models that are, in a certain natural sense, the most expressive generalization of SEMs. Our generalized SEMs (GSEMs) can be viewed as a unifying framework that recovers structural dynamical causal models, causal constraints models, counterfactual resimulation, and common-sense causal interpretations of systems of ODEs and hybrid automata (Alur et al. 1992) as special cases. The input-output behavior, or “interface”, of GSEMs is exactly that of SEMs, which means that definitions of concepts like actual cause, responsibility, blame, and explanation, can be immediately lifted from SEMs to GSEMs. The generality of GSEMs also makes them ideally suited to studying causality in the abstract; for example, they have been used to establish independence relationships among Halpern’s axioms for SEMs (Peters and Halpern 2022).

We define what it means for a joint probability distribution to be compatible with aset of independent causal mechanisms, at a qualitative level—or, more precisely with a directed hypergraph $\mathcal A$, which is the qualitative structure of a probabilistic dependency graph (PDG). When A represents a qualitative Bayesian network, QIM-compatibility with $\mathcal A$ reduces to satisfying the appropriate conditional independencies. But giving semantics to hypergraphs using QIM-compatibility lets us do much more. For one thing, we can capture functional dependencies. For another, we can capture important aspects of causality using compatibility: we can use compatibility to understand cyclic causal graphs, and to demonstrate structural compatibility, we must essentially produce a causal model. Finally, compatibility has deep connections to information theory. Applying compatibility to cyclic structures helps to clarify a longstanding conceptual issue in information theory.

We study the complexity of lattice problems in a world where algorithms, reductions, and protocols can run in superpolynomial time. Specifically, we revisit four foundational results in this context—two protocols and two worst-case to average-case reductions. We show how to improve the approximation factor in each result by a factor of roughly √n/logn when running the protocol or reduction in 2є n time instead of polynomial time, and we show a novel protocol with no polynomial-time analog. Our results are as follows.

Generalized structural equations models (GSEMs) (Peters and Halpern 2021), are, as the name suggests, a generalization of structural equations models (SEMs). They can deal with (among other things) infinitely many variables with infinite ranges, which is critical for capturing dynamical systems. We provide a sound and complete axiomatization of causal reasoning in GSEMs that is an extension of the sound and complete axiomatization provided by Halpern (2000) for SEMs. Considering GSEMs helps clarify what properties Halpern's axioms capture.