Dr Soren Riis
Reader
School of Electronic Engineering and Computer Science
Queen Mary University of London
Research
Mathematical Logic, Complexity Theory, Proof Complexity, Algebraic Proof Complexity, Information Theory, Network Coding
Publications
Publications of specific relevance to the Centre for Fundamentals of AI and Computational Theory
2026
Mastering NIM and Impartial Games with Weak Neural Networks: An AlphaZero-inspired Multi-Frame ApproachRiis S
In
Arxiv 15-02-2026 Term Coding and Dispersion: A Perfect-vs-Rate Complexity Dichotomy for Information FlowRiis S
In
Arxiv 08-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 Term Coding: An Entropic Framework for Extremal Combinatorics and the Guessing--Number Sandwich TheoremRiis S
In
Arxiv 23-01-2026 Coin flipping and waiting times paradoxes: Why fair coins are exceptionalRiis S Paterson M
In
Arxiv 23-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 2025
Term Coding for Extremal Combinatorics: Dispersion and Complexity DichotomiesRiis SR
In
Arxiv 04-10-2025Humanity's Last ExamPhan L Gatti A Han Z Li N Hu J Zhang H Zhang CBC Shaaban M et al.
In
Arxiv 25-09-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-2025 An 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 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 SR 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 CDL: A fast and flexible library for the study of permutation sets with structural restrictions.Zhou B Markström K
Softwarex vol. 28, 101951-101951.
01-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 2022
Impartial Games: A Challenge for Reinforcement Learning.Zhou B
Corr vol. abs/2205.12787
01-01-2022 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
Research Group
PhD Students
- Remo Sasso
Efficient Exploration and Foundation Model Priors: Enhancing Sample Efficiency in Deep Reinforcement Learning
News
March 2026
20 March 2026
Søren Riis and Marc Roth are both joint winners of the SafeAI Benchmark Competition "Humanity's Last Exam".
The linked paper "A benchmark of expert-level academic questions to assess AI capabilities", co-authored by FACT researchers Søren Riis and Marc Roth, has been published in Nature. This paper accompanies the ... [more]
