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 Fundamental Computer Science

2025

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

DOI 10.1016/j.mathsocsci.2024.12.002

01-01-2025

2024

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

DOI 10.1016/j.softx.2024.101951

QMRO

01-12-2024

Arrow's single peaked domains, richness, and domains for plurality and the Borda count.
Markström K, Riis S and Zhou B
Corr vol. abs/2401.12547 
01-01-2024

Local Diversity of Condorcet Domains.
Karpov A, Markström K, Riis S and Zhou B
Corr vol. abs/2401.11912 
01-01-2024

2023

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

DOI 10.1007/s00355-023-01481-3

QMRO

05-09-2023

New Record-Breaking Condorcet Domains on 10 and 11 Alternatives.
Zhou B and 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 and Zhou B
Corr vol. abs/2308.02817 
01-01-2023

Condorcet Domains of Degree at most Seven.
Akello-Egwell D, Leedham-Green CR, Litterick A, Markström K and Riis S
Corr vol. abs/2306.15993 
01-01-2023

Exploring Parity Challenges in Reinforcement Learning through Curriculum Learning with Noisy Labels.
Zhou B and Riis S
Corr vol. abs/2312.05379 
01-01-2023

2022

Impartial Games: A Challenge for Reinforcement Learning.
Zhou B and Riis S
Corr vol. abs/2205.12787 
01-01-2022

2019

Max-Flow Min-Cut Theorems on Dispersion and Entropy Measures for Communication Networks
RIIS S and 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 and Riis S
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, Dang NA and 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 and Woodhouse N
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 and Vaughan E
 

DOI 10.1109/TIT.2016.2628819

QMRO

30-10-2014

Guessing Games on Triangle-free Graphs
Cameron PJ, Dang AN and Riis S
 

DOI 10.37236/4731

QMRO

09-10-2014

Fixed points of Boolean networks, guessing graphs, and coding theory
Gadouleau M, Richard A and 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 and Vaughan ER
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 and Vaughan E R
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 and Riis S
Perception vol. 41 (12), 1526-1526.  
01-01-2012

2011

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

DOI 10.1016/j.tcs.2014.09.040

QMRO

25-11-2011

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

DOI 10.1016/j.jcta.2012.12.002

QMRO

06-09-2011

A Dispersion Theorem for Communication Networks Based on Term Sets
Riis S and Gadouleau M
2011 IEEE International Symposium on Information Theory Proceedings., 593-597.  

DOI 10.1109/isit.2011.6034198

01-07-2011

Network Coding Theorem for Dynamic Communication Networks
RIIS SM and Gadouleau M
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 and 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 and Riis S
Corr vol. abs/1111.6026 
01-01-2011

2010

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

QMRO

23-12-2010

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

DOI 10.1109/TIT.2011.2155618

QMRO

13-10-2010

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

2009

On the guessing number of shift graphs
Wu T, Cameron P and Riis S
Journal of Discrete Algorithms, Elsevier vol. 7 (2), 220-226.  

DOI 10.1016/j.jda.2008.09.009

01-06-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 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 and Ahlswede R
General Theory of Information Transfer and Combinatorics. vol. 4123, 861-897. Editors: Ahlswede R, Baumer L, Cai N, Aydinian H, Blinovsky V, Deppe C and Mashurian H. 

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 and Riis S
CSL. vol. 2803, 142-154. Editors: Baaz M and Makowsky JA. 
01-01-2003

On relativisation and complexity gap for resolution-based proof systems
Dantchev S and Riis S
COMPUTER SCIENCE LOGIC, PROCEEDINGS. vol. 2803, 142-154. Editors: Baaz M and Makowsky JA. 

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 and Sitharam M
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Ó and Riis S
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 and 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 and 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 and 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 and Riis S
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 and 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 and 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, Riis S and Thorup M
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 AC⁰ RAMs: Query time Θ(√log n/log log n) is necessary and sufficient
Andersson A, Miltersen PB, Riis S and Thorup M
Annual Symposium on Foundations of Computer Science - Proceedings., 441-450.  
01-12-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