Publications of Matthias Krause

Please note

• The only criterion for the order in which co-authors appear is the alphabetic order of their family names

Papers for Qualification

• Matthias Krause: Exponentielle untere Schranken für one-time-only Branching Programme. Master Thesis, Humboldt University at Berlin, 1986
• Matthias Krause: Untere Schranken für Berechnungen durch Verzweigungsprogramme. PhD Thesis, Humboldt University at Berlin, 1988
• Matthias Krause: Zur Berechnung Boolescher Funktionen durch Branching Programme und Schaltkreise kleiner Tiefe. Habilitation Thesis, Dortmund University, 1992

Conference Papers

• Matthias Krause, Christoph Meinel, Stephan Waack: Separating the Eraser Turing Machine Classes L, NL, coNL, and AL=P. Proceedings of the 13th Annual Conference on Mathematical Foundations of Computer Science (MFCS) 1988, Lecture Notes in Computer Science 324, 405-414
• Matthias Krause, Christoph Meinel, Stephan Waack: Separating complexity classes related to certain input-oblivious, logarithmic space bounded Turing machines. Proceedings of the 4th Annual IEEE Conference on Structure in Complexity Theory 1989, 240-259
• Matthias Krause, Stephan Waack: On oblivious branching programs of linear length. Proceedings of the 7th Conference on Fundamentals of Computational Theory (FCT) 1989, Lecture Notes in Computer Science 380, 287-297
• Matthias Krause, Christoph Meinel, Stephan Waack: Separating complexity classes related to certain restricted logarithmic space bounded Turing machines. Proceedings of the IFIP Congress 1989, Information Processing 89, 287--292
• Matthias Krause: Separating Parity-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, Lecture Notes in Computer Science 452, 385--392
• Matthias Krause: Geometric arguments yield better bounds for threshold circuits and distributed computing. Proceedings of the 6th Annual IEEE Conference Structure in Complexity Theory 1991, 314-321
• Matthias Krause, Stephan Waack: Variation ranks of communication matrices and lower bounds for depth two circuits having symmetric gates with unbounded fan-in. Proceedings of the 32th Annual IEEE Symposium Foundation of Computer Science (FOCS) 1991, 777-782
• Carsten Damm, Matthias Krause, Christoph Meinel, Stephan Waack: Separating counting communication complexity classes. Proceedings of the 9th Annual Symposium on Theoretical Aspects of Computer Science (STACS) 1992, Lecture Notes in Computer Science 577, 281-189
• Matthias Krause, Pavel Pudlak: On the computational power of threshold circuits with MOD gates. Proceedings of the 26th Annual ACM Symposium on Theory of Computing (STOC) 1994, 48-57
• Matthias Krause: On realizing iterated multiplication by small depth threshold circuits. Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science (STACS) 1995, Lecture Notes in Computer Science 900, 83-94
• Matthias Krause, Pavel Pudlak: On computing Boolean functions by sparse real polynomials. Proceedings of the 36th Annual IEEE Symposium Foundation of Computer Science (FOCS) 1995, 682-691
• Thomas Hofmeister, Matthias Krause, Hans-Ulrich Simon: Contrast optimal k-out-of-n secret sharing schemes in visual cryptography Proceedings of the Third Annual International Computing and Combinatorics Conference (COCOON) 1997, Lecture Notes in Computer Science, 176-185
• Matthias Krause, Petr Savicky, Ingo Wegener: Approximations by OBDDs and the variable ordering problem. Proceedings of the 26th Annual International Conference on Automata, Languages, and Programming (ICALP) 1999, Lecture Notes in Computer Science 1644, 493-502
• Matthias Krause, Hans-Ulrich Simon: On contrast optimal secret sharing schemes in visual cryptography: determining the optimal contrast exactly. Proceedings of the Annual Conference Latin American Theoretical INformatics (LATIN) 2000, Lecture Notes in Computer Science 1776, 280-291
• Matthias Krause, Stefan Lucks: On the Minimal Hardware Complexity of Pseudorandom Function Generators. Proceedings of the 18th Annual Symposium of Theoretical Aspects of Computer Science (STACS), 2001, Lecture Notes in Computer Science 2010, 419-430
• Matthias Krause, Stefan Lucks, Erik Zenner: Improved Cryptananlysis of the Self-Shrinking Generator. To appear in the Proceedings of the 6th Australasian Conference on Information Security and Privacy (ACIPS 2001), Lecture Notes in Computer Science 2119, 21-35
• Jürgen Forster, Matthias Krause, Satyanarajana V. Lokam, Rustam Mubarakzjanov, Niels Schmitt, Hans U. Simon: Relations Between Communication Complexity, Linear Arrangements, and Computational Complexity. To appear in the Proceedings of the Conference Foundation of Software Technology and Theoretical Computer Science (FSTCS2001), 2001, Lecture Notes in Computer Science 2245, 171-182
• Matthias Krause: On the Computational Power of Boolean Decision Lists. To appear in the Proceedings of the 19th Annual Symposium of Theoretical Aspects of Computer Science (STACS), 2002
• Matthias Krause: BDD-based Cryptanalysis of Keystream Generators. To appear in the Proceedings of EUROCRYPT 2002 For a preliminary version see Report 2001/092 in the Cryptology ePrint Archive, http://eprint.iacr.org/curr/

