Papers:

Analysis of Algorithms:

• �On the greedy superstring conjecture�, (with M. Weinard), Proceedings of the 23^rd FSTTCS 03, Indien, Lecture Notes in Computer Science 2914, Springer, pp. 387 - 398, (2003).

• �On the performance of the minimal degree heuristic for Gaussian elimination� (with P. Berman), SIAM Journal on Matrix Analysis and Applications 11, pp. 83-88 (1990).

• �On the complexity of approximating the independent set problem� (with P. Berman), Proceedings of the Symposium in Theoretical Aspects of Computer Science (STACS), Lecture Notes in Computer Science 349, Springer, pp. 256 � 268 (1989).

  The final version appears in Information and Computation 96(1), pp. 77-94 (1992).

• �Checking local optimality in constrained quadratic programming is NP-hard� (with P. Pardalos), Operations Research Letters 7(1), pp. 33 � 35 (1988).

Communication Complexity:

• �On multipartition communication complexity�, (with P. Duris, J. Hromkovic, S. Jukna, M. Sauerhoff), Proc. of the 18^th Symposium on Theoretical Aspects of Computer Science (STACS), Lecture Notes in Computer Science Bd. 2010, Springer, pp. 206 � 217 (2001). The final version appears in Information and Computation,  194:1 , 49-75, (2004).

• �Triangle-Freeness Is Hard To Detect�, (with S. Jukna), Combinatorics, Probability & Computing, pp. 549 � 569, (2002).

• �Las Vegas versus determinism for one-way communication complexity, finite automata and polynomial-time computation� (with P. Duris, J. Hromkovic, D.P. Rolim), Proc. of the 14^th Symposium on Theoretical Aspects of Computer Science (STACS), Lecture Notes in Computer Science 1200, Springer, pp. 117 � 128 (1997).

  The final version with the title �On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata� , (coauthor J. Hromokovic), appears in Information and Computation, pp. 284 � 296, (2001).�Nondeterministic communication with a limited number of advice bits�, (with J. Hromkovic), Proc. of the 28^th Annual ACM Symposium on Theory of Computing (STOC), pp. 551 � 560, (1996).

  The final version appears in SIAM Journal of Computing, 33 (1), pp. 43 - 68, (2003).

• �Communication complexity of matrix computation over finite fields� (with J. Chu), Math. Syst. Theory 28(3), pp. 215 � 228, (1995).

• �A comparison of two lower bound methods for communication complexity� (with M. Dietzfelbinger, J. Hromkovic), Proc. of the 19^th International Symposium on Mathematical Foundations of Computer Science (MFCS), pp. 326 � 335, (1994).

  The final version appears in Theoretical Computer Science 168(1), pp. 39 � 51 (1996).

• �Two-tapes are better than one for off-line Turing machines� (with W. Maass, E. Szemeredi), Proceedings of the 19^th Annual ACM Symposium on Theory of Computing (STOC), pp. 94 � 100 (1987).

  The final and extended version (with G. Turan as additional author) appears in Computational Complexity 3(4), pp. 392 � 401 (1993).

• �The complexity of matrix transposition on one-tape off-line Turing machines� (with M. Dietzfelbinger, W. Maass), Theoretical Computer Science 82(1), pp. 113 � 129 (1991).

• �The communication complexity of several problems in matrix computation� (with J. Chu), Proceedings of the 1^st Annual ACM Symposium on Parallel Algorithmus and Architectures (SPAA), Santa Fe, NM, pp. 22 � 31 (1989). The final version appears in Journal of Complexity 7 (4), pp. 395 � 407 (1991).

• �The probabilistic communication complexity of set intersection� (with B. Kalyanasundaram), Proceedings of the 2^nd Structures of Complexity Theory Conference, Cornell, pp. 41 -49 (1987).

  The final version appears in SIAM J. on Discrete Math. 5 , (4), pp. 545 � 557,  (1992).

• �On the power of probabilistic one-tape Turing machines� (with B. Kalyanasundaram), Proceedings of the 24^th Allerton Conference on Communications, Control and Computing, pp. 749-757 (1986).

• �An optimal lover bound for Turing machines with one work tape and a two-way input tape� (with W. Maass). Proceedings of The Structure in Complexity Theory Conference, Lecture Notes in Computer Science 223, Springer, pp. 249-264 (1986).

• �Lower bounds on communication complexity� (with P. Duris, Z. Galil), Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing (STOC), Washington, D.C., pp. 81-91 (1984). The final version appears in Information and Computation, 73(1), pp- 1-22 (1987).

• �Three applications of Kolmogorov-complexity� (with S. Reisch), Proceedings of the 23^rd Annual Symposium on the Foundations of Computer Science (FOCS), pp. 45-52 (1982).

Formal Languages:

• �Regular expressions and NFAs without epsilon-transitions�,  Proceedings of the 23^rd Symposium on Theoretical Aspects of Computer Science (STACS), Lecture Notes in Computer Science, Springer, pp. xx-xx, 2006. (Presentation)

• �NFAs with and without epsilon-transitions�, (with J. Hromkovic), Proceedings of 32^nd International Colloquium on Automata, Languages and Programming (ICALP), Lissabon, Springer, pp. 385-396, (2005).

