Dr Soren RiisReaderEmail: s.riis@qmul.ac.ukTelephone: +44 20 7882 6284Room Number: Peter Landin, CS 420Website: http://www.eecs.qmul.ac.uk/~smriisOffice Hours: Thursday 11:30-13:30, Wednesday 13:00-15:00TeachingResearchPublicationsTeachingComputability, 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).ResearchResearch Interests:Mathematical Logic, Complexity Theory, Proof Complexity, Algebraic Proof Complexity, Information Theory, Network Coding, Combinatorics and Reinforced Learning.Publications Markström K, Riis S, Zhou B (2024). Arrow's single peaked domains, richness, and domains for plurality and the Borda count.. nameOfConference DOI: doi QMRO: qmroHref Karpov A, Markström K, Riis S et al. (2024). Local Diversity of Condorcet Domains.. nameOfConference DOI: doi QMRO: qmroHref Leedham-Green C, Markström K, Riis S (2024). The largest Condorcet domain on 8 alternatives. nameOfConference DOI: 10.1007/s00355-023-01481-3 QMRO: https://qmro.qmul.ac.uk/xmlui/handle/123456789/90709 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 DOI: 10.1016/j.ic.2019.03.004 QMRO: https://uat2-qmro.qmul.ac.uk/xmlui/handle/123456789/56598 Baber R, Christofides D, Dang AN et al. (2017). Graph Guessing Games and Non-Shannon Information Inequalities. nameOfConference DOI: 10.1109/tit.2016.2628819 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 DOI: 10.48550/arxiv.1507.01249 QMRO: https://uat2-qmro.qmul.ac.uk/xmlui/handle/123456789/11053 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 DOI: 10.1145/2867731.2867747 QMRO: qmroHref Baber R, Christofides D, Dang AN et al. (2014). Graph Guessing Games and non-Shannon Information Inequalities. nameOfConference DOI: 10.1109/TIT.2016.2628819 QMRO: https://uat2-qmro.qmul.ac.uk/xmlui/handle/123456789/11052 Cameron PJ, Dang AN, Riis S (2014). Guessing Games on Triangle-free Graphs. nameOfConference DOI: 10.37236/4731 QMRO: https://uat2-qmro.qmul.ac.uk/xmlui/handle/123456789/11893 Gadouleau M, Richard A, Riis S (2014). Fixed points of Boolean networks, guessing graphs, and coding theory. nameOfConference DOI: 10.1137/140988358 QMRO: https://uat2-qmro.qmul.ac.uk/xmlui/handle/123456789/25117 Riis S (2014). What makes a chess program original? Revisiting the Rybka case. nameOfConference DOI: 10.1016/j.entcom.2014.04.004 QMRO: https://uat2-qmro.qmul.ac.uk/xmlui/handle/123456789/11880 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) 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 Gadouleau M, Riis S (2011). 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 Cameron PJ, Gadouleau M, Riis S (2011). Combinatorial representations. nameOfConference DOI: 10.1016/j.jcta.2012.12.002 QMRO: https://uat2-qmro.qmul.ac.uk/xmlui/handle/123456789/3153 Riis S, Gadouleau M (2011). A Dispersion Theorem for Communication Networks Based on Term Sets. 2011 IEEE International Symposium on Information Theory Proceedings DOI: 10.1109/isit.2011.6034198 QMRO: qmroHref 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 (2011). Max-Flow Min-Cut Theorem for Renyi Entropy in Communication Networks. nameOfConference DOI: 10.1109/ISIT.2011.6034200 QMRO: qmroHref Riis S, Gadouleau M (2010). Max-Flow Min-Cut Theorems for Multi-User Communication Networks. nameOfConference DOI: doi QMRO: https://uat2-qmro.qmul.ac.uk/xmlui/handle/123456789/3199 Gadouleau M, Riis S (2010). Graph-theoretical Constructions for Graph Entropy and Network Coding Based Communications. nameOfConference DOI: 10.1109/TIT.2011.2155618 QMRO: https://uat2-qmro.qmul.ac.uk/xmlui/handle/123456789/22923 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 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://uat2-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 Dantchev S, Riis S (publicationYear). A Tough Nut for Tree Resolution. nameOfConference DOI: 10.7146/brics.v7i10.20137 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 (publicationYear). A Complexity Gap for Tree-Resolution. nameOfConference DOI: 10.7146/brics.v6i29.20098 QMRO: qmroHref Riis S, Sitharam M (publicationYear). Uniformly Generated Submodules of Permutation Modules. nameOfConference DOI: 10.7146/brics.v5i20.19426 QMRO: qmroHref Riis S, Sitharam M (publicationYear). Generating Hard Tautologies Using Predicate Logic and the Symmetric Group. nameOfConference DOI: 10.7146/brics.v5i19.19425 QMRO: qmroHref Riis S (1997). Count(ifq) does not imply Count(ifp). nameOfConference DOI: 10.1016/s0168-0072(97)00029-8 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 DOI: 10.7146/brics.v4i14.21678 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 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 DOI: 10.7146/brics.v1i24.21642 QMRO: qmroHref Riis S (publicationYear). Bootstrapping the Primitive Recursive Functions by 47 Colors. nameOfConference DOI: 10.7146/brics.v1i25.21641 QMRO: qmroHref Riis S (publicationYear). Count(q) versus the Pigeon-Hole Principle. nameOfConference DOI: 10.7146/brics.v1i26.21640 QMRO: qmroHref Riis S (publicationYear). Finitisation in Bounded Arithmetic. nameOfConference DOI: 10.7146/brics.v1i23.21644 QMRO: qmroHref Riis S (publicationYear). Count(q) does not imply Count(p). nameOfConference DOI: 10.7146/brics.v1i21.21646 QMRO: qmroHref