LIPIcs.MFCS.2024.73.pdf
- Filesize: 0.74 MB
- 16 pages
Document
On the Complexity of the Conditional Independence Implication Problem with Bounded Cardinalities
Author
Michał Makowski 
-
Part of:
Volume:
49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Mathematical Foundations of Computer Science (MFCS) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2024-08-23
File
Document Identifiers
Author Details
Acknowledgements
The author would like to thank Damian Niwiński for his guidance and the anonymous reviewers for their valuable comments.
Cite AsGet BibTex
Michał Makowski. On the Complexity of the Conditional Independence Implication Problem with Bounded Cardinalities. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 73:1-73:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
https://doi.org/10.4230/LIPIcs.MFCS.2024.73
https://doi.org/10.4230/LIPIcs.MFCS.2024.73
Abstract
We show that the conditional independence (CI) implication problem with bounded cardinalities, which asks whether a given CI implication holds for all discrete random variables with given cardinalities, is co-NEXPTIME-hard. The problem remains co-NEXPTIME-hard if all variables are binary. The reduction goes from a variant of the tiling problem and is based on a prior construction used by Cheuk Ting Li to show the undecidability of a related problem where the cardinality of some variables remains unbounded. The CI implication problem with bounded cardinalities is known to be in EXPSPACE, as its negation can be stated as an existential first-order logic formula over the reals of size exponential with regard to the size of the input.
Subject Classification
ACM Subject Classification
- Mathematics of computing → Information theory
- Theory of computation → Problems, reductions and completeness
Keywords
- Conditional independence implication
- exponential time
- tiling problem
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- John F. Canny. Some algebraic and geometric computations in PSPACE. In Janos Simon, editor, Proceedings of the 20th Annual ACM Symposium on Theory of Computing, May 2-4, 1988, Chicago, Illinois, USA, pages 460-467. ACM, 1988. URL: https://doi.org/10.1145/62212.62257.
-
Dan Geiger and Judea Pearl. Logical and algorithmic properties of conditional independence and graphical models. The Annals of Statistics, 21(4):2001-2021, 1993.
- Daniel Gottesman and Sandy Irani. The quantum and classical complexity of translationally invariant tiling and hamiltonian problems. Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, May 2009. URL: https://doi.org/10.1109/FOCS.2009.22.
- Miika Hannula, Åsa Hirvonen, Juha Kontinen, Vadim Kulikov, and Jonni Virtema. Facets of distribution identities in probabilistic team semantics. In Francesco Calimeri, Nicola Leone, and Marco Manna, editors, Logics in Artificial Intelligence - 16th European Conference, JELIA 2019, Rende, Italy, May 7-11, 2019, Proceedings, volume 11468 of Lecture Notes in Computer Science, pages 304-320. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-19570-0_20.
- Mahmoud Abo Khamis, Phokion G. Kolaitis, Hung Q. Ngo, and Dan Suciu. Decision problems in information theory. In Artur Czumaj, Anuj Dawar, and Emanuela Merelli, editors, 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference), volume 168 of LIPIcs, pages 106:1-106:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.ICALP.2020.106.
- Lukas Kühne and Geva Yashfe. On entropic and almost multilinear representability of matroids. CoRR, abs/2206.03465, 2022. URL: https://arxiv.org/abs/2206.03465.
-
Harry R. Lewis and Christos H. Papadimitriou. Elements of the theory of computation, 2nd Edition. Prentice Hall, 1998.
- Cheuk Ting Li. The undecidability of conditional affine information inequalities and conditional independence implication with a binary constraint. IEEE Transactions on Information Theory, 68(12):7685-7701, 2022. URL: https://doi.org/10.1109/TIT.2022.3190800.
- Cheuk Ting Li. Undecidability of network coding, conditional information inequalities, and conditional independence implication. IEEE Transactions on Information Theory, 2023. URL: https://doi.org/10.1109/TIT.2023.3247570.
- Michał Makowski. On the complexity of the conditional independence implication problem with bounded cardinalities, 2024. Full version of this paper. URL: https://arxiv.org/abs/2408.02550.
- Paul W. K. Rothemund and Erik Winfree. The program-size complexity of self-assembled squares (extended abstract). In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, STOC '00, pages 459-468, New York, NY, USA, 2000. Association for Computing Machinery. URL: https://doi.org/10.1145/335305.335358.
-
Peter van Emde Boas. The convenience of tilings. In A. Sorbi, editor, Complexity, Logic, and recursion Theory, volume 187 of Lecture Notes in Pure and Applied Logic, pages 331-363. Marcel Dekker, Inc., 1997.
- Z. Zhang and R.W. Yeung. A non-Shannon-type conditional inequality of information quantities. IEEE Transactions on Information Theory, 43(6):1982-1986, 1997. URL: https://doi.org/10.1109/18.641561.