DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2024.73

On the Complexity of the Conditional Independence Implication Problem with Bounded Cardinalities

Authors: Michał Makowski

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

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.

Cite as

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)

Copy BibTex To Clipboard

@InProceedings{makowski:LIPIcs.MFCS.2024.73,
  author =	{Makowski, Micha{\l}},
  title =	{{On the Complexity of the Conditional Independence Implication Problem with Bounded Cardinalities}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{73:1--73:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.73},
  URN =		{urn:nbn:de:0030-drops-206291},
  doi =		{10.4230/LIPIcs.MFCS.2024.73},
  annote =	{Keywords: Conditional independence implication, exponential time, tiling problem}
}

Search Results

Documents authored by Makowski, Michał

On the Complexity of the Conditional Independence Implication Problem with Bounded Cardinalities

Abstract

Cite as

Thanks for your feedback!

Could not send message