Professur für
Theoretische Informatik

Goethe-Universität Frankfurt am Main - Institut für Informatik

Prof. Dr. Georg Schnitger

Prof. Dr. Georg Schnitger

Prof. Dr. Georg Schnitger
Institut für Informatik
Robert-Mayer-Straße 11-15
60325 Frankfurt am Main
Raum 302

Telefon +49-69-798-28326
Fax +49-69-798-28814
Sprechzeiten Dienstag, 14 – 16 Uhr (in der Vorlesungszeit)

Veröffentlichungen

Bitte beachten Sie die eingeschränkten Nutzungsrechte einiger Veröffentlichungen. Die Nutzung dieser Dokumente im privaten Kontext sowie für Lehrzwecke ist jedoch freigegeben. Die hier verlinkten Beiträge sind in der Regel Vordrucke und entsprechen nicht notwendigerweise der veröffentlichten Endversion. Insbesondere können Korrekturen fehlen, die während der Herausgabe entstanden.

Liste der Veröffentlichungen
  • 2011 Randomized variants of Johnson's algorithm for MAX SAT (with M. Poloczek).
    Proc. of 22nd Ann. ACM-SIAM Symp. on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, (2011).
  • 2011 Yet harder knapsack problems (with S. Jukna).
    Journal version in: Theoretical Computer Science 412 (2011), 6351-6358.
    [Abstract (HTML)]
  • 2011 Min-rank conjecture for log-depth circuits (with S. Jukna).
    Journal version in: Journal of Comput. Syst. Sci. 77:6 (2011), 1023-1038.
    [Abstract (HTML)]
  • 2011 Ambiguity and communication (with J. Hromkovic).
    Journal version: Theory Comput. Syst. 48(3), pp. 517-534 (2011).
    Preliminary version: Proc. of 26th STACS, pp. 553-564 (2009).
  • 2010 On probabilistic pushdown automata (with J. Hromkovic).
    Journal version: Information and Computation 208(8): 982-995 (2010).
  • 2009 Lower Bounds on the size of sweeping automata (with J. Hromkovic).
    Journal version: Journal of Automata, Languages and Combinatorics, 14(1), 23-31, (2009).
  • 2009 On the limits of the communication complexity technique for proving lower bounds on the size of minimal NFA's (with J. Hromkovic and H. Petersen).
    Journal version: Theoretical Computer Science 410(30-32): 2972-2981, (2009).
  • 2008 On the Hardness of Determining Small NFA's and of Proving Lower Bounds on Their Size
    (with J. Hromkovic).
    Proc. 12th Int. Conf. Developments in Language Theory, DLT 2008, Kyoto, Japan, September 16-19,Springer LNCS, vol. 5257, pp. 34-55, (2008).
  • 2007 Comparing the size of NFAs with and without epsilon-transition (with J. Hromkovic).
    Journal version: Theoretical Computer Science 380(1-2): 100-114 (2007)
    Preliminary version: NFAs with and without epsilon-transitions
    Proc. of 32nd ICALP, Lissabon, Springer LNCS, vol. 3580 pp. 385-396 (2005).
  • 2007 Minimizing nfa's and regular expressions (with G. Gramlich).
    Journal version: Journal of Comput. Syst. Sci. 73(6): 908-923 (2007)
    Preliminary version: Proc. of 22nd STACS, Springer LNCS, vol. 3404, pp. 399-411, 2005.
  • 2006 Regular expressions and NFAs without epsilon-transitions
    Proc. of 23rd STACS, Springer LNCS, vol. 3884, pp. 432-443, (2006).
  • 2006 On the greedy superstring conjecture (with M. Weinard).
    Journal version: SIAM J. Discrete Math. 20(2): 502-522 (2006).
    Preliminary version: Proc. of the 23rd FSTTCS, Springer LNCS, vol. 2914, pp. 387-398, (2003).
  • 2005 On the power of randomized multicounter machines (with J. Hromkovic).
    Journal version: Theoretical Computer Science, vol. 330 (1), pp. 135-144, (2005).
  • 2004 On multi-partition communication complexity (with P. Duris, J. Hromkovic, S. Jukna and M. Sauerhoff).
    Journal version in: Information and Computation, 194:1 (2004), 49-75 .
    Preliminary version: Proc. of the 18th STACS, Springer LNCS, vol. 2010, pp. 206-217 (2001).
  • 2003 Pushdown automata and multicounter machines, a comparison of computation modes
    (with J. Hromkovic).
    Proc. of 30th ICALP, Wien, Springer, pp. 66-80, (2003).
  • 2003 Nondeterminism versus determinism for two-way finite automata: generalizations of Sipser's separation (with J. Hromkovic).
    Proc. of 30th ICALP, Wien, Springer, pp. 439-451, (2003).
  • 2003 Nondeterministic Communication with a Limited Number of Advice Bits (with J. Hromkovic).
    Journal version: SIAM Journal on computing, 33 (1), pp. 43-68, (2003).
    Preliminary version: Nondeterministic communication with a limited number of advice bits, Proc. of 28th STOCS, pp. 551-560, (1996).
  • 2002 Triangle-freeness is hard to detect (with S. Jukna).
    Journal version in: Combinatorics, Probability & Computing , pp. 549-569, (2002).
    [Abstract (HTML)] See also a Comment
  • 2002 Communication complexity method for measuring nondeterminism in finite automata (with J. Hromkovic, J. Karhumaki, H. Klauck, and S. Seibert).
    Journal Publication: Information and Computation, pp. 202-217, (2002).
    Preliminary version with the title: Measures of nondeterminism in finite automata: Proc. of 28th ICALP, Lecture Notes in Computer Science, Springer, pp. 199-210, (2000).
  • 2001 On the power of randomized pushdown automata (with J. Hromkovic).
    Proc. of DLT 2001, Springer, pp. 262-271, (2001).
  • 2001 On multipartition communication complexity (with P. Duris,J. Hromkovic, S. Jukna, M. Sauerhoff).
    Journal version: Theoretical Computer Science 262(1), pp. 1-24, (2001).
    Preliminary version: Proc. of the 18th STACS, Lecture Note in Computer Science, Springer, (2001).
  • 2001 On the power of Las Vegas II: Two-way finite automata (with J. Hromkovic).
    Journal version: Theoretical Computer Science 262(1), pp. 1-24, (2001).
    Preliminary version: Proc. of 26th ICALP, Springer, pp. 433-443, (1999).
  • 2001 On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata (with J. Hromkovic).
    Journal version: Information and Computation, pp. 284-296, (2001).
    Preliminary version with the title: 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 14th STACS, Springer LNCS, vol. 1200, pp. 117-128 (1997).
  • 1998 Neural networks and efficient associative memory (with M. Miltrup).
    Proc. of 11th Annual Conference on Computational Learning Theory COLT, pp. 235-246 (1998).
  • 1996 A Comparison of Two Lower-Bound Methods for Communication Complexity (with M. Dietzfelbinger and J. Hromkovic).
    Journal version: Theoretical Computer Science 168(1), pp. 39-51 (1996).
    Preliminary version: Proc. of 19th International Symposium on Mathematical Foundations of Computer Science, pp. 326-335, (1994).
  • 1996 Analog versus discrete neural networks (with B. DasGupta).
    Journal version: Neural Computation 8(4), pp. 805-818, (1996).
    Preliminary version with the title: The power of approximating: a comparison of activation function: Proceedings of the Neural Information Processing Systems Conference, pp. 615-622, (1993).
  • 1995 Communication complexity of matrix computation over finite fields (with J. Chu).
    Journal version: Math. Syst. Theory 28(3), pp. 215-228, (1995).
  • 1993 Two-tapes are better than one for off-line Turing machines (with W. Maass, E. Szemeredi and G. Turan).
    Journal version: Computational Complexity 3(4), pp. 392-401 (1993).
    Preliminary version (with W. Maass and E. Szemeredi): Proceedings of 19th Annual ACM Symposium on Theory of Computing, pp. 94-100 (1987).
  • 1992 The probabilistic communication complexity of set intersection (with B. Kalyanasundaram).
    Journal version: SIAM J. on Discrete Math. 5 , (4), pp. 545-557 (1992).
    Preliminary version: Proceedings of the 2nd Structures of Complexity Theory Conference, Cornell, pp. 41-49 (1987).
  • 1992 On the complexity of approximating the independent set problem (with P. Berman).
    Journal version: Information and Computation 96(1), pp. 77-94 (1992).
    Prelinimary version: Proceedings of the Symposium in Theoretical Aspects of Computer Science, Lecture Notes in Computer Science 349, Springer, pp. 256-268 (1989).
  • 1992 A note on the complexity of reliability in neural networks (with P. Berman and I. Parberry).
    Journal version: IEEE Transactions on Neural Networks 3 (6), pp. 998-1002, (1992).
  • 1991 On the computational power of sigmoid versus boolean threshold circuits (with W. Maass and E. Sontag).
    Proceedings of the 32nd Annual Symposium on Foundation of Computer Science, pp. 767-776, (1991).
  • 1991 On the power of white pebbles (with B. Kalyanasundaram).
    Journal version: Combinatorica 11 (2), pp. 157-171 (1991).
    Preliminary version: Proceedings of the 18th STOC, pp. 258-266 (1988).
  • 1991 The complexity of matrix transposition on one-tape off-line Turing machines (with M. Dietzfelbinger and W. Maass).
    Journal version: Theoretical Computer Science 82(1), pp. 113-129 (1991).
  • 1991 The communication complexity of several problems in matrix computation (with J. Chu).
    Jornal version: Journal of Complexity 7 (4), pp. 395-407 (1991).
    Preliminary version: Proceedings of the 1st Annual ACM Symposium on Parallel Algorithmus and Architectures, Santa Fe, NM, pp. 22-31 (1989).
  • 1990 On the performance of the minimal degree heuristic for Gaussian elimination (with P. Berman).
    Journal version: SIAM Journal on Matrix Analysis and Applications 11, pp. 83-88 (1990).
  • 1990 Rounds versus time for the two person pebble game (with B. Kalyanasundaram).
    Journal version: Information and Computation 88 (1), pp. 1-17 (1990).
    Preliminary version: Proceedings of the Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science 349, Springer, pp. 517-529 (1989).
  • 1989 Relating Boltzmann machines to conventional models of computation (with I. Parberry).
    Journal version: Neural Networks 2(1), pp. 59-67 (1989).
    Preliminary version: Proceedings of the 2nd International Symposium on Methodologies for Intelligent Systems, pp. 347-354 (1987).
  • 1988 Parallel computations with threshold functions (with I. Parberry).
    Journal version: Journal of Computer and System Sciences, 36(3), pp. 278-302 (1988).
    Preliminary version: Proceedings of the Structure in Complexity Theory Conference, June 1986; Lecture Notes in Computer Science 223, Springer, 272-290 (1986).
  • 1988 Checking local optimality in constrained quadratic programming is NP-hard (with P. Pardalos).
    Journal version: Operations Research Letters 7(1), pp. 33-35 (1988).
  • 1987 Lower bounds on communication complexity (with P. Duris and Z. Galil).
    Journal version: Information and Computation, 73(1), pp- 1-22 (1987).
    Preliminary version: Proceedings of the 16th STOC, Washington D.C., pp. 81-91 (1984).
  • 1986 On the power of probabilistic one-tape Turing machines (with B. Kalyanasundaram).
    Proceedings of the 24th Allerton Conference on Communications, Control and Computing, pp. 749-757 (1986).
  • 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).
  • 1983 On depth reduction and grates,
    Proceedings of the 24th FOCS,     pp. 323-327 (1983).
  • 1982 Three applications of Kolmogorov-complexity (with S. Reisch).
    Proceedings of the 23rd FOCS, pp. 45-52 (1982).
  • 1982 A family of graphs with expensive depth reduction
    Journal version: Theoretical Computer Science 18(1), pp. 89-93 (1982).
    Preliminary version: Proceedings of the 5th GI-Conference on Theoretical Computer Science, (1981).

Beiträge zu Büchern

Liste der Beiträge zu Büchern
  • On the computational power of analog neural networks (with B. DasGupta).
    The Handbook of Brain Theory and Neural Networks, MIT Press, (M.A. Arbib, ed.),pp. 97-100, (2002).
  • Communication complexity and sequential computation (with J. Hromkovic).
    Proc. of the 22nd MFCS, Springer LNCS, vol. 1295, pp. 71-84, (1997).
  • Theoretische Aspekte neuronaler Netzwerke
    Highlights aus der Informatik, Springer-Verlag (I. Wegener, ed.), pp. 267-286 (1996).
  • On the computational power of sigmoid versus boolean threshold circuits (with W. Maass and E. Sontag).
    Theoretical Advances in Neural Computation and Learning, (V.P. Roychowdhury, K,Y. Siu, and A. Orlitzky, eds.), Kluwer Academic Publishers, pp. 127-151, (1994).
  • Communication complexity and lower bounds for sequential computation (with B. Kalyanasundaram).
    Festschrift zum 60. Geburtstag von Gunter Hotz (J. Buchmann, H. Ganzinger, W.J. Paul, eds.), Teubner Verlag, pp. 253-268, (1992).