# Dr Soren Riis

Email: s.riis@qmul.ac.uk
Telephone: +44 20 7882 6284
Room Number: Peter Landin, CS 420
Website: http://www.eecs.qmul.ac.uk/~smriis
Office Hours: Thursday 11:30-13:30, Wednesday 13:00-15:00

## Teaching

### Computability, Complexity and Algorithms (Undergraduate)

A theoretical course, which concerned with the theoretical core of Computer Science. The course covers some of the most successful algorithms as well as some of the most central decision problems. A large part of the course will focus on the NP versus P problem as well as other famous unsolved problem in Computer Science. To understand this problem we consider the issue of how one programming problem can be disguised as another apparently very different problem. This idea is very important in designing algorithms and plays a crucial role in the theory of NP-completeness.

### Logic and Discrete Structures (Undergraduate)

The module consists of two parts, each of fundamental importance for any serious approach to Computer Science: Logic and Discrete Structures. Logic has been called the Calculus of Computer Science. It plays a very important role in computer architecture (logic gates), software engineering (specification and verification), programming languages (semantics, logic programming), databases (relational algebra and SQL the standard computer language for accessing and manipulating databases), artificial intelligence (automatic theorem proving), algorithms (complexity and expressiveness), and theory of computation (general notions of computability). Computer scientists use Discrete Mathematics to think about their subject and to communicate their ideas independently of particular computers and programs. They expect other computer scientists to be fluent in the language and methods of Discrete Mathematics. In the module we consider Propositional logic as well as Predicate Calculus. We will treat Propositional Logic and Predicate Calculus as formal systems. You will learn how to produce and annotate formal proofs. As application we will briefly consider the programming language Prolog. This module will also cover a variety of standard representations, operations, properties, constructions and applications associated with selected structures from Discrete Mathematics (sets, relations, functions, directed graphs, orders).

## Research

### Research Interests:

Mathematical Logic, Complexity Theory, Proof Complexity, Algebraic Proof Complexity, Information Theory, Network Coding, Combinatorics and Reinforced Learning.

## Publications

• Leedham-Green C, Markström K, Riis S (2024). The largest Condorcet domain on 8 alternatives. nameOfConference

• Zhou B, Markström K, Riis S (2023). CDL: A fast and flexible library for the study of permutation sets with structural restrictions.. nameOfConference

DOI: doi

QMRO: qmroHref
• Akello-Egwell D, Leedham-Green CR, Litterick A et al. (2023). Condorcet Domains of Degree at most Seven.. nameOfConference

DOI: doi

QMRO: qmroHref
• Zhou B, Riis S (2023). Exploring Parity Challenges in Reinforcement Learning through Curriculum Learning with Noisy Labels.. nameOfConference

DOI: doi

QMRO: qmroHref
• Zhou B, Riis S (2023). New Record-Breaking Condorcet Domains on 10 and 11 Alternatives.. nameOfConference

DOI: doi

QMRO: qmroHref
• Karpov A, Markström K, Riis S et al. (2023). Set-alternating schemes: A new class of large Condorcet domains.. nameOfConference

DOI: doi

QMRO: qmroHref
• Zhou B, Riis S (2022). Impartial Games: A Challenge for Reinforcement Learning.. nameOfConference

DOI: doi

QMRO: qmroHref
• RIIS S, Gadouleau M (2019). Max-Flow Min-Cut Theorems on Dispersion and Entropy Measures for Communication Networks. nameOfConference

• Baber R, Christofides D, Dang AN et al. (2017). Graph Guessing Games and Non-Shannon Information Inequalities. nameOfConference

QMRO: qmroHref
• Cameron PJ, Dang NA, Riis S (2016). Guessing Games on Triangle-Free Graphs.. nameOfConference

DOI: doi

QMRO: qmroHref
• Riis S (2015). Network Communication with operators in Dedekind Finite and Stably Finite Rings. nameOfConference

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

QMRO: qmroHref
• Baber R, Christofides D, Dang AN et al. (2014). Graph Guessing Games and non-Shannon Information Inequalities. nameOfConference

• Cameron PJ, Dang AN, Riis S (2014). Guessing Games on Triangle-free Graphs. nameOfConference

• Gadouleau M, Richard A, Riis S (2014). Fixed points of Boolean networks, guessing graphs, and coding theory. nameOfConference

• Riis S (2014). What makes a chess program original? Revisiting the Rybka case. nameOfConference

• Baber R, Christofides D, Dang NA et al. (2014). Graph Guessing Games and non-Shannon Information Inequalities.. nameOfConference

DOI: doi

QMRO: qmroHref
• RIIS SM, Barber, R, Christofides, D et al. (2013). Multiple unicasts, graph guessing games, and non-Shannon inequalities. 2013 International Symposium on Network Coding (NetCod)

QMRO: qmroHref
• Williams H, McOwan P, Riis S (2012). Making magic: applying artificial intelligence methods to design a psychophysically compelling illusion. nameOfConference

DOI: doi

QMRO: qmroHref
• Gadouleau M, Riis S (2011). Memoryless computation: new results, constructions, and extensions. nameOfConference

• Cameron PJ, Gadouleau M, Riis S (2011). Combinatorial representations. nameOfConference

• Riis S, Gadouleau M (2011). A Dispersion Theorem for Communication Networks Based on Term Sets. 2011 IEEE International Symposium on Information Theory Proceedings

