Research
Mathematical Logic, Complexity Theory, Proof Complexity, Algebraic Proof Complexity, Information Theory, Network Coding
Publications
Publications of specific relevance to the Centre for Multimodal AI
2026
Overcoming a Learning Bottleneck in Impartial Games: A Circuit Complexity ApproachRiis S
In
Arxiv 11-10-2026 Coin flipping and waiting times paradoxes: Why fair coins are exceptionalRiis S Paterson M
In
Arxiv 05-10-2026 One Unit Separates Polynomial Time from Undecidability in Term CodingRiis SR
In
Arxiv 12-09-2026 Term Coding and Dispersion: Exact and Asymptotic Decision ProblemsRiis S
In
Arxiv 01-09-2026 Term Coding: An Entropic Framework for Extremal Combinatorics and the Guessing--Number Sandwich TheoremRiis S
In
Arxiv 30-08-2026 Humanity's Last ExamPhan L Gatti A Han Z Li N Hu J Zhang H Zhang CBC Shaaban M et al.
28-07-2026 Drift and selection in LLM text ecosystemsRiis S
In
Arxiv 15-03-2026 Term Coding and Dispersion: A Perfect-vs-Rate Complexity Dichotomy for Information Flow.Riis S
Corr vol. abs/2602.08110
01-02-2026 A benchmark of expert-level academic questions to assess AI capabilitiesPhan L Gatti A Li N Khoja A Kim R Ren R Hausenloy J Zhang O et al.
Nature,
Springer Nature vol. 649 (8099), 1139-1146.
28-01-2026 Impartial Games: A Challenge for Reinforcement LearningZhou B Riis SR
21-01-2026 Improved lower bounds for the maximum size of Condorcet domainsKarpov A Markstrom K Riis S Zhou B
In
Arxiv 12-01-2026 Term Coding: An Entropic Framework for Extremal Combinatorics and the Guessing-Number Sandwich Theorem.Riis S
Corr vol. abs/2601.16614
01-01-2026 Improved lower bounds for the maximum size of Condorcet domains.Karpov A Markström K Riis S Zhou B
Corr vol. abs/2601.07336
01-01-2026 2025
Coherent domains and improved lower bounds for the maximum size of Condorcet domainsKarpov A Markström K Riis S
Discrete Applied Mathematics,
Elsevier vol. 370, 57-70.
01-07-2025An efficient heuristic search algorithm for discovering large Condorcet domainsZhou B
4or,
Springer Nature vol. 23 (2), 193-216.
24-01-2025 Condorcet domains on at most seven alternativesAkello-Egwel D Leedham-Green C Litterick A Riis S
Mathematical Social Sciences,
Elsevier vol. 133, 23-33.
01-01-2025 Humanity's Last Exam.Phan L Gatti A Han Z Li N Hu J Zhang H Shi S Choi M et al.
Corr vol. abs/2501.14249
01-01-2025 2024
CDL: A fast and flexible library for the study of permutation sets with structural restrictionsZhou B Markström K
Softwarex,
Elsevier vol. 28
01-12-2024 A heuristic search algorithm for discovering large Condorcet domainsZhou B Riis S
In
Arxiv 26-04-2024 Bipartite peak-pit domainsKarpov A Markström K Riis S Zhou B
In
Arxiv 26-01-2024 Arrow's single peaked domains, richness, and domains for plurality and the Borda countMarkström K Riis S Zhou B
In
Arxiv 23-01-2024 Local Diversity of Condorcet DomainsKarpov A Markström K Riis S Zhou B
In
Arxiv 22-01-2024 Exploring Parity Challenges in Reinforcement Learning through Curriculum Learning with Noisy LabelsZhou B Riis S
In
Arxiv 14-01-2024 Mastering NIM and Impartial Games with Weak Neural Networks: An AlphaZero-inspired Multi-Frame Approach.Riis S
Corr vol. abs/2411.06403
01-01-2024 Arrow's single peaked domains, richness, and domains for plurality and the Borda count.Markström K Riis S
Corr vol. abs/2401.12547
01-01-2024 Local Diversity of Condorcet Domains.Karpov A Markström K
Corr vol. abs/2401.11912
01-01-2024 2023
Condorcet Domains of Degree at most SevenAkello-Egwell D Leedham-Green C Litterick A Markström K Riis S
In
Arxiv 12-12-2023 The largest Condorcet domain on 8 alternativesLeedham-Green C Markström K
Social Choice and Welfare,
Springer Nature vol. 62 (1), 109-116.
05-09-2023 The Largest Condorcet Domains on 8 AlternativesLeedham-Green C Markström K Riis S
In
Arxiv 03-07-2023 New Record-Breaking Condorcet Domains on 10 and 11 Alternatives.Zhou B Riis S
Corr vol. abs/2303.06524
01-01-2023 Set-alternating schemes: A new class of large Condorcet domains.Karpov A Markström K Riis S Zhou B
Corr vol. abs/2308.02817
01-01-2023 Exploring Parity Challenges in Reinforcement Learning through Curriculum Learning with Noisy Labels.Zhou B Riis S
Corr vol. abs/2312.05379
01-01-2023 2019
Max-flow min-cut theorems on dispersion and entropy measures for communication networksRiis S Gadouleau M
Information and Computation,
Elsevier vol. 267, 49-73.
01-08-2019 2017
Graph Guessing Games and Non-Shannon Information InequalitiesBaber R Christofides D Dang AN Vaughan ER
IEEE Transactions on Information Theory,
Institute of Electrical and Electronics Engineers (IEEE) vol. 63 (7), 4257-4267.
01-07-2017 2016
Guessing Games on Triangle-Free Graphs.Cameron PJ Riis S
Electron. J. Comb. vol. 23, 1-1.
01-01-2016 2015
Guessing Games on Triangle-free GraphsCameron PJ Dang AN Riis S
In
Arxiv 13-10-2015 Network Communication with operators in Dedekind Finite and Stably Finite RingsRiis S
In
Arxiv 05-07-2015 Ada Lovelace, a scientist in the archivesRiis S Martin U
Ada Lovelace Symposium 2015- Celebrating 200 Years of a Computer Visionary on - Ada Lovelace Symposium '15.
01-01-2015 2014
Graph Guessing Games and non-Shannon Information InequalitiesBaber R Christofides D Dang AN Riis S Vaughan E
In
Arxiv 02-11-2014 Graph Guessing Games and non-Shannon Information InequalitiesBaber R Christofides D Dang AN Riis S
30-10-2014 Max-Flow Min-Cut Theorems for Multi-User Communication NetworksRiis S Gadouleau M
In
Arxiv 15-10-2014 Guessing Games on Triangle-free GraphsCameron PJ Dang AN
09-10-2014 Fixed points of Boolean networks, guessing graphs, and coding theoryGadouleau M Richard A Riis S
22-09-2014 What makes a chess program original? Revisiting the Rybka caseRiis S
Entertainment Computing,
Elsevier vol. 5 (3), 189-204.
01-08-2014 Graph Guessing Games and non-Shannon Information Inequalities.Baber R Christofides D Dang NA Riis S
Corr vol. abs/1410.8349
01-01-2014 2013
Memoryless computation: new results, constructions, and extensionsGadouleau M Riis S
In
Arxiv 13-11-2013 Multiple unicasts, graph guessing games, and non-Shannon inequalitiesRIIS SM Barber R Christofides D Dang A N
2013 International Symposium on Network Coding (NetCod) Calgary 7 Jun 2013 - 9 Jun 2013., 1-6.
01-01-2013 2012
Making magic: applying artificial intelligence methods to design a psychophysically compelling illusionWilliams H McOwan P
Perception vol. 41 (12), 1526-1526.
01-01-2012 2011
Memoryless computation: new results, constructions, and extensionsGadouleau M Riis S
25-11-2011 Combinatorial representationsCameron PJ Gadouleau M
Journal of Combinatorial Theory: Series A vol. 120 (3), 671-682.
06-09-2011 Network Coding Theorem for Dynamic Communication NetworksRIIS SM
Network Coding (NetCod), 2011 International Symposium Beijing 25 Jul 2011 - 26 Jul 2011., 1-6.
01-07-2011 Graph-theoretical Constructions for Graph Entropy and Network Coding Based CommunicationsGadouleau M Riis S
In
Arxiv 18-04-2011 Max-Flow Min-Cut Theorem for Renyi Entropy in Communication NetworksGadouleau M Riis S
2011 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY PROCEEDINGS (ISIT)., 603-607.
01-01-2011 Computing without memoryGadouleau M Riis S
Corr vol. abs/1111.6026
01-01-2011 2010
Max-Flow Min-Cut Theorems for Multi-User Communication NetworksRiis S
23-12-2010 Graph-theoretical Constructions for Graph Entropy and Network Coding
Based CommunicationsGadouleau M
13-10-2010 Graph-theoretical Constructions for Graph Entropy and Network Coding Based CommunicationsGadouleau M Riis S
Corr vol. abs/1010.2619
01-01-2010 2009
On the asymptotic Nullstellensatz and Polynomial Calculus proof complexityRIIS SM
In
On The Asymptotic Nullstellensatz and Polynomial Calculus Proof Complexity,
Electronic Colloquium on Computational Complexty 01-02-2009 2008
On the asymptotic Nullstellensatz and Polynomial calculus proof complexityRiis S
TWENTY-THIRD ANNUAL IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE, PROCEEDINGS., 272-283.
01-01-2008 2007
Graph Entropy, Network Coding and Guessing gamesRiis S
In
Arxiv 27-11-2007 Graph Entropy, Network Coding and Guessing gamesRIIS SM
01-11-2007 Reversible and irreversible information networksRiis S
IEEE T Inform Theory vol. 53 (11), 4339-4349.
01-11-2007 Information flows, graphs and their guessing numbersRiis S
Electron J Comb vol. 14 (1)
07-06-2007 2006
Problems in network coding and error correcting codes appended by a draft version of S Riis utilising public information in network codingRiis S Ahlswede R Baumer L Cai N Aydinian H Blinovsky V Deppe C Mashurian H
General Theory of Information Transfer and Combinatorics. vol. 4123, 861-897.
01-01-2006 Information flows, graphs and their guessing numbersRiis S
2006 4th International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks, Vols 1 and 2., 640-648.
01-01-2006 2004
Linear versus non-linear Boolean functions in Network FlowRIIS SM
38th Annual Conference on Information Sciences and Systems (CISS).
01-03-2004 2003
On Relativisation and Complexity Gap.Dantchev SS Baaz M Makowsky JA
CSL. vol. 2803, 142-154.
01-01-2003 On relativisation and complexity gap for resolution-based proof systemsDantchev S Riis S Baaz M Makowsky JA
COMPUTER SCIENCE LOGIC, PROCEEDINGS. vol. 2803, 142-154.
01-01-2003 2001
Uniformly generated submodules of permutation modules - Over fields of characteristic 0Riis S
J Pure Appl Algebra vol. 160 (2-3), 285-318.
25-06-2001 The complexity of scheduling TV commercialsHägele K Dúnlaing CÓ
Electronic Notes in Theoretical Computer Science,
Elsevier vol. 40, 162-185.
01-03-2001 A complexity gap for tree resolutionRiis S
Comput Complex vol. 10 (3), 179-209.
01-01-2001 Planar tautologies hard for ResolutionDantchev S Riis S
42ND ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS., 220-229.
01-01-2001 2000
A Tough Nut for Tree ResolutionDantchev S Riis S
Brics Report Series,
Det Kgl. Bibliotek/Royal Danish Library vol. 7 (10)
10-01-2000 Tree resolution proofs of the weak Pigeon-Hole PrincipleDantchev S Riis S
16TH ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY, PROCEEDINGS., 69-75.
01-01-2000 Self-organizing letter code-book for text-to-phoneme neural network modelJensen KJ
6th International Conference on Spoken Language Processing ICSLP 2000.
01-01-2000 1999
A Complexity Gap for Tree-ResolutionRiis S
Brics Report Series,
Det Kgl. Bibliotek/Royal Danish Library vol. 6 (29)
29-01-1999 1998
Uniformly Generated Submodules of Permutation ModulesRiis S Sitharam M
Brics Report Series,
Det Kgl. Bibliotek/Royal Danish Library vol. 5 (20)
20-01-1998 Generating Hard Tautologies Using Predicate Logic and the Symmetric GroupRiis S Sitharam M
Brics Report Series,
Det Kgl. Bibliotek/Royal Danish Library vol. 5 (19)
19-01-1998 1997
Count(ifq) does not imply Count(ifp)Riis S
Annals of Pure and Applied Logic,
Elsevier vol. 90 (1-3), 1-56.
01-12-1997 Dictionaries on AC^0 RAMs: Query Time Theta(√log n/log log n) is Necessary and SufficientAndersson A Miltersen PB
Brics Report Series,
Det Kgl. Bibliotek/Royal Danish Library vol. 4 (14)
04-06-1997 Bootstrapping the primitive recursive functions by only 27 colorsRiis S
Discrete Mathematics,
Elsevier vol. 169 (1-3), 269-272.
01-05-1997 Count($$q$$) versus the pigeon-hole principleRiis S
Archive For Mathematical Logic,
Springer Nature vol. 36 (3), 157-188.
01-04-1997 1996
Static dictionaries on AC0 RAMs: Query time Θ(√log n/log log n) is necessary and sufficientAndersson A Miltersen PB
Annual Symposium on Foundations of Computer Science Proceedings., 441-450.
01-12-1996 Static dictionaries on AC/sup 0/ RAMs: query time /spl theta/(/spl radic/log n/log log n) is necessary and sufficientAndersson A Miltersen PB Riis S Thorup M
Proceedings of 37th Conference on Foundations of Computer Science., 441-450.
01-01-1996 1994
Count(q) versus the Pigeon-Hole PrincipleRiis S
Brics Report Series,
Det Kgl. Bibliotek/Royal Danish Library vol. 1 (26)
03-08-1994 Bootstrapping the Primitive Recursive Functions by 47 ColorsRiis S
Brics Report Series,
Det Kgl. Bibliotek/Royal Danish Library vol. 1 (25)
03-08-1994 A Fractal which violates the Axiom of DeterminacyRiis S
Brics Report Series,
Det Kgl. Bibliotek/Royal Danish Library vol. 1 (24)
03-08-1994 Finitisation in Bounded ArithmeticRiis S
Brics Report Series,
Det Kgl. Bibliotek/Royal Danish Library vol. 1 (23)
03-08-1994 Count(q) does not imply Count(p)Riis S
Brics Report Series,
Det Kgl. Bibliotek/Royal Danish Library vol. 1 (21)
03-07-1994 A Dispersion Theorem for Communication Networks Based on Term SetsRIIS SM Gadouleau M
2011 IEEE International Symposium on Information Theory 31 Jul 2011 - 5 Aug 2011., 593-597.
The guessing number of shift graphsCameron P Riis S Wu T
Journal of Discrete Algorithms, vol. 2009 (7), 220-226.
Classification of the asymptotic Proof Complexity of Polynomial CalculusRIIS SM
