Department of Computer Science
Queen Mary, University of London
London E1 4NS
UK
Phone: +44 020-7882 7611
Fax: +44 020-7882 3159
Email:smriis@dcs.qmul.ac.uk
I am a Reader in Computer Science. My PhD thesis (DPhil in Mathematics
from the University of Oxford, UK), concerns Independence in Bounded Arithmetic.
During 1994 I was a Research Assistant Professor at BRICS, Aarhus Denmark.
Here I continued my work in Bounded Arithmetic.
During 1995 I was attached to The Hebrew University in Jerusalem where
I worked on Complexity and Mathematical Logic.
In 1996 I was attached to The University of Leeds working
on Proof theory as well as decidability and undecidability in dynamic
systems. I have also had longer visits at the University of Lund,
the University of Copenhagen as well as DIMACS (Rutgers), New Jersey
USA and Kent State University, Ohio USA. I won a fellowship to visit
the Fields Institute in Toronto, during the 1998-theme in Complexity
Theory. In 1999 I returned to BRICS, Aarhus Denmark. I was
appointed at Queen Mary, University of London September 2000.
Research Interests: Mathematical logic including Bounded Arithmetic and Complexity Theory. My research includes Complexity Theory, non-standard models, Representation Theory and Algebra, Network Coding and Information Theory.
Current Students: PhD students Sun Yun as well as a constantly changing number of Advanced MSc, MSc and BSC students
Former PhD Students: Stefan Dantchev (1998-2001), Taoyang Wu (2004-2009)
Teaching , Supervising and coaching
Recearch: Online publications:
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. "Digital Information is not an Ordinary Commodity" Abstract (2009)
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
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.
Riis, S. "Linear versus non-linear Boolean functions in Network Flow" , appears in the Proceedings of CISS 2004
Riis, S. "A complexity gap for tree-resolution" Computational Complexity 10 (2001) 179-209
Riis, S., Sitharam, M. "Uniformly Generated Submodules of Permutation Modules". Journal and of Pure and Applied algebra 160 (2001) 285-318
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
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
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
Riis, S. "Count(q) does not imply Count(p)" Preprint. Journal version appears in Annals of Pure and Applied Logic, 90(1-3): (1997) 1-56
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. "Count(q) versus the pigeon-hole principle" The Journal version of the paper appear in 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
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