The Combinatorics of Causality

• URL: http://arxiv.org/abs/2206.08911v4
• Date: Thu, 27 Jul 2023 20:30:34 GMT
• Title: The Combinatorics of Causality
• Abstract summary: We introduce and explore the notion of "spaces of input histories" In the simplest case of binary inputs, the number of available "causally complete" spaces grows from 7 on 2 events, to 2644 on 3 events, to an unknown number on 4 events (likely around a billion) For perspective, previous literature on non-locality and contextuality used a single one of the 2644 available spaces on 3 events, work on definite causality used 19 spaces, derived from partial orders, and work on indefinite causality used only 6 more, for a grand total of 25.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce and explore the notion of "spaces of input histories", a broad family of combinatorial objects which can be used to model input-dependent, dynamical causal order. We motivate our definition with reference to traditional partial order- and preorder-based notions of causal order, adopted by the majority of previous literature on the subject, and we proceed to explore the novel landscape of combinatorial complexity made available by our generalisation of those notions. In the process, we discover that the fine-grained structure of causality is significantly more complex than we might have previously believed: in the simplest case of binary inputs, the number of available "causally complete" spaces grows from 7 on 2 events, to 2644 on 3 events, to an unknown number on 4 events (likely around a billion). For perspective, previous literature on non-locality and contextuality used a single one of the 2644 available spaces on 3 events, work on definite causality used 19 spaces, derived from partial orders, and work on indefinite causality used only 6 more, for a grand total of 25. This paper is the first instalment in a trilogy: the sheaf-theoretic treatment of causal distributions is detailed in Part 2, "The Topology of Causality" [arXiv:2303.07148], while the polytopes formed by the associated empirical models are studied in Part 3, "The Geometry of Causality" [arXiv:2303.09017]. An exhaustive classification of the 2644 causally complete spaces on 3 events with binary inputs is provided in the supplementary work "Classification of causally complete spaces on 3 events with binary inputs", together with the algorithm used for the classification and partial results from the ongoing search on 4 events.

Related papers

• ComBench: A Benchmark for Rigorous Proof Reasoning and Constructive Realization in Olympiad-Level Combinatorics [95.15900681087088]
  We introduce ComBench, an Olympiad-level benchmark for diagnosing and the reasoning capabilities of large language models.<n>ComBench contains 100 human-annotated competition-level problems organized around two complementary settings.<n>Experiments show that the strongest model reaches 65.4% overall Avg. and 75.3% overall Best@4.
  arXiv  Detail & Related papers  (2026-06-09T06:50:15Z)
• KnowledgeBerg: Evaluating Systematic Knowledge Coverage and Compositional Reasoning in Large Language Models [8.584257473147568]
  Many real-world questions appear deceptively simple yet implicitly demand two capabilities.<n>We formalize this challenge through two dimensions: knowledge width, the cardinality of the required universe, and reasoning depth.<n>We introduce KnowledgeBerg, a benchmark of 4,800 multiple-choice questions from 1,183 enumeration seeds spanning 10 domains and 17 languages.
  arXiv  Detail & Related papers  (2026-04-19T21:18:42Z)
• Enhancing Spatial Reasoning in Multimodal Large Language Models through Reasoning-based Segmentation [50.81551581148339]
  We introduce Relevant Reasoning (R$2$S), a reasoning-based segmentation framework.<n>We also introduce 3D ReasonSeg, a reasoning-based segmentation dataset.<n>Both experiments demonstrate that the R$2$S and 3D ReasonSeg effectively endow 3D point cloud perception with stronger spatial reasoning capabilities.
  arXiv  Detail & Related papers  (2025-06-29T06:58:08Z)
• Local-Data-Hiding and Causal Inseparability: Probing Indefinite Causal Structures with Cryptographic Primitives [0.0]
  Recent studies suggest the possibility of indefiniteness in causal structure, which emerges as a novel information primitive. We show that agents embedded in an indefinite causal structure can outperform their counterparts operating in a definite causal background. We report an intriguing super-activation phenomenon, where two quantum processes, each individually not useful for the LBH task, become useful when used together.
  arXiv  Detail & Related papers  (2024-07-30T04:54:03Z)
• Hexagons govern three-qubit contextuality [0.06597195879147556]
  Split Cayley hexagons of order two are distinguished finite living in the three-qubit symplectic polar space. For each set of unsatisfiable contexts there exists some classically-embedded hexagon sharing with the configuration exactly this set of contexts and nothing else.
  arXiv  Detail & Related papers  (2023-12-12T21:10:42Z)
