Dr Soren Riis

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:

Publications

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

  
  

  DOI: 10.1016/j.ic.2019.03.004

  
  

  QMRO: https://qmro.qmul.ac.uk/xmlui/handle/123456789/56598
• Baber R, Christofides D, Dang NA et al. (2016). Graph Guessing Games and Non-Shannon Information Inequalities.. nameOfConference

  
  

  DOI: 10.1109/TIT.2016.2628819

  
  

  QMRO: https://qmro.qmul.ac.uk/xmlui/handle/123456789/11052
• Cameron PJ, Dang AN, Riis S (2016). Guessing games on triangle-free graphs. nameOfConference

  
  

  DOI: 10.37236/4731

  
  

  QMRO: https://qmro.qmul.ac.uk/xmlui/handle/123456789/11893
• Riis S, Martin U, Woodhouse N (2015). Ada Lovelace, a scientist in the archives. nameOfConference

  
  

  DOI: 10.1145/2867731.2867747

  
  

  QMRO: qmroHref
• Gadouleau M, Richard A, Riis S (2015). FIXED POINTS OF BOOLEAN NETWORKS, GUESSING GRAPHS, AND CODING THEORY. nameOfConference

  
  

  DOI: 10.1137/140988358

  
  

  QMRO: https://qmro.qmul.ac.uk/xmlui/handle/123456789/25117
• Gadouleau M, Riis S (2015). Memoryless computation: New results, constructions, and extensions. nameOfConference

  
  

  DOI: 10.1016/j.tcs.2014.09.040

  
  

  QMRO: https://qmro.qmul.ac.uk/xmlui/handle/123456789/11879
• Riis S (2014). What makes a chess program original? Revisiting the Rybka case. nameOfConference

  
  

  DOI: 10.1016/j.entcom.2014.04.004

  
  

  QMRO: https://qmro.qmul.ac.uk/xmlui/handle/123456789/11880
• 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)

  
  

  DOI: 10.1109/NetCod.2013.6570823

  
  

  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
• Riis S, Gadouleau M (2011). A dispersion theorem for communication networks based on term sets. nameOfConference

  
  

  DOI: 10.1109/ISIT.2011.6034198

  
  

  QMRO: qmroHref
• RIIS SM, Gadouleau M (2011). Graph theoretical constructions for Graph Entropy and Network Coding Based Communications. nameOfConference

  
  

  DOI: 10.1109/TIT.2011.2155618

  
  

  QMRO: https://qmro.qmul.ac.uk/xmlui/handle/123456789/22923
• Cameron PJ, Gadouleau M, Riis S (2011). Combinatorial representations. nameOfConference

  
  

  DOI: 10.1016/j.jcta.2012.12.002

  
  

  QMRO: https://qmro.qmul.ac.uk/xmlui/handle/123456789/3153
• RIIS SM, Gadouleau M (2011). Network Coding Theorem for Dynamic Communication Networks. Network Coding (NetCod), 2011 International Symposium

  
  

  DOI: 10.1109/ISNETCOD.2011.5979085

  
  

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

  
  

  DOI: doi

  
  

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

  
  

  DOI: 10.1109/ISIT.2011.6034200

  
  

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

  
  

  DOI: doi

  
  

  QMRO: qmroHref
• Gadouleau M, Riis S (2010). Max-Flow Min-Cut Theorems for Communication Networks Based on Equational Logic. nameOfConference

  
  

  DOI: doi

  
  

  QMRO: https://qmro.qmul.ac.uk/xmlui/handle/123456789/3199
• Wu T, Cameron P, Riis S (2009). On the guessing number of shift graphs. nameOfConference

  
  

  DOI: 10.1016/j.jda.2008.09.009

  
  

  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

  
  

  DOI: 10.1109/LICS.2008.30

  
  

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

  
  

  DOI: doi

  
  

  QMRO: https://qmro.qmul.ac.uk/xmlui/handle/123456789/3110
• Riis S (2007). Reversible and irreversible information networks. nameOfConference

  
  

  DOI: 10.1109/TIT.2007.907345

  
  

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

  
  

  DOI: 10.1109/WIOPT.2006.1666516

  
  

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

  
  

  DOI: 10.37236/962

  
  

  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

  
  

  DOI: 10.1007/11889342_56

  
  

  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

  
  

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

  
  

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

  
  

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

  
  

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

  
  

  DOI: 10.1016/S1571-0661(05)80043-X

  
  

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

  
  

  DOI: 10.1109/SFCS.2001.959896

  
  

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

  
  

  DOI: 10.1007/s00037-001-8194-y

  
  

  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

  
  

  DOI: 10.1109/CCC.2001.933873

  
  

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

  
  

  DOI: 10.1016/S0168-0072(97)00029-8

  
  

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

  
  

  DOI: 10.1016/S0012-365X(97)87041-0

  
  

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

  
  

  DOI: 10.1007/s001530050060

  
  

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

  
  

  DOI: doi

  
  

  QMRO: qmroHref