Publications

Papers, preprints, and other research publications. Hosted copies have a direct Hosted PDF link; publisher and earlier-version links are listed alongside them.

Hosted papers · DBLP · Google Scholar

48 records, with earlier versions grouped where identified.

2026

One Unit Separates Polynomial Time from Undecidability in Term Coding
Søren Riis
arXiv 2504.16265 · 2026 Preprint
Latest manuscript: 12 September 2026. The arXiv replacement is awaiting its public update; use the hosted PDF for this revision. The interactive edition connects the paper to explanations and formal proof evidence.
Hosted PDF arXiv Interactive paper Lean source Archived software (DOI)
A benchmark of expert-level academic questions to assess AI capabilities
Center for AI Safety, Scale AI, HLE Contributors Consortium (including Søren Riis)
Nature 649: 1139–1146 · 2026 Published
Published consortium paper for Humanity’s Last Exam.
Paper / publisher Earlier preprint: Humanity’s Last Exam
Impartial Games: A Challenge for Reinforcement Learning
Bei Zhou, Søren Riis
Machine Learning 115: 54 · 2026 Published
First preprint 2022; journal article 2026.
Paper / publisher Earlier preprint (2022) Try it Watch it
Coin flipping and waiting times paradoxes: Why fair coins are exceptional
Søren Riis, Mike Paterson
arXiv 2601.16580 · 2026 Preprint
arXiv Try it Watch it
Drift and selection in LLM text ecosystems
Søren Riis
Preprint abs/2604.08554 · 2026 Preprint
Hosted PDF arXiv Try it Watch it
Improved lower bounds for the maximum size of Condorcet domains
Alexander Karpov, Klas Markström, Søren Riis, Bei Zhou
Preprint abs/2601.07336 · 2026 Preprint
arXiv
Mastering NIM and Impartial Games with Weak Neural Networks: An AlphaZero-inspired Multi-Frame Approach
Søren Riis
Preprint abs/2411.06403 · 2026 Preprint
First submitted 2024; updated 2026.
arXiv Try it Watch it
Term Coding: An Entropic Framework for Extremal Combinatorics and the Guessing-Number Sandwich Theorem
Søren Riis
Preprint abs/2601.16614 · 2026 Preprint
arXiv

2025

An efficient heuristic search algorithm for discovering large Condorcet domains
Bei Zhou, Søren Riis
4OR 23: 193–216 · 2025 Published
Paper / publisher
Coherent domains and improved lower bounds for the maximum size of Condorcet domains
Alexander Karpov, Klas Markström, Søren Riis, Bei Zhou
Discrete Applied Mathematics 370: 57–70 · 2025 Published
Paper / publisher Earlier preprint (2023)
Condorcet domains on at most seven alternatives
Dolica Akello-Egwel, Charles R. Leedham-Green, Alastair Litterick, Klas Markström, Søren Riis
Mathematical Social Sciences 133: 23–33 · 2025 Published
Paper / publisher Earlier preprint (2023) Repository PDF

2024

CDL: A fast and flexible library for the study of permutation sets with structural restrictions
Bei Zhou, Klas Markström, Søren Riis
SoftwareX 28: 101951 · 2024 Published
Paper / publisher Earlier preprint (2023)
The largest Condorcet domain on 8 alternatives
Charles R. Leedham-Green, Klas Markström, Søren Riis
Social Choice and Welfare 62: 109–116 · 2024 Published
Paper / publisher Try it
Arrow's single peaked domains, richness, and domains for plurality and the Borda count
Klas Markström, Søren Riis, Bei Zhou
Preprint abs/2401.12547 · 2024 Preprint
arXiv
Local Diversity of Condorcet Domains
Alexander Karpov, Klas Markström, Søren Riis, Bei Zhou
Preprint abs/2401.11912 · 2024 Preprint
arXiv

2023

Exploring Parity Challenges in Reinforcement Learning through Curriculum Learning with Noisy Labels
Bei Zhou, Søren Riis
Preprint abs/2312.05379 · 2023 Preprint
arXiv

2019

Max-flow min-cut theorems on dispersion and entropy measures for communication networks
Søren Riis, Maximilien Gadouleau
Information and Computation 267: 49–73 · 2019 Published
Paper / publisher Earlier preprint (2010)

2017

Graph Guessing Games and Non-Shannon Information Inequalities
Rahil Baber, Demetres Christofides, Ntah Ahn Dang, Emil R. Vaughan, Søren Riis
IEEE Transactions on Information Theory 63: 4257–4267 · 2017 Published
Paper / publisher Earlier preprint (2014)

2016

Guessing Games on Triangle-Free Graphs
Peter J. Cameron, Ntah Ahn Dang, Søren Riis
Electronic Journal of Combinatorics 23: P1.48 · 2016 Published
Paper / publisher Earlier preprint (2014)

2015

Ada Lovelace, a scientist in the archives
Søren Riis, Ursula Martin, Nick Woodhouse
Ada Lovelace Symposium: 14 · 2015 Published
Paper / publisher
Fixed Points of Boolean Networks, Guessing Graphs, and Coding Theory
Maximilien Gadouleau, Adrien Richard, Søren Riis
SIAM Journal on Discrete Mathematics 29: 2312–2335 · 2015 Published
Paper / publisher Earlier preprint (2014)
Memoryless computation: New results, constructions, and extensions
Maximilien Gadouleau, Søren Riis
Theoretical Computer Science 562: 129–145 · 2015 Published
Paper / publisher Earlier preprint (2011)