• The Computational Complexity of Concise Hypersphere Classification [49.57441416941195]
  This paper is the first complexity-theoretic study of the hypersphere classification problem for binary data. We use the fine-grained parameterized complexity paradigm to analyze the impact of structural properties that may be present in the input data.
  arXiv  Detail & Related papers  (2023-12-12T09:33:03Z)
• Regularization-Based Methods for Ordinal Quantification [49.606912965922504]
  We study the ordinal case, i.e., the case in which a total order is defined on the set of n>2 classes. We propose a novel class of regularized OQ algorithms, which outperforms existing algorithms in our experiments.
  arXiv  Detail & Related papers  (2023-10-13T16:04:06Z)
• A Measure-Theoretic Axiomatisation of Causality [55.6970314129444]
  We argue in favour of taking Kolmogorov's measure-theoretic axiomatisation of probability as the starting point towards an axiomatisation of causality. Our proposed framework is rigorously grounded in measure theory, but it also sheds light on long-standing limitations of existing frameworks.
  arXiv  Detail & Related papers  (2023-05-19T13:15:48Z)
• New and improved bounds on the contextuality degree of multi-qubit configurations [0.0699049312989311]
  We present algorithms and a C code to reveal quantum contextuality and evaluate the contextuality degree. The paper first describes the algorithms and the C code. Then it illustrates its power on a number of subspaces of symplectic polar spaces whose rank ranges from 2 to 7. The most interesting new results include: (i) non-contextuality of configurations whose contexts are subspaces of dimension 2 and higher, (ii) non-existence of negative subspaces of dimension 3 and higher.
  arXiv  Detail & Related papers  (2023-05-17T14:02:57Z)
• Classification of causally complete spaces on 3 events with binary inputs [0.0]
  We present an exhaustive classification of the 2644 causally complete spaces of input histories on 3 events with binary inputs. This paper forms the supplementary material for a trilogy of works: spaces of input histories, our dynamical generalisation of causal orders, and the sheaf-theoretic treatment of causal distributions.
  arXiv  Detail & Related papers  (2023-03-13T15:22:14Z)
• Compatibility of Cyclic Causal Structures with Spacetime in General Theories with Free Interventions [0.0]
  We show the possibility of operationally detectable causal loops embedded in (1+1)-Minkowski spacetime without superluminal signalling. We establish new properties of HO affects relations and apply them to infer causal structures. We study the embedding of information-theoretic causal structures into partially ordered spacetimes.
  arXiv  Detail & Related papers  (2022-11-07T14:30:03Z)
• Tripartite entanglement measure under local operations and classical communication [0.6759148939470331]
  We study the concurrence fill, which admits a geometric interpretation to measure genuine tripartite entanglement. Our results shed light on studying genuine entanglement and also reveal the complex structure of multipartite systems.
  arXiv  Detail & Related papers  (2022-10-13T03:39:20Z)
• Proofs of network quantum nonlocality aided by machine learning [68.8204255655161]
  We show that the family of quantum triangle distributions of [DOI40103/PhysRevLett.123.140] did not admit triangle-local models in a larger range than the original proof. We produce a large collection of network Bell inequalities for the triangle scenario with binary outcomes, which are of independent interest.
  arXiv  Detail & Related papers  (2022-03-30T18:00:00Z)
• Nested Counterfactual Identification from Arbitrary Surrogate Experiments [95.48089725859298]
  We study the identification of nested counterfactuals from an arbitrary combination of observations and experiments. Specifically, we prove the counterfactual unnesting theorem (CUT), which allows one to map arbitrary nested counterfactuals to unnested ones.
  arXiv  Detail & Related papers  (2021-07-07T12:51:04Z)
• Emergence of classical behavior in the early universe [68.8204255655161]
  Three notions are often assumed to be essentially equivalent, representing different facets of the same phenomenon. We analyze them in general Friedmann-Lemaitre- Robertson-Walker space-times through the lens of geometric structures on the classical phase space. The analysis shows that: (i) inflation does not play an essential role; classical behavior can emerge much more generally; (ii) the three notions are conceptually distinct; classicality can emerge in one sense but not in another.
  arXiv  Detail & Related papers  (2020-04-22T16:38:25Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.