Prof. Dr. Matthias Krause

Prof. Dr. Matthias Krause

Lehr­stuhl für Theoretische Informatik
University of Mannheim
Fakultät für Wirtschafts­informatik und Wirtschafts­mathematik
B 6, 26 – Room B 2.02
68159 Mannheim
  • Lebenslauf

    1960 Born in Jena
    1967-1975 Primary and Secondary School in Jena and Potsdam
    1975-1979 High School in Potsdam
    1979 Abitur
    1979-1981 Military Service
    1981-1986 Studies of Mathematics at the Humboldt University Berlin
    1986 Diploma thesis
    1986-1988 PhD student in the Theoretical Computer Science Group of Lothar Budach at the Math Department of the Humboldt University Berlin and in the group of Oleg B. Lupanov at the MechMath Department of the Moscow State University
    1988 PhD thesis
    1988-1991 Research and Teaching Assistent in the Theoretical Computer Science Group of Christoph Meinel at the Computer Science Department of the Humboldt University Berlin
    1991-1993 Research and Teaching Assistent in the Theoretical Computer Science Group of Ingo Wegener at the Computer Science Department of the University of Dortmund
    1993 Habilitation thesis
    1993-1996 Lecturer (C2) at the Computer Science Department of the University of Dortmund
    1995-1996 Professor (Substitute) for Theoretical Computer Science at the University of Paderborn
    1996-2005 Associate Professor for Theoretical Computer Science at the University of Mannheim
    1997 Offer for a Professorship at the University of Padernborn (refused)
    1998 Offer for a Professorship at the University of Trier (refused)
    2004 Offer for a Professorship at the Universität der Bundes­wehr in Munich (refused)
    since 2005 Full Professor for Theoretical Computer Science at the University of Mannheim
    2005-2008 Dean of the Faculty of Mathematics and Informatics
    since 2010 Prorektor of the University of Mannheim
    since 1997 living in Mannheim
      married, three daughters
  • Publikationen

    Theses

    • Zur Berechnung Boolescher Funktionen durch Branching Programme und Schaltkreise kleiner Tiefe (in German) Habilitation Thesis, University of Dortmund, 1992
      [bibtex]
    • Untere Schranken für Berechnungen durch Verzweigungs­programme (in German), PhD Thesis, Humboldt University Berlin, 1988
      [bibtex]
    • Exponentielle untere Schranken für one-time-only Branching Programme Diploma Thesis, Humboldt University Berlin, 1986
      [bibtex]

     

    Conference Papers

    • The Preimage Security of Double-Block-Length Compression Functions (with F. Armknecht, E. Fleischmann, J. Lee, M. Stam, J. Steinberger), ASIACRYPT - 17th Annual International Conference on the Theory and Application of Cryptology and Information Security, 2011
      [PDF] [bibtex]
    • The Cryptographic Power of Random Selection (with Matthias Hamann), Selected Areas in Cryptography (SAC 2011), 2011
      [PDF] [bibtex]
    • More on the Security of Linear RFID Authentication Protocols (with Dirk Stegemann), Proceedings of the 16th Annual International Workshop on Selected Areas in Cryptography (SAC 2009), LNCS 5867, pp. 182-196, 2009
      [PDF] [bibtex]
    • Constructing Single- and Multi-Output Boolean Functions with Maximal Algebraic Immunity (with Frederik Armknecht), Proceedings of the 33th Annual International Conference on Automata, Languages, and Programming (ICALP 2006), LNCS 4051, pp. 180-191, 2006
      [PDF] [bibtex]
    • Reducing the Space Complexity of BDD-based Attacks on Keystream Generators (with Dirk Stegemann), Proceedings of the 13th Fast Software Encryption Workshop (FSE 2006), LNCS 4047, pp. 173-178, 2006
      [PDF] [bibtex]
    • Design Principles for Combiners With Memory, (with Frederik Armknecht and Dirk Stegemann), Proceedings of the 6th International Conference on Cryptology in India (INDOCRYPT 2005), LNCS 3739, pp. 104-117, 2005
      [PDF] [bibtex]
    • Algebraic Attacks on Combiners with Memory (with Frederik Armknecht), Proceedings of the 23rd Annual International Cryptology Conference (CRYPTO 2003), LNCS 2729, pp. 162-173, 2003
      [PDF] [bibtex]
    • BDD-based Cryptanalysis of Keystream Generators, Proceedings Advances in Cryptology (EUROCRYPT 2002), LNCS 2332, pp. 222-237, 2002
      [PDF] [bibtex]
    • On the Computational Power of Boolean Decision Lists, Proceedings des 19th Annual Symposium of Theoretical Aspects of Computer Science (STACS 2002), LNCS 2285, pp. 372-383, 2002
      http://www.springerlink.com/content/rg0gncxjd02fhalr/fulltext.pdf [bibtex]
    • Relations Between Communication Complexity, Linear Arrangements, and Computational Complexity (with Jürgen Forster, Satyanarajana V. Lokam, Rustam Mubarakzjanov, Niels Schmitt, Hans U. Simon), Proceedings of the Conference Foundation of Software Technology and Theoretical Computer Science (FSTCS 2001), LNCS 2245, pp. 171-182, 2001
      [PDF] [bibtex]
    • Improved Cryptananlysis of the Self-Shrinking Generator (with Stefan Lucks and Erik Zenner), Proceedings des 6th Australasian Conference on Information Security and Privacy (ACIPS 2001), LNCS 2119, pp. 21-35, 2001
      [PDF] [bibtex]
    • On the Minimal Hardware Complexity of Pseudorandom Function Generators (with Stefan Lucks), Proceedings of the 18th Symposium of Theoretical Aspects of Computer Science (STACS 2001), LNCS 2010, pp. 419-430, 2001
      [PDF] [bibtex]
    • On contrast optimal secret sharing schemes in visual cryptography: determining the optimal contrast exactly (with Hans U. Simon), Proceedings of the Annual Conference Latin American Theoretical Informatics (LATIN 2000), LNCS 1776, pp. 280-291, 2000
      [PDF] [bibtex]
    • Approximations by OBDDs and the variable ordering problem (with Petr Savicky and Ingo Wegener), Proceedings of the 26th Annual International Conference on Automata, Languages, and Programming (ICALP 1999), LNCS 1644, pp. 493-502, 1999
      [PDF] [bibtex]
    • Contrast-optimal out of secret sharing schemes in visual cryptography (with Hans U. Simon and Thomas Hofmeister), Proceedings of the Third Annual International Computing and Combinatorics Conference (COCOON 1997), LNCS 1276, pp. 176-185, 1997
      [PDF] [bibtex]
    • On computing Boolean functions by sparse real polynomials (with Pavel Pudlák), Proceedings of the 36th Annual IEEE Symposium Foundation of Computer Science (FOCS 1995), pp. 682-691, IEEE Computer Society, 1995
      [PDF] [bibtex]
    • On realizing iterated multiplication by small depth threshold circuits, Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science (STACS 1995), LNCS 900, pp. 83-94, 1995
      [PDF] [bibtex]
    • On the computational power of threshold circuits with MOD gates (with Pavel Pudlák), Proceedings of the 26th Annual ACM Symposium on Theory of Computing (STOC 1994), pp. 48-57, ACM, 1994
      [PDF] [bibtex]
    • Separating counting communication complexity classes (with Christoph Meinel, Carsten Damm, and Stephan Waack), Proceedings of the 9th Annual Symposium on Theoretical Aspects of Computer Science (STACS 1992), LNCS 577, pp. 281-189, 1992
      [PDF] [bibtex]
    • Variation ranks of communication matrices and lower bounds for depth two circuits having symmetric gates with unbounded fan-in (with Stephan Waack), Proceedings of the 32th Annual IEEE Symposium Foundation of Computer Science (FOCS 1991), pp. 777-782, IEEE Computer Society, 1991
      [PDF] [bibtex]
    • Geometric arguments yield better bounds for threshold circuits and distributed computing, Proceedings of the 6th Annual IEEE Conference Structure in Complexity Theory 1991, pp. 314-321, IEEE Computer Society, 1991
      [PDF] [bibtex]
    • Separating from L, NL, co-NL, and AL=P for oblivious Turing machines of linear access time, Proceedings of the 15th Annual Conference of Mathematical Foundations of Computer Science (MFCS 1990), LNCS 452, pp. 385-392, 1990
      [PDF] [bibtex]
    • Separating complexity classes related to certain restricted logarithmic space bounded Turing machines (with Christoph Meinel and Stephan Waack), Proceedings of the IFIP Congress 1989, Information Processing 89, pp. 287-292, 1989
      [PDF] [bibtex]
    • On oblivious branching programs of linear length (with Stephan Waack), Proceedings of the 7th Conference on Fundamentals of Computational Theory (FCT 1989), LNCS 380, pp. 287-297, 1989
      [PDF] [bibtex]
    • Separating complexity classes related to certain input-oblivious, logarithmic space bounded Turing machines (with Christoph Meinel and Stephan Waack), Proceedings of the 4th Annual IEEE Conference on Structure in Complexity Theory 1989, pp. 240-259, IEEE Computer Society, 1989
      [PDF] [bibtex]
    • Separating the eraser Turing machine classes (with Christoph Meinel and Stephan Waack), Proceedings of the 13th Annual Conference on Mathematical Foundations of Computer Science (MFCS 1988), LNCS 324, pp. 405-414, 1988
      [PDF] [bibtex]

     

    Book Chapters

    • Circuit complexity (with Ingo Wegener), to appear in Monography on Boolean Functions Vol. II (Eds. Y. Crama, P. Hammer)
      [bibtex]

     

    Journal papers

    • OBDD-based Cryptanalysis of Oblivious Keystream Generators, TOCS-Theory of Computing Systems, Vol. 40, Nr. 1, pp. 101-121, Springer, 2007
      [PDF] [bibtex]
    • On the Computational Power of Boolean Decision Lists, Computational Complexity, Vol. 14, pp. 362-375, 2005
      [PDF] [bibtex]
    • On the influence of the variable ordering for algorithmic learning using OBDDs (with Petr Savicky and Ingo Wegener), Information und Computation, Vol. 201, pp. 160-177, 2005
      [PDF] [bibtex]
    • On contrast optimal secret sharing schemes in visual cryptography (with Hans U. Simon), Combinatorics, Probability and Computing, Vol. 12, pp. 285-299, 2003
      [PDF] [bibtex]
    • On Pseudorandom Functions in and Cryptographic Limitations of Proving Lower Bounds (with Stefan Lucks), Computational Complexity, Vol. 10, pp. 297-313, 2001
      [PDF] [bibtex]
    • Optimal out of secret sharing schemes in visual cryptography (with Thomas Hofmeister and Hans U. Simon), Theoretical Computer Science, Vol. 240, pp. 471-485, 2000
      [PDF] [bibtex]
    • Computing Boolean functions by polynomials and threshold circuits (with Pavel Pudlák), Journal of Computational Complexity, Vol. 7, pp. 346-370, 1998
      [PDF] [bibtex]
    • On the computational power of depth-2 circuits with threshold and modulo gates (with Pavel Pudlák), Theoretical Computer Science, Vol. 174, pp. 137-156, 1997
      [PDF] [bibtex]
    • Geometric arguments yield better bounds for threshold circuits and distributed computing, Theoretical Computer Science, Vol. 156, pp. 99-117, 1996
      [PDF] [bibtex]
    • Variation ranks of communication matrices and lower bounds for depth two circuits having symmetric gates with unbounded fan-in (with Stephan Waack), Mathematical System Theory, Vol. 28, pp. 553-564, 1995
      [PDF] [bibtex]
    • Separating Oblivious Linear Length -Branching Program Classes (with Christoph Meinel, Carsten Damm, and Stephan Waack), Journal of Information Processing and Cybernetics, Vol. 30, Nr. 2, pp. 63-76, 1994
      [bibtex]
    • Separating from L, NL, co-NL, and AL=P for oblivious Turing machines of linear access timeRAIRO, Informatique Theoretique et Applications (Theoretical Informatics and Applications), Vol. 26, Nr. 6, pp. 507-522, 1992
      [PDF] [bibtex]
    • Branching programs provide lower bounds on the area of multilective deterministic and nondeterministic VLSI circuits (with Juraj Hromkovic, Christoph Meinel, and Stephan Waack) Information and Computation, Vol. 96, Nr. 2, pp. 168-178, 1992
      [bibtex]
    • Separating complexity classes related to certain input-oblivious, logarithmic space bounded Turing machines (with Christoph Meinel and Stephan Waack) RAIRO, Informatique Theoretique et Applications (Theoretical Informatics and Applications), Vol. 26, Nr. 4, pp. 345-362, 1992
      [PDF] [bibtex]
    • On oblivious branching programs of linear length (with Stephan Waack) Information and Computation, Vol. 94, Nr. 2, pp. 232-249, 1991
      [PDF] [bibtex]
    • Separating the eraser Turing machine classes (with Christoph Meinel and Stephan Waack) Theoretical Computer Science, Vol. 86, pp. 267-275, 1991
      [PDF] [bibtex]
    • Lower bounds for depth-restricted branching programsInformation and Computation, Vol. 91, Nr. 1, pp. 1-14, 1991
      [bibtex]
    • Exponential lower bounds on the complexity of real-time and local branching programs, Information, Processing and Cybernetics (EIK), Vol. 24, Nr. 3, pp. 99-111, 1988
      [bibtex]