Decision problems in information theory

DOI10.4230/LIPICS.ICALP.2020.106MaRDI QIDQ6842464zbMATH OpenFDO

Authors Mahmoud Abo Khamis, Phokion G. Kolaitis, Hung Q. Ngo, Dan Suciu

Publication date 18 March 2026

Copyright license Creative Commons Attribution 3.0 Unported

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2020.106

zbMATH Keywords

arithmetical hierarchydecision problemsentropic functionsinformation theory

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• A class of non-Shannon-type information inequalities and their applications
• A new class of non-Shannon-type inequalities for entropies
• A non-Shannon-type conditional inequality of information quantities
• Balanced information inequalities
• Coding and cryptology. Third international workshop, IWCC 2011, Qingdao, China, May 30 -- June 3, 2011. Proceedings
• Conditional Information Inequalities for Entropic and Almost Entropic Points
• How to share a secret
• scientific article; zbMATH DE number 67424 (Why is no real title available?)
• scientific article; zbMATH DE number 176109 (Why is no real title available?)
• scientific article; zbMATH DE number 1157649 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• Inequalities for Shannon entropy and Kolmogorov complexity
• Information theory and network coding
• Logical and algorithmic properties of conditional independence and graphical models
• Logical and algorithmic properties of stable conditional independence
• Model theory and exponentiation.
• On a new non-Shannon type information inequality
• On a relation between information inequalities and group theory
• On characterization of entropy function via information inequalities
• On secret sharing schemes
• On secret sharing systems
• On the completeness of the semigraphoid axioms for deriving arbitrary from saturated conditional independence statements
• On the conditional independence implication problem: a lattice-theoretic approach
• On the number of copies of one hypergraph in another
• On the number of subgraphs of prescribed type of graphs with a given number of edges
• On the size of shares for secret sharing schemes
• PROBABILISTIC CONDITIONAL INDEPENDENCE STRUCTURES AND MATROID THEORY: BACKGROUND¹
• Size and treewidth bounds for conjunctive queries
• Size bounds and query plans for relational joins
• Some intersection theorems for ordered sets and graphs
• The homomorphism domination exponent
• The polynomial-time hierarchy
• The size of a share must be large

Cited in

(4)

• Conditional independence on semiring relations
• Information inequality problem over set functions
• On the complexity of the conditional independence implication problem with bounded cardinalities
• On entropic and almost multilinear representability of matroids

This page was built for publication: Decision problems in information theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6842464)