Dr Soren Riis

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

2025

Term Coding for Extremal Combinatorics: Dispersion and Complexity Dichotomies
Riis SR
In Arxiv 

DOI 10.48550/arxiv.2504.16265

04-10-2025

Humanity's Last Exam
Phan L Gatti A Han Z Li N Hu J Zhang H Zhang CBC Shaaban M et al.
In Arxiv 

DOI 10.48550/arxiv.2501.14249

25-09-2025

Impartial Games: A Challenge for Reinforcement Learning
Zhou B Riis SR
In Arxiv 

DOI 10.48550/arxiv.2205.12787

03-08-2025

Coherent domains and improved lower bounds for the maximum size of Condorcet domains
Karpov A Markström K Riis S
Discrete Applied Mathematics, Elsevier vol. 370, 57-70.  

DOI 10.1016/j.dam.2025.03.007

QMRO

01-07-2025

An efficient heuristic search algorithm for discovering large Condorcet domains
Zhou B
4or, Springer Nature vol. 23 (2), 193-216.  

DOI 10.1007/s10288-025-00583-1

QMRO

24-01-2025

Condorcet domains on at most seven alternatives
Akello-Egwel D Leedham-Green C Litterick A Riis S
Mathematical Social Sciences, Elsevier vol. 133, 23-33.  

DOI 10.1016/j.mathsocsci.2024.12.002

QMRO

01-01-2025

2024

CDL: A fast and flexible library for the study of permutation sets with structural restrictions
Zhou B Markström K
Softwarex, Elsevier vol. 28 

DOI 10.1016/j.softx.2024.101951

QMRO

01-12-2024

Mastering NIM and Impartial Games with Weak Neural Networks: An AlphaZero-inspired Multi-Frame Approach
Riis S
In Arxiv 

DOI 10.48550/arxiv.2411.06403

10-11-2024

Arrow's single peaked domains, richness, and domains for plurality and the Borda count
Markström K Riis S Zhou B
In Arxiv 

DOI 10.48550/arxiv.2401.12547

23-01-2024

Local Diversity of Condorcet Domains
Karpov A Markström K Riis S Zhou B
In Arxiv 

DOI 10.48550/arxiv.2401.11912

22-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.  

QMRO

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

Exploring Parity Challenges in Reinforcement Learning through Curriculum Learning with Noisy Labels
Zhou B Riis S
In Arxiv 

DOI 10.48550/arxiv.2312.05379

08-12-2023

The largest Condorcet domain on 8 alternatives
Leedham-Green C Markström K
Social Choice and Welfare, Springer Nature vol. 62 (1), 109-116.  

DOI 10.1007/s00355-023-01481-3

QMRO

05-09-2023

Bipartite peak-pit domains
Karpov A Markström K Riis S Zhou B
In Arxiv 

DOI 10.48550/arxiv.2308.02817

05-08-2023

Condorcet Domains of Degree at most Seven
Akello-Egwell D Leedham-Green C Litterick A Markström K Riis S
In Arxiv 

DOI 10.48550/arxiv.2306.15993

QMRO

28-06-2023

The Largest Condorcet Domains on 8 Alternatives
Leedham-Green C Markström K Riis S
In Arxiv 

DOI 10.48550/arxiv.2303.15002

27-03-2023

A heuristic search algorithm for discovering large Condorcet domains
Zhou B Riis S
In Arxiv 

DOI 10.48550/arxiv.2303.06524

QMRO

11-03-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 Networks
RIIS S Gadouleau M
Information and Computation, Elsevier 

DOI 10.1016/j.ic.2019.03.004

QMRO

19-03-2019

2017

Graph Guessing Games and Non-Shannon Information Inequalities
Baber R Christofides D Dang AN Vaughan ER
IEEE Transactions on Information Theory, Institute of Electrical and Electronics Engineers (IEEE) vol. 63 (7), 4257-4267.  

DOI 10.1109/tit.2016.2628819

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

Network Communication with operators in Dedekind Finite and Stably Finite Rings
Riis S
In Arxiv 

DOI 10.48550/arxiv.1507.01249

QMRO

05-07-2015

Ada Lovelace, a scientist in the archives
Riis S Martin U
Ada Lovelace Symposium 2015- Celebrating 200 Years of a Computer Visionary on - Ada Lovelace Symposium '15. 

DOI 10.1145/2867731.2867747

01-01-2015

2014

Graph Guessing Games and non-Shannon Information Inequalities
Baber R Christofides D Dang AN Riis S Vaughan E
In Arxiv 

DOI 10.48550/arxiv.1410.8349

30-10-2014

Guessing Games on Triangle-free Graphs
Cameron PJ Dang AN
 

DOI 10.37236/4731