2014

What makes a chess program original? Revisiting the Rybka case
Søren Riis
Entertainment Computing 5: 189–204 · 2014 Published
Paper / publisher

2013

Combinatorial representations
Peter J. Cameron, Maximilien Gadouleau, Søren Riis
Journal of Combinatorial Theory, Series A 120: 671–682 · 2013 Published
Paper / publisher
Multiple unicasts, graph guessing games, and non-Shannon inequalities
Rahil Baber, Demetres Christofides, Ntah Ahn Dang, Søren Riis, Emil R. Vaughan
NetCod: 1–6 · 2013 Published
Paper / publisher

2011

A dispersion theorem for communication networks based on term sets
Søren Riis, Maximilien Gadouleau
ISIT: 593–597 · 2011 Published
Paper / publisher
Graph-Theoretical Constructions for Graph Entropy and Network Coding Based Communications
Maximilien Gadouleau, Søren Riis
IEEE Transactions on Information Theory 57: 6703–6717 · 2011 Published
Hosted PDF Paper / publisher Earlier preprint (2010) Try it
Max-flow min-cut theorem for Rényi entropy in communication networks
Maximilien Gadouleau, Søren Riis
ISIT: 603–607 · 2011 Published
Paper / publisher

2009

On the guessing number of shift graphs
Taoyang Wu, Peter J. Cameron, Søren Riis
Journal of Discrete Algorithms 7: 220–226 · 2009 Published
Paper / publisher
On the asymptotic Nullstellensatz and Polynomial Calculus proof complexity
Søren Riis
Electronic Colloquium on Computational Complexity TR09: TR09-014 · 2009 Report
Paper / publisher

2008

On the Asymptotic Nullstellensatz and Polynomial Calculus Proof Complexity
Søren Riis
LICS: 272–283 · 2008 Published
Paper / publisher

2007

Information Flows, Graphs and their Guessing Numbers
Søren Riis
Electronic Journal of Combinatorics 14: R44 · 2007 Published
Paper / publisher Try it
Reversible and Irreversible Information Networks
Søren Riis
IEEE Transactions on Information Theory 53: 4339–4349 · 2007 Published
Paper / publisher
Graph Entropy, Network Coding and Guessing games
Søren Riis
Preprint abs/0711.4175 · 2007 Preprint
arXiv

2006

Problems in Network Coding and Error Correcting Codes Appended by a Draft Version of S. Riis "Utilising Public Information in Network Coding"
Søren Riis, Rudolf Ahlswede
GTIT-C: 861–897 · 2006 Published
Paper / publisher

2003

On Relativisation and Complexity Gap
Stefan S. Dantchev, Søren Riis
CSL: 142–154 · 2003 Published
Paper / publisher

2001

"Planar" Tautologies Hard for Resolution
Stefan S. Dantchev, Søren Riis
FOCS: 220–229 · 2001 Published
Paper / publisher
A complexity gap for tree resolution
Søren Riis
Computational Complexity 10: 179–209 · 2001 Published
Paper / publisher Watch it
Tree Resolution Proofs of the Weak Pigeon-Hole Principle
Stefan S. Dantchev, Søren Riis
CCC: 69–75 · 2001 Published
Paper / publisher

2000

Generating hard tautologies using predicate logic and the symmetric group
Søren Riis, Meera Sitharam
Logic Journal of the IGPL 8: 787–795 · 2000 Published
Paper / publisher
The complexity of scheduling TV commercials
Klemens Hägele, Colm Ó'Dúnlaing, Søren Riis
MFCSIT: 162–185 · 2000 Published
Paper / publisher
Preface
Carsten Butz, Ulrich Kohlenbach, Søren Riis, Glynn Winskel
Annals of Pure and Applied Logic 104: 1–2 · 2000 Editorial
Paper / publisher

1997

Bootstrapping the primitive recursive functions by only 27 colors
Søren Riis
Discrete Mathematics 169: 269–272 · 1997 Published
Paper / publisher
Count(q) Does Not Imply Count(p)
Søren Riis
Annals of Pure and Applied Logic 90: 1–56 · 1997 Published
Paper / publisher
Count(q) versus the pigeon-hole principle
Søren Riis
Archive for Mathematical Logic 36: 157–188 · 1997 Published
Paper / publisher
Non-constant Degree Lower Bounds imply linear Degree Lower Bounds
Søren Riis, Meera Sitharam
Electronic Colloquium on Computational Complexity TR97: TR97-048 · 1997 Report
Paper / publisher

1996

More on the relative strength of counting principles
Paul Beame, Søren Riis
Proof Complexity and Feasible Arithmetics: 13–35 · 1996 Published
Paper / publisher
Static Dictionaries on AC0 RAMs: Query Time Theta(sqrt(log n/log log n)) is Necessary and Sufficient
Arne Andersson, Peter Bro Miltersen, Søren Riis, Mikkel Thorup
FOCS: 441–450 · 1996 Published
Paper / publisher