• �Minimizing nfa�s and regular expression�, (with G. Gramlich),

  Proceedings of the 22^nd Symposium on Theoretical Aspects of Computer Science (STACS),

  Lecture Notes in Computer Science 3404, Springer, pp. 399-411, 2005.

• �On the power of randomized multicounter machines�, (with J. Hromkovic),

  Theoretical Computer Science,  vol. 330 (1), pp. 135-144, 2005.

• �Pushdown automata and multicounter machines, a comparison of computation modes�, (with J. Hromkovic), Proceedings of 30^th International Colloquium on Automata, Languages and Programming (ICALP),, Wien, Springer, pp. 66 - 80, (2003).

• �Nondeterminism versus determinism for two-way finite automata: generalizations of Sipser�s separation�, (with J. Hromkovic), Proceedings of 30^th International Colloquium on Automata, Languages and Programming (ICALP), Wien, Springer, pp. 439 - 451, (2003).

• �On the power of randomized pushdown automata�, (with J. Hromkovic), Proceedings of DLT 2001, Springer, pp. 262 � 271, (2001).

• �Measures of nondeterminism in finite automata�, (with J. Hromkovic, J. Karhum�ki, H. Klauck, S. Seibert), Proc. of 28^th International Colloquium on Automata, Languages and Programming (ICALP), Lecture Notes in Computer Science, Springer, pp. 199 � 210, (2000).

  The final version with the title �Communication complexity method for measuring nondeterminism in finite automata� appears in Information and Computation, pp. 202 � 217, (2002).

• �On the power of Las Vegas II: Two-way finite automata�, (with J. Hromkovic), Proc. of International Colloquium on Automata, Languages and Programming (ICALP), Lecture Notes in Computer Science, Springer, pp. 433 � 443, (1999).The final version appears in Theoretical Computer Science 262(1), pp. 1 � 24, (2001).

Graph-Theoretic Modelling:

• �Rounds versus time for the two person pebble game� (with B. Kalyanasundaram), Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS), Lecture Notes in Computer Science 349, Springer, pp. 517 � 529 (1989). The final version appears in Information and Computation 88 (1), pp. 1 � 17 (1990).

• �On the power of white pebbles� (with B. Kalyanasundaram), Proceedings of the 20^th ACM Symposium on Theory of Computing (STOC), pp. 258 � 266 (1988).

  The final version appears in Combinatorica 11 (2), pp. 157 � 171 (1991).

• �On depth reduction and grates�, Proceedings of the 24^th Annual Symposium on Foundations of Computer Science (FOCS), pp. 323 � 327 (1983).

• �A family of graphs with expensive depth reduction�, Proceedings of the 5^th GI-Conference on Theoretical Computer Science, (1981). The final version appears in Theoretical Computer Science 18(1), pp. 89-93 (1982).

Neural Networks:

• �Neural networks and efficient associative memory�, (with M. Miltrup), Proc. of the 11^th Annual Conference on Computational Learning Theory (COLT), pp. 235 � 246, (1998).

• �The power of approximating: a comparison of activation functions� (with B. DasGupta), Proceedings of the Neural Information Processing Systems Conference (NIPS), pp. 615 � 622, (1993).

  The final version (with the title �Analog versus discrete neural networks�) appears in Neural Computation 8(4), pp. 805 � 818, (1996).

• �A Note on the complexity of reliability in neural networks� (with P. Berman, I. Parberry) IEEE Transactions on Neural Networks 3 (6), pp. 998-1002, (1992).

• �On the computational power of sigmoid versus boolean threshold circuits� (with W. Maass, E. Sontag), Proceedings of the 32^nd Annual Symposium on Foundation of Computer Science (FOCS), pp. 767 � 776, (1991).

• �Relating Boltzmann machines to conventional models of computation� (with I. Parberry), Proceedings of the 2^nd International Symposium on Methodologies for Intelligent Systems, pp. 347 � 354 (1987).

  The final version appears in Neural Networks 2(1), pp. 59 � 67 (1989).

• �Parallel computations with threshold functions� (with I. Parberry), Proceedings of the Structure in Complexity Theory Conference, June 1986; Lecture Notes in Computer Science 223, Springer, 272 � 290 (1986). The final version appears in Journal of Computer and System Sciences, 36(3), pp. 278 � 302 (1988).

Book Chapters: 

• �On the Computational Power of Analog Neural Networks�, (with B. DasGupta), in ed. M.A. Arbib, The Handbook of Brain Theory and Neural Networks, MIT Press, pp. 97 � 100, (2002).

• �Communication complexity and sequential computation�, (with J. Hromkovic), Proc. of the 22^nd International Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science 1295, Springer, pp. 71 � 84, (1997).

• �Theoretische Aspekte neuronaler Netzwerke�, in ed. I. Wegener, Highlights aus der Informatik, Springer-Verlag, pp. 267-286 (1996).

• �On the computational power of sigmoid versus boolean threshold circuits� (with W. Maass, E. Sontag), in eds. V.P. Roychowdhury, K,Y. Siu, and A. Orlitzky, �Theoretical Advances in Neural Computation and Learning�, Kl�wer Academic Publishers, pp. 127 � 151, (1994).

• �Communication complexity and lower bounds for sequential computation�, (with B. Kalyanasundaram), in eds. J. Buchmann, H. Ganzinger, W.J. Paul, Festschrift zum 60. Geburtstag von G�nter Hotz, Teubner Verlag, pp. 253 � 268, (1992).