QMRO: qmroHref
• RIIS SM, Gadouleau M (2011). Network Coding Theorem for Dynamic Communication Networks. Network Coding (NetCod), 2011 International Symposium

QMRO: qmroHref
• Gadouleau M, Riis S (2011). Computing without memory. nameOfConference

DOI: doi

QMRO: qmroHref
• Gadouleau M, Riis S (2011). Max-Flow Min-Cut Theorem for Renyi Entropy in Communication Networks. nameOfConference

QMRO: qmroHref
• Riis S, Gadouleau M (2010). Max-Flow Min-Cut Theorems for Multi-User Communication Networks. nameOfConference

DOI: doi

• Gadouleau M, Riis S (2010). Graph-theoretical Constructions for Graph Entropy and Network Coding Based Communications. nameOfConference

• Gadouleau M, Riis S (2010). Graph-theoretical Constructions for Graph Entropy and Network Coding Based Communications. nameOfConference

DOI: doi

QMRO: qmroHref
• Wu T, Cameron P, Riis S (2009). On the guessing number of shift graphs. nameOfConference

QMRO: qmroHref
• RIIS SM (2009). On the asymptotic Nullstellensatz and Polynomial Calculus proof complexity. nameOfConference

DOI: doi

QMRO: qmroHref
• Riis S (2008). On the asymptotic Nullstellensatz and Polynomial calculus proof complexity. nameOfConference

QMRO: qmroHref
• RIIS SM (2007). "Graph Entropy, Network Coding and Guessing games". nameOfConference

DOI: doi

• Riis S (2007). Reversible and irreversible information networks. nameOfConference

QMRO: qmroHref
• Riis S (2007). Information flows, graphs and their guessing numbers. nameOfConference

QMRO: qmroHref
• Riis S (2006). Information flows, graphs and their guessing numbers. nameOfConference

QMRO: qmroHref
• Riis S, Ahlswede R (2006). Problems in network coding and error correcting codes appended by a draft version of S Riis "utilising public information in network coding". nameOfConference

QMRO: qmroHref
• RIIS SM (2004). Linear versus non-linear Boolean functions in Network Flow. 38th Annual Conference on Information Sciences and Systems (CISS)

DOI: doi

QMRO: qmroHref
• Dantchev SS, Riis S (2003). On Relativisation and Complexity Gap.. nameOfConference

DOI: doi

QMRO: qmroHref
• Dantchev S, Riis S (2003). On relativisation and complexity gap for resolution-based proof systems. nameOfConference

QMRO: qmroHref
• Riis S, Sitharam M (2001). Uniformly generated submodules of permutation modules - Over fields of characteristic 0. nameOfConference

QMRO: qmroHref
• Hägele K, Dúnlaing CÓ, Riis S (2001). The complexity of scheduling TV commercials. nameOfConference

QMRO: qmroHref
• Dantchev S, Riis S (2001). "Planar" tautologies hard for Resolution. nameOfConference

QMRO: qmroHref
• Riis S (2001). A complexity gap for tree resolution. nameOfConference

QMRO: qmroHref
• Dantchev S, Riis S (publicationYear). A Tough Nut for Tree Resolution. nameOfConference

QMRO: qmroHref
• Jensen KJ, Riis S (2000). Self-organizing letter code-book for text-to-phoneme neural network model. nameOfConference

DOI: doi

QMRO: qmroHref
• Dantchev S, Riis S (2000). Tree resolution proofs of the weak Pigeon-Hole Principle. nameOfConference

QMRO: qmroHref
• Riis S (publicationYear). A Complexity Gap for Tree-Resolution. nameOfConference

QMRO: qmroHref
• Riis S, Sitharam M (publicationYear). Uniformly Generated Submodules of Permutation Modules. nameOfConference

QMRO: qmroHref
• Riis S, Sitharam M (publicationYear). Generating Hard Tautologies Using Predicate Logic and the Symmetric Group. nameOfConference

QMRO: qmroHref
• Riis S (1997). Count(ifq) does not imply Count(ifp). nameOfConference

QMRO: qmroHref
• Andersson A, Miltersen PB, Riis S et al. (publicationYear). Dictionaries on AC^0 RAMs: Query Time Theta(√log n/log log n) is Necessary and Sufficient. nameOfConference

QMRO: qmroHref
• Riis S (1997). Bootstrapping the primitive recursive functions by only 27 colors. nameOfConference

QMRO: qmroHref
• Riis S (1997). Count(\$\$q\$\$) versus the pigeon-hole principle. nameOfConference

QMRO: qmroHref
• Andersson A, Miltersen PB, Riis S et al. (1996). Static dictionaries on AC0 RAMs: Query time Θ(√log n/log log n) is necessary and sufficient. nameOfConference

DOI: doi

QMRO: qmroHref
• Riis S (publicationYear). A Fractal which violates the Axiom of Determinacy. nameOfConference

QMRO: qmroHref
• Riis S (publicationYear). Bootstrapping the Primitive Recursive Functions by 47 Colors. nameOfConference

QMRO: qmroHref
• Riis S (publicationYear). Count(q) versus the Pigeon-Hole Principle. nameOfConference

QMRO: qmroHref
• Riis S (publicationYear). Finitisation in Bounded Arithmetic. nameOfConference

QMRO: qmroHref
• Riis S (publicationYear). Count(q) does not imply Count(p). nameOfConference

QMRO: qmroHref