QMRO

09-10-2014

Fixed points of Boolean networks, guessing graphs, and coding theory
Gadouleau M Richard A Riis S
 

DOI 10.1137/140988358

QMRO

22-09-2014

What makes a chess program original? Revisiting the Rybka case
Riis S
Entertainment Computing, Elsevier vol. 5 (3), 189-204.  

DOI 10.1016/j.entcom.2014.04.004

QMRO

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

Multiple unicasts, graph guessing games, and non-Shannon inequalities
RIIS SM Barber R Christofides D Dang A N
2013 International Symposium on Network Coding (NetCod) Calgary 7 Jun 2013 - 9 Jun 2013., 1-6.  

DOI 10.1109/NetCod.2013.6570823

01-01-2013

2012

Making magic: applying artificial intelligence methods to design a psychophysically compelling illusion
Williams H McOwan P
Perception vol. 41 (12), 1526-1526.  
01-01-2012

2011

Memoryless computation: new results, constructions, and extensions
Gadouleau M Riis S
 

DOI 10.1016/j.tcs.2014.09.040

QMRO

25-11-2011

Combinatorial representations
Cameron PJ Gadouleau M
Journal of Combinatorial Theory: Series A vol. 120 (3), 671-682.  

DOI 10.1016/j.jcta.2012.12.002

QMRO

06-09-2011

Network Coding Theorem for Dynamic Communication Networks
RIIS SM
Network Coding (NetCod), 2011 International Symposium Beijing 25 Jul 2011 - 26 Jul 2011., 1-6.  

DOI 10.1109/ISNETCOD.2011.5979085

01-07-2011

Max-Flow Min-Cut Theorem for Renyi Entropy in Communication Networks
Gadouleau M Riis S
2011 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY PROCEEDINGS (ISIT)., 603-607.  

DOI 10.1109/ISIT.2011.6034200

01-01-2011

Computing without memory
Gadouleau M Riis S
Corr vol. abs/1111.6026 
01-01-2011

2010

Max-Flow Min-Cut Theorems for Multi-User Communication Networks
Riis S
 

QMRO

23-12-2010

Graph-theoretical Constructions for Graph Entropy and Network Coding Based Communications
Gadouleau M Riis S
In Arxiv 

DOI 10.48550/arxiv.1010.2619

13-10-2010

Graph-theoretical Constructions for Graph Entropy and Network Coding Based Communications
Gadouleau M
 

DOI 10.1109/TIT.2011.2155618

QMRO

13-10-2010

Graph-theoretical Constructions for Graph Entropy and Network Coding Based Communications
Gadouleau M Riis S
Corr vol. abs/1010.2619 
01-01-2010

2009

On the asymptotic Nullstellensatz and Polynomial Calculus proof complexity
RIIS 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 complexity
Riis S
TWENTY-THIRD ANNUAL IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE, PROCEEDINGS., 272-283.  

DOI 10.1109/LICS.2008.30

01-01-2008

2007

Graph Entropy, Network Coding and Guessing games
Riis S
In Arxiv 

DOI 10.48550/arxiv.0711.4175

26-11-2007

Graph Entropy, Network Coding and Guessing games
RIIS SM
 

QMRO

01-11-2007

Reversible and irreversible information networks
Riis S
IEEE T Inform Theory vol. 53 (11), 4339-4349.  

DOI 10.1109/TIT.2007.907345

01-11-2007

Information flows, graphs and their guessing numbers
Riis S
Electron J Comb vol. 14 (1) 

DOI 10.1109/WIOPT.2006.1666516

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 coding
Riis 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.  

DOI 10.1007/11889342_56

01-01-2006

Information flows, graphs and their guessing numbers
Riis S
2006 4th International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks, Vols 1 and 2., 640-648.  

DOI 10.37236/962

01-01-2006

2004

Linear versus non-linear Boolean functions in Network Flow
RIIS 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 systems
Dantchev S Riis S Baaz M Makowsky JA
COMPUTER SCIENCE LOGIC, PROCEEDINGS. vol. 2803, 142-154.  

DOI 10.1007/978-3-540-45220-1_14

01-01-2003

2001

Uniformly generated submodules of permutation modules - Over fields of characteristic 0
Riis S
J Pure Appl Algebra vol. 160 (2-3), 285-318.  

DOI 10.1016/S0022-4049(00)00069-4

25-06-2001

The complexity of scheduling TV commercials
Hägele K Dúnlaing CÓ
Electronic Notes in Theoretical Computer Science, Elsevier vol. 40, 162-185.  

DOI 10.1016/s1571-0661(05)80043-x

01-03-2001

A complexity gap for tree resolution
Riis S
Comput Complex vol. 10 (3), 179-209.  

