It is impossible for me to read contemporary mathematicians who, instead of saying, "Petya washed his hands", write: "There is a t _1< 0 such that the image of t_1 under the natural mapping t_1 -> Petya(t_1) belongs to the set of dirty hands, and a t_2, t_1

Arnol'd on reading mathematics

Søren Riis' Home Page

School of Electronic Engineering and Computer Science
Queen Mary, University of London
London E1 4NS

Phone: +44 020-7882 7611
Fax: +44 020-7882 3159
Email:soren.riis at

Title: Reader
Thesis: DPhil in Mathematics from the University of Oxford, UK with the title "Independence in Bounded Arithmetic"
Research Interests: Mathematical Logic, Bounded Arithmetic, Complexity Theory, Representation Theory and Algebra, Network Coding and Information Theory.
Current PhD students: Nhat Anh Dang (2011 - ), Sune Jakobsen (2012 - ) (shared with Peter Keevash) Howard Manning (2011 - ) (Second supervisor with Peter McOwan).
Former Post Doctorial Students: Maximilien Gadouleau (2010-2012), Antonia Katzouraki (2010-2011), Emil Vaughan (2011-2012), Rahil Baber (2012)
Former PhD Students: Stefan Dantchev (1998-2001), Taoyang Wu (2004-2009), Sun Yun (2004-2009), John Fabien (2009-2012) (second supervisor with Mark Jerum)
Teaching , Supervising and coaching

Online papers and preprints by topic:

Network Coding (link to "Network Coding Seminars")

Baber, R., Christofides, D., Dang, A,D., Riis, S., Vaugh, E,R. "Multiple Unicasts, Graph Guessing Games and non-Shannon Information Inequalities" preprint

Riis, S., Gadouleau, M. "Max-Flow Min-Cut Theorems for Multi-User Communication Networks" ArXiv December 2010

Gadouleau, M., Riis,S. "Graph theoretical constructions for Graph Entropy and Network Coding Based Communications" ArXiv September 2010

Riis, S. "Graph Entropy, Network Coding and Guessing games" ArXiv November 2007

Riis, S. "Information flows, graphs and their guessing numbers" Electronic Journal of Combinatorics, R44 p1-17, 2006

Riis, S. "Reversible and Irreversible information networks" IEEE Transactions on Information Theory Vol53 No.11 November 2007p 4339-4349

Wu, T., Cameron, P., Riis, S. " On the guessing number of shift graphs. J. Discrete Algorithms 7(2): 220-226 (2009)"

Riis, S., Ahlswede, U. "Problems in Network coding and error correcting codes" , appear in NetCod the first Workshop on Network Coding, Theory, and Applications , April 2005, Trento, Italy. Appears also General Theory of Information Transfer and Combinatorics Lecture Notes in Computer Science, 2006, Volume 4123/2006, 861-865, DOI: 10.1007/11889342_56

Riis, S. "Utilising public information in Network Coding" in General Theory of Information Transfer and Combinatorics Lecture Notes in Computer Science, 2006, Volume 4123/2006, 866-897, DOI: 10.1007/11889342_56

Riis, S. "Linear versus non-linear Boolean functions in Network Flow" , appears in the Proceedings of CISS 2004

Algebraic proof complexity

Riis, S. "On the asymptotic Nullstellensatz and Polynomial Calculus proof complexity" LICS 2008 A much longer and more detailed technical report of the paper can be found at ECCC TR09-014 .

Riis, S. "A dimension Theorem for Permutation Modules" (preprint 2005)

Riis, S., Sitharam, M. "Uniformly Generated Submodules of Permutation Modules" Journal and of Pure and Applied algebra 160 (2001) 285-318

Riis, S., Sitharam, M. "Generating hard tautologies using logic and the symmetric group" Logic Journal of the IGPL, Oxford University Press, vol 8. No 6. (2000) 787-795

Propositional proof Complexity

Riis, S. "A complexity gap for tree-resolution" Computational Complexity 10 (2001) 179-209

Dantchev, S., Riis, S. "Planar tautologies hard for Resolution" In the 42th annual FOCS IEEE, October (2001)

Dantchev, S., Riis, S. "On Complexity gaps for Resolution-based proof systems" In The 12th Annual Conference of the EACSL, Computer Science Logic, LNCS 2803, Springer, August (2003) 142-154

Dantchev, S., Riis, S. "Tree Resolution proofs of the Weak Pigeon-Hole Principle" In the 16th annual IEEE Conference on Computational Complexity, IEEE June (2001) 69-75

Bounded Arithmetic

Riis, S. "Count(q) does not imply Count(p)" Annals of Pure and Applied Logic, 90(1-3): (1997) 1-56

Riis, S. "Count(q) versus the pigeon-hole principle" Arch. Math. Logic 36 no. 3 (1997) 157-188

Beame, P., Riis, S. "More on the Relative Strength of Counting Principles" Appear in: DIMACS Series in Discrete Mathematics and Theoretical Computer Science Vol. 39, (1998) 13-35

Riis, S. "Finitisation in Bounded Arithmetic" : Slightly extended version of: Making infinite structures finite in models of Second Order Bounded Arithmetic.In: Arithmetic, proof theory and computational complexity, Oxford University Press (1993) 289-319


Hägele, K., Dúnlaing, C., Riis, S. "The complexity of scheduling TV commercials" Electronic Notes in Theoretical Computer Science Volume 40, March 2001, Pages 162-185 MFCSIT2000, The First Irish Conference on the Mathematical Foundations of Computer Science and Information Technology

Andersson, A., Miltersen, P.B., Riis, S., Thorup, M. "Dictionaries on RAMs: Query Time \theta(sqrt(logn/loglogn) is Necessary and Sufficient" In STOCS (1996)

Riis, S. "Bootstrapping the Primitive Recursive Functions by 47 Colours" : Appear as RS-94-25 in the BRICS rapport series. Premilinary version of the Journal version: "Bootstrapping the Primitive Recursive Functions by only 27 Colours" appear in Discrete Mathematics Vol 169 no1-3 (1997) 269-272