Journal Papers

• Matthias Krause: Exponential lower bounds on the complexity of real-time and local branching programs. Journal Information, Processing and Cybernetics (EIK) 24-3, 1988, 99-111
• Matthias Krause: Lower bounds for depth-restricted branching programs. Information and Computation, 91-1, 1991, 1-14
• Matthias Krause, Christoph Meinel, Stephan Waack: Separating the eraser Turing machine classes L, NL, coNL, AL=P. Theoretical Computer Science 86, 1991, Seiten 267-275
• Matthias Krause, Christoph Meinel, Stephan Waack: Separating complexity classes related to certain input-oblivious, logarithmic space bounded Turing machines. RAIRO, Informatique Theoretique et Applications (Theoretical Informatics and Applications) 26-4, 1992, 345--362
• Matthias Krause, Stephan Waack: On oblivious branching programs of linear length. Information and Computation, 94-2, 1991, 232-249.
• Juraj Hromkovic, Matthias Krause, Christoph Meinel, Stephan Waack: Branching programs provide lower bounds on the area of multilective deterministic and nondeterministic VLSI circuits. Information and Computation 96-2, 1992, 168-178
• Matthias Krause: Separating Parity-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), 26-6, 1992, 507--522
• Carsten Damm, Matthias Krause, Christoph Meinel, Stephan Waack: Separating Oblivious Linear Length MOD-p-Branching Program Classes. Journal of Information Processing and Cybernetics 30-2, 1994, 63--76
• Matthias Krause: Geometric arguments yield better bounds for threshold circuits and distributed computing. Theoretical Computer Science 156, 1996, 99-117
• Matthias Krause, Stephan Waack: Variation ranks of communication matrices and lower bounds for depth two circuits having symmetric gates with unbounded fan-in. Mathematical System Theory 28, 1995, 553-564.
• Matthias Krause, Pavel Pudlak: On the computational power of depth-2 circuits with threshold and modulo gates. Theoretical Computer Science 174, 1997, 137-156
• Matthias Krause, Pavel Pudlak: Computing Boolean functions by polynomials and threshold circuits. Journal of Computational Complexity 7, 1998, 346-370
• Thomas Hofmeister, Matthias Krause, Hans U. Simon: Optimal k out of n secret sharing schemes in visual cryptography. Theoretical Computer Science 240, 2000, 471-485
• Matthias Krause, Petr Savicky, Ingo Wegener: On the influence of the variable ordering for algorithmic learning using OBDDs. submitted to the Journal Information und Computation
• Matthias Krause, Hans U. Simon: On contrast optimal secret sharing schemes in visual cryptography. submitted to the SIAM Journal on Discrete Mathematics
• Matthias Krause, Stefan Lucks: On the Minimal Hardware Complexity of Pseudorandom Function Generators. submitted to the Journal of Computational Complexity