One Unit Separates Polynomial Time from Undecidability in Term Coding

Søren Riis

Term coding provides a common algebraic framework for network coding, index coding and problems in extremal combinatorics. We exhibit a decision problem in which lowering an output…