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 |
School of Electronic Engineering and Computer Science
Queen Mary, University of London
London E1 4NS
UK
Phone: +44 020-7882 7611
Fax: +44 020-7882 3159
Email:soren.riis at eecs.qmul.ac.uk
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
Miscellaneous
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