Abstract AlphaZero-style reinforcement learning (RL) algorithms have achieved superhuman performance in many complex board games such as Chess, Shogi, and Go. However, we showcase that these algorithms encounter significant and fundamental challenges when applied to impartial games, a class where players share game pieces and optimal strategy often relies on abstract mathematical principles. Specifically, we utilise the game of Nim as a concrete and illustrative case study to reveal critical limitations of AlphaZero-style and similar self-play RL algorithms. We introduce a novel conceptual framework distinguishing between champion and expert mastery to evaluate RL agent performance. Our findings reveal that while AlphaZero-style agents can achieve champion-level play on very small Nim boards, their learning progression severely degrades as the board size increases. This difficulty stems not merely from complex data distributions or noisy labels, but from a deeper representational bottleneck: the inherent struggle of generic neural networks to implicitly learn abstract, non-associative functions like parity, which are crucial for optimal play in impartial games. This limitation causes a critical breakdown in the positive feedback loop essential for self-play RL, preventing effective learning beyond rote memorisation of frequently observed states. These results align with broader concerns regarding AlphaZero-style algorithms’ vulnerability to adversarial attacks, highlighting their inability to truly master all legal game states. Our work underscores that simple hyperparameter adjustments are insufficient to overcome these challenges, establishing a crucial foundation for the development of fundamentally novel algorithmic approaches, potentially involving neuro-symbolic or meta-learning paradigms, to bridge the gap towards true expert-level AI in combinatorial games.

In this paper, we study Condorcet domains, sets of linear orders from which majority ranking produces a linear order. We introduce a new class of Condorcet domains, called coherent domains, which is natural from both a voting theoretic and combinatorial perspective. After studying the properties of these domains we introduce set-alternating schemes. This is a method for constructing well-behaved coherent domains. Using this we show that, for sufficiently large numbers of alternatives n , there are coherent domains of size more than 2 . 197 3 n . This improves the best existing asymptotic lower bounds for the size of the largest general Condorcet domains.

Guessing games for directed graphs were introduced by Riis for studying multiple unicast network coding problems. In a guessing game, the players toss generalised dice and can see some of the other outcomes depending on the structure of an underlying digraph. They later guess simultaneously the outcome of their own die. Their objective is to find a strategy, which maximizes the probability that they all guess correctly. The performance of the optimal strategy for a graph is measured by the guessing number of the digraph. Christofides and Markström studied guessing numbers of undirected graphs and defined a strategy which they conjectured to be optimal. One of the main results of this paper is a disproof of this conjecture. The main tool so far for computing guessing numbers of graphs is information theoretic inequalities. The other main result of this paper is that Shannon's information inequalities, which work particularly well for a wide range of graph classes, are not sufficient for computing the guessing number. Finally, we pose a few more interesting questions some of which we can answer and some which we leave as open problems.

In this paper, we are interested in the number of fixed points of functions $f:A^n\to A^n$ over a finite alphabet $A$ defined on a given signed digraph $D$. We first use techniques from network coding to derive some lower bounds on the number of fixed points that only depends on $D$. We then discover relationships between the number of fixed points of $f$ and problems in coding theory, especially the design of codes for the asymmetric channel. Using these relationships, we derive upper and lower bounds on the number of fixed points, which significantly improve those given in the literature. We also unveil some interesting behavior of the number of fixed points of functions with a given signed digraph when the alphabet varies. We finally prove that signed digraphs with more (disjoint) positive cycles actually do not necessarily have functions with more fixed points.

A symbolic approach to communication networks, where the topology of the underlying network is contained in a set of formal terms, was recently introduced. Many communication problems can be recast as dispersion problems in this setup. The so-called min-cut of a term set represents its number of degrees of freedom. For any assignment of function symbols, its dispersion measures the amount of information sent to the destinations. It was proved that the maximum dispersion asymptotically reaches the min-cut of the term set. In this paper, we refine this result in two ways. First, we prove a max-flow min-cut theorem for the Rényi entropy with order less than one, given that the inputs are equiprobably distributed; conversely, there is no max-flow min-cut theorem for Rényi entropy with order greater than one. Second, although linear coding functions have the practical appeal of low complexity, we prove that they are insufficient in general to reach the min-cut. More specifically, there exist term sets which have an arbitrarily large dispersion for non-linear coding functions, yet limited dispersion when linear coding functions are considered. Conversely, we show that if there is a solution based on low degree polynomials, then there exists a linear solution.

Traditionally, communication networks are modeled and analyzed in terms of information flows in graphs. In this paper, we introduce a new symbolic approach to communication networks, where the topology of the underlying network is contained in a set of formal terms. To any choice of coding functions we associate a measure of performance, referred to as the dispersion. Many communication problems can be recast as dispersion problems in this setup. We state and prove variants of a theorem concerning dispersion of information in communication networks which generalizes the network coding theorem. The dispersion theorem resembles the max-flow min-cut theorem for commodity networks and states that the minimal cut value can be asymptotically achieved by the use of coding functions based on a routing scheme that uses dynamic headers.

