Publications of Matthias Krause

Theses

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

Conference Papers

On the Complexity of a Learning Problem induced by a Lightweight Cryptographic Construction (with Matthias Hamann), submitted, 2010
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
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
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
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
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
BDD-based Cryptanalysis of Keystream Generators, Proceedings Advances in Cryptology (EUROCRYPT 2002), LNCS 2332, pp. 222-237, 2002
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
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
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
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
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
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
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
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
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
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
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
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
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
Separating $\oplus L$ 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
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
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
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
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

Book Chapters

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

Journal papers

OBDD-based Cryptanalysis of Oblivious Keystream Generators, TOCS-Theory of Computing Systems, Vol. 40, Nr. 1, pp. 101-121, Springer, 2007
On the Computational Power of Boolean Decision Lists, Computational Complexity, Vol. 14, pp. 362-375, 2005
On Pseudorandom Functions in and Cryptographic Limitations of Proving Lower Bounds (with Stefan Lucks), Computational Complexity, Vol. 10, pp. 297-313, 2001
On contrast optimal secret sharing schemes in visual cryptography (with Hans U. Simon), Combinatorics, Probability and Computing, Vol. 12, pp. 285-299, 2003
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
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
Computing Boolean functions by polynomials and threshold circuits (with Pavel Pudlák), Journal of Computational Complexity, Vol. 7, pp. 346-370, 1998
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
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
Geometric arguments yield better bounds for threshold circuits and distributed computing, Theoretical Computer Science, Vol. 156, pp. 99-117, 1996
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
Separating $\oplus L$ from L, NL, co-NL, and AL=P for oblivious Turing machines of linear access time RAIRO, Informatique Theoretique et Applications (Theoretical Informatics and Applications), Vol. 26, Nr. 6, pp. 507-522, 1992
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
On oblivious branching programs of linear length (with Stephan Waack) Information and Computation, Vol. 94, Nr. 2, pp. 232-249, 1991
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
Separating the eraser Turing machine classes (with Christoph Meinel and Stephan Waack) Theoretical Computer Science, Vol. 86, pp. 267-275, 1991
Lower bounds for depth-restricted branching programs Information and Computation, Vol. 91, Nr. 1, pp. 1-14, 1991
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