DOI 10.1007/s00037-001-8194-y

01-01-2001

Planar tautologies hard for Resolution
Dantchev S Riis S
42ND ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS., 220-229.  

DOI 10.1109/SFCS.2001.959896

01-01-2001

2000

A Tough Nut for Tree Resolution
Dantchev S Riis S
Brics Report Series, Det Kgl. Bibliotek/Royal Danish Library vol. 7 (10) 

DOI 10.7146/brics.v7i10.20137

10-01-2000

Tree resolution proofs of the weak Pigeon-Hole Principle
Dantchev S Riis S
16TH ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY, PROCEEDINGS., 69-75.  

DOI 10.1109/CCC.2001.933873

01-01-2000

Self-organizing letter code-book for text-to-phoneme neural network model
Jensen KJ
6th International Conference on Spoken Language Processing ICSLP 2000. 
01-01-2000

1999

A Complexity Gap for Tree-Resolution
Riis S
Brics Report Series, Det Kgl. Bibliotek/Royal Danish Library vol. 6 (29) 

DOI 10.7146/brics.v6i29.20098

29-01-1999

1998

Uniformly Generated Submodules of Permutation Modules
Riis S Sitharam M
Brics Report Series, Det Kgl. Bibliotek/Royal Danish Library vol. 5 (20) 

DOI 10.7146/brics.v5i20.19426

20-01-1998

Generating Hard Tautologies Using Predicate Logic and the Symmetric Group
Riis S Sitharam M
Brics Report Series, Det Kgl. Bibliotek/Royal Danish Library vol. 5 (19) 

DOI 10.7146/brics.v5i19.19425

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.  

DOI 10.1016/s0168-0072(97)00029-8

01-12-1997

Dictionaries on AC^0 RAMs: Query Time Theta(√log n/log log n) is Necessary and Sufficient
Andersson A Miltersen PB
Brics Report Series, Det Kgl. Bibliotek/Royal Danish Library vol. 4 (14) 

DOI 10.7146/brics.v4i14.21678

04-06-1997

Bootstrapping the primitive recursive functions by only 27 colors
Riis S
Discrete Mathematics, Elsevier vol. 169 (1-3), 269-272.  

DOI 10.1016/s0012-365x(97)87041-0

01-05-1997

Count($$q$$) versus the pigeon-hole principle
Riis S
Archive For Mathematical Logic, Springer Nature vol. 36 (3), 157-188.  

DOI 10.1007/s001530050060

01-04-1997

1996

Static dictionaries on AC0 RAMs: Query time Θ(√log n/log log n) is necessary and sufficient
Andersson 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 sufficient
Andersson A Miltersen PB Riis S Thorup M
Proceedings of 37th Conference on Foundations of Computer Science., 441-450.  

DOI 10.1109/sfcs.1996.548503

01-01-1996

1994

Count(q) versus the Pigeon-Hole Principle
Riis S
Brics Report Series, Det Kgl. Bibliotek/Royal Danish Library vol. 1 (26) 

DOI 10.7146/brics.v1i26.21640

03-08-1994

Bootstrapping the Primitive Recursive Functions by 47 Colors
Riis S
Brics Report Series, Det Kgl. Bibliotek/Royal Danish Library vol. 1 (25) 

DOI 10.7146/brics.v1i25.21641

03-08-1994

A Fractal which violates the Axiom of Determinacy
Riis S
Brics Report Series, Det Kgl. Bibliotek/Royal Danish Library vol. 1 (24) 

DOI 10.7146/brics.v1i24.21642

03-08-1994

Finitisation in Bounded Arithmetic
Riis S
Brics Report Series, Det Kgl. Bibliotek/Royal Danish Library vol. 1 (23) 

DOI 10.7146/brics.v1i23.21644

03-08-1994

Count(q) does not imply Count(p)
Riis S
Brics Report Series, Det Kgl. Bibliotek/Royal Danish Library vol. 1 (21) 

DOI 10.7146/brics.v1i21.21646

03-07-1994

A Dispersion Theorem for Communication Networks Based on Term Sets
RIIS SM Gadouleau M
2011 IEEE International Symposium on Information Theory 31 Jul 2011 - 5 Aug 2011., 593-597.  

DOI 10.1109/ISIT.2011.6034198

The guessing number of shift graphs
Cameron P Riis S Wu T
Journal of Discrete Algorithms, vol. 2009 (7), 220-226.  

DOI 10.1016/j.jda.2008.09.009

Classification of the asymptotic Proof Complexity of Polynomial Calculus
RIIS SM
 

QMRO

Research Group

PhD Students

• Remo Sasso
  Scalable and Efficient Exploration For Model-Based Reinforcement Learning

News