5 papers
Term Coding and Dispersion: Exact and Asymptotic Decision Problems
Søren Riis
Let t be a tuple of r terms that, under an interpretation on an n-element alphabet A, defines a map from k-tuples over A to r-tuples over A. We study the decision theory of its max…
Coin flipping and waiting times paradoxes: Why fair coins are exceptional
Søren Riis, Mike Paterson
Penney's Ante exhibits non-transitivity when two target strings race to appear in a shared stream of coin tosses. We study instead independent string races, where each player obser…
Term Coding: An Entropic Framework for Extremal Combinatorics and the Guessing--Number Sandwich Theorem
Søren Riis
Classical existence problems in extremal combinatorics ask whether finite operations can satisfy prescribed identities universally. Term Coding replaces this yes-or-no question by…
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…
Overcoming a Learning Bottleneck in Impartial Games: A Circuit Complexity Approach
Søren Riis
Why can neural networks struggle to learn optimal play in a game with a simple, efficient solution algorithm? Motivated by empirical difficulties with parity in impartial games, we…