The guessing number of a directed graph (digraph), equivalent to the entropy of that digraph, was introduced as a direct criterion on the solvability of a network coding instance. This paper makes two contributions on the guessing number. First, we introduce an undirected graph on all possible configurations of the digraph, referred to as the guessing graph, which encapsulates the essence of dependence amongst configurations. We prove that the guessing number of a digraph is equal to the logarithm of the independence number of its guessing graph. Therefore, network coding solvability is no more a problem on the operations made by each node, but is simplified into a problem on the messages that can transit through the network. By studying the guessing graph of a given digraph, and how to combine digraphs or alphabets, we are thus able to derive bounds on the guessing number of digraphs. Second, we construct specific digraphs with high guessing numbers, yielding network coding instances where a large amount of information can transit. We first propose a construction of digraphs with finite parameters based on cyclic codes, with guessing number equal to the degree of the generator polynomial. We then construct an infinite class of digraphs with arbitrary girth for which the ratio between the linear guessing number and the number of vertices tends to one, despite these digraphs being arbitrarily sparse. These constructions yield solvable network coding instances with a relatively small number of intermediate nodes for which the node operations are known and linear, although these instances are sparse and the sources are arbitrarily far from their corresponding sinks.

We show that the asymptotic complexity of uniformly generated (expressible in First-Order (FO) logic) propositional tautologies for the Nullstellensatz proof system (NS) as well as for Polynomial Calculus, (PC) has four distinct types of asymptotic behavior over fields of finite characteristic. More precisely, based on some highly non-trivial work by Krajicek, we show that for each prime p there exists a function l(n) \in \Omega(\log(n)) for NS and l(n) \in \Omega(\log(\log(n)) for PC, such that the propositional translation of any FO formula (that fails in all finite models), has degree proof complexity over fields of characteristic p, that behave in 4 mutually distinct ways:(i) The degree complexity is bound by a constant.(ii) The degree complexity is at least l(n) for all values of n.(iii) The degree complexity is at least l(n) except in a finite number of regular subsequences of inifinite size, where the degree is constant.(iv) The degree complexity fluctuates in a very particular way with the degree complexity taking different constant values on an infinite number of regular subsequences each of infinite size.We leave it as an open question whether the classification remains valid for l(n) \in n^\Omega(1) or even for l(n) \in \Omega(n). Finally, we show that for any non-empty proper subset A \subseteq \(i), (ii), (iii), (iv)\ the decision problem of whether a given input FO formula \psi has type belonging to A - is undecidable.

It is shown that there exist information networks where messages can be sent (utilizing network coding) more easily in one direction than in the opposite direction. This is valid even though each channel is assumed to have the same capacity in both directions. It is shown that irreversible information networks only have solutions that use nonlinear network coding. This correspondence argues that this result is more surprising than it might appear at first sight and that it follows using ideas resembling the path integral in quantum mechanics.

We prove that any optimal tree resolution proof of PHP/sub n//sup m/ is of size 2/sup /spl theta/(n log n)/, independently from m, even if it is infinity. So far, only a 2/sup /spl Omega/(n)/ lower bound has been known in the general case. We also show that any, not necessarily optimal, regular tree resolution proof PHP/sub n//sup m/ is bounded by 2/sup O(n log m)/. To the best of our knowledge, this is the first time the worst case proof complexity has been considered. Finally, we discuss possible connections of our result to Riis' (1999) complexity gap theorem for tree resolution.

We prove exponential lower bounds on the resolution proofs of some tautologies, based on rectangular grid graphs. More specifically, we show a 2/sup /spl Omega/(n)/ lower bound for any resolution proof of the mutilated chessboard problem on a 2n/spl times/2n chessboard as well as for the Tseitin tautology (G. Tseitin, 1968) based on the n/spl times/n rectangular grid graph. The former result answers a 35 year old conjecture by J. McCarthy (1964).

This paper describes an improved input coding method for a text-to-phoneme (TTP) neural network model for speaker independent speech recognition systems. The code-book is self-organizing and is jointly optimized with the TTP model ensuring that the coding is optimal in terms of overall performance. The code-book is based on a set of single layer neural networks with shared weights. Experiments show that performance is increased com-pared to the NETTalk and NETSpeak models. 1.

In this paper we consider solutions to the static dictionary problem on AC/sup 0/ RAMs, i.e. random access machines where the only restriction on the finite instruction set is that all computational instructions are in AC/sup 0/. Our main result is a tight upper and lower bound of /spl theta/(/spl radic/log n/log log n) on the time for answering membership queries in a set of size n when reasonable space is used for the data structure storing the set; the upper bound can be obtained using O(n) space, and the lower bound holds even if we allow space 2/sup polylog n/. Several variations of this result are also obtained. Among others, we show a tradeoff between time and circuit depth under the unit-cost assumption: any RAM instruction set which permits a linear space, constant query time solution to the static dictionary problem must have an instruction of depth /spl Omega/(log w/log log to), where w is the word size of the machine (and log the size of the universe). This matches the depth of multiplication and integer division, used in the perfect hashing scheme by M.L. Fredman, J. Komlos and E. Szemeredi (1984).