Prof. Dr. Georg Schnitger
Prof. Dr. Georg Schnitger
Institut für Informatik
RobertMayerStraße 1115
60325 Frankfurt am Main
Room 302
Phone  +496979828326 
Fax  +496979828814 
Office hours  Tuesday, 2  4 pm 
Publications
Please note that some of the publications are subject to copyright restrictions but you are free to use such publications for personal research or education purposes. For papers that have already been published, the versions available here are, as a rule, those of the earlier preprints, and may not contain corrections made in the editing process.
List of publications

2011
Randomized variants of Johnson's algorithm for MAX SAT
.
Proc. of 22^{nd} Ann. ACMSIAM Symp. on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 2325, (2011). 
2011
Yet harder knapsack problems
.
Journal version in: Theoretical Computer Science 412 (2011), 63516358.
[Abstract (HTML)] 
2011
Minrank conjecture for logdepth circuits
.
Journal version in: Journal of Comput. Syst. Sci. 77:6 (2011), 10231038.
[Abstract (HTML)] 
2011
Ambiguity and communication
.
Journal version: Theory Comput. Syst. 48(3), pp. 517534 (2011).
Preliminary version: Proc. of 26^{th} STACS, pp. 553564 (2009). 
2010
On probabilistic pushdown automata
.
Journal version: Information and Computation 208(8): 982995 (2010). 
2009
Lower Bounds on the size of sweeping automata
.
Journal version: Journal of Automata, Languages and Combinatorics, 14(1), 2331, (2009). 
2009
On the limits of the communication complexity technique for proving lower bounds on the size of minimal NFA's
.
Journal version: Theoretical Computer Science 410(3032): 29722981, (2009). 
2008
On the Hardness of Determining Small NFA's and of Proving Lower Bounds on Their Size
.
Proc. 12^{th} Int. Conf. Developments in Language Theory, DLT 2008, Kyoto, Japan, September 1619,Springer LNCS, vol. 5257, pp. 3455, (2008). 
2007
Comparing the size of NFAs with and without epsilontransition
.
Journal version: Theoretical Computer Science 380(12): 100114 (2007)
Preliminary version: NFAs with and without epsilontransitions
Proc. of 32^{nd} ICALP, Lissabon, Springer LNCS, vol. 3580 pp. 385396 (2005). 
2007
Minimizing nfa's and regular expressions
.
Journal version: Journal of Comput. Syst. Sci. 73(6): 908923 (2007)
Preliminary version: Proc. of 22^{nd} STACS, Springer LNCS, vol. 3404, pp. 399411, 2005. 
2006
Regular expressions and NFAs without epsilontransitions
Proc. of 23^{rd} STACS, Springer LNCS, vol. 3884, pp. 432443, (2006).

2006
On the greedy superstring conjecture
.
Journal version: SIAM J. Discrete Math. 20(2): 502522 (2006).
Preliminary version: Proc. of the 23^{rd} FSTTCS, Springer LNCS, vol. 2914, pp. 387398, (2003). 
2005
On the power of randomized multicounter machines
.
Journal version: Theoretical Computer Science, vol. 330 (1), pp. 135144, (2005). 
2004
On multipartition communication complexity (with P. Duris,
J. Hromkovic, S. Jukna and M. Sauerhoff).
Journal version in: Information and Computation, 194:1 (2004), 4975 .
Preliminary version: Proc. of the 18^{th} STACS, Springer LNCS, vol. 2010, pp. 206217 (2001). 
2003
Pushdown automata and multicounter machines, a comparison of computation modes
.
Proc. of 30^{th} ICALP, Wien, Springer, pp. 6680, (2003). 
2003
Nondeterminism versus determinism for twoway finite automata: generalizations
of Sipser's separation
.
Proc. of 30^{th} ICALP, Wien, Springer, pp. 439451, (2003). 
2003
Nondeterministic Communication with a Limited Number of Advice Bits
.
Journal version: SIAM Journal on computing, 33 (1), pp. 4368, (2003).
Preliminary version: Nondeterministic communication with a limited number of advice bits, Proc. of 28^{th} STOCS, pp. 551560, (1996). 
2002
Trianglefreeness is hard to detect
.
Journal version in: Combinatorics, Probability & Computing , pp. 549569, (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. 202217, (2002).
Preliminary version with the title: Measures of nondeterminism in finite automata: Proc. of 28^{th} ICALP, Lecture Notes in Computer Science, Springer, pp. 199210, (2000). 
2001
On the power of randomized pushdown automata
.
Proc. of DLT 2001, Springer, pp. 262271, (2001). 
2001
On multipartition communication complexity
.
Journal version: Theoretical Computer Science 262(1), pp. 124, (2001).
Preliminary version: Proc. of the 18^{th} STACS, Lecture Note in Computer Science, Springer, (2001). 
2001
On the power of Las Vegas II: Twoway finite automata
.
Journal version: Theoretical Computer Science 262(1), pp. 124, (2001).
Preliminary version: Proc. of 26^{th} ICALP, Springer, pp. 433443, (1999). 
2001
On the power of Las Vegas for oneway communication complexity, OBDDs, and finite automata
.
Journal version: Information and Computation, pp. 284296, (2001).
Preliminary version with the title: Las Vegas versus determinism for oneway communication complexity, finite automata and polynomialtime computation , Proc. of 14^{th} STACS, Springer LNCS, vol. 1200, pp. 117128 (1997). 
1998
Neural networks and efficient associative memory
.
Proc. of 11^{th} Annual Conference on Computational Learning Theory COLT, pp. 235246 (1998). 
1996
A Comparison of Two LowerBound Methods for Communication Complexity
.
Journal version: Theoretical Computer Science 168(1), pp. 3951 (1996).
Preliminary version: Proc. of 19^{th} International Symposium on Mathematical Foundations of Computer Science, pp. 326335, (1994). 
1996
Analog versus discrete neural networks
.
Journal version: Neural Computation 8(4), pp. 805818, (1996).
Preliminary version with the title: The power of approximating: a comparison of activation function: Proceedings of the Neural Information Processing Systems Conference, pp. 615622, (1993). 
1995
Communication complexity of matrix computation over finite fields
.
Journal version: Math. Syst. Theory 28(3), pp. 215228, (1995). 
1993
Twotapes are better than one for offline Turing machines
.
Journal version: Computational Complexity 3(4), pp. 392401 (1993).
Preliminary version : Proceedings of 19^{th} Annual ACM Symposium on Theory of Computing, pp. 94100 (1987). 
1992
The probabilistic communication complexity of set intersection
.
Journal version: SIAM J. on Discrete Math. 5 , (4), pp. 545557 (1992).
Preliminary version: Proceedings of the 2^{nd} Structures of Complexity Theory Conference, Cornell, pp. 4149 (1987). 
1992
On the complexity of approximating the independent set problem
.
Journal version: Information and Computation 96(1), pp. 7794 (1992).
Prelinimary version: Proceedings of the Symposium in Theoretical Aspects of Computer Science, Lecture Notes in Computer Science 349, Springer, pp. 256268 (1989). 
1992
A note on the complexity of reliability in neural networks
.
Journal version: IEEE Transactions on Neural Networks 3 (6), pp. 9981002, (1992). 
1991
On the computational power of sigmoid versus boolean threshold circuits
.
Proceedings of the 32^{nd} Annual Symposium on Foundation of Computer Science, pp. 767776, (1991). 
1991
On the power of white pebbles
.
Journal version: Combinatorica 11 (2), pp. 157171 (1991).
Preliminary version: Proceedings of the 18^{th} STOC, pp. 258266 (1988). 
1991
The complexity of matrix transposition on onetape offline Turing machines
.
Journal version: Theoretical Computer Science 82(1), pp. 113129 (1991). 
1991
The communication complexity of several problems in matrix computation
.
Jornal version: Journal of Complexity 7 (4), pp. 395407 (1991).
Preliminary version: Proceedings of the 1^{st} Annual ACM Symposium on Parallel Algorithmus and Architectures, Santa Fe, NM, pp. 2231 (1989). 
1990
On the performance of the minimal degree heuristic for Gaussian elimination
.
Journal version: SIAM Journal on Matrix Analysis and Applications 11, pp. 8388 (1990). 
1990
Rounds versus time for the two person pebble game
.
Journal version: Information and Computation 88 (1), pp. 117 (1990).
Preliminary version: Proceedings of the Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science 349, Springer, pp. 517529 (1989). 
1989
Relating Boltzmann machines to conventional models of computation
.
Journal version: Neural Networks 2(1), pp. 5967 (1989).
Preliminary version: Proceedings of the 2nd International Symposium on Methodologies for Intelligent Systems, pp. 347354 (1987). 
1988
Parallel computations with threshold functions
.
Journal version: Journal of Computer and System Sciences, 36(3), pp. 278302 (1988).
Preliminary version: Proceedings of the Structure in Complexity Theory Conference, June 1986; Lecture Notes in Computer Science 223, Springer, 272290 (1986). 
1988
Checking local optimality in constrained quadratic programming is NPhard
.
Journal version: Operations Research Letters 7(1), pp. 3335 (1988). 
1987
Lower bounds on communication complexity
.
Journal version: Information and Computation, 73(1), pp 122 (1987).
Preliminary version: Proceedings of the 16^{th} STOC, Washington D.C., pp. 8191 (1984). 
1986
On the power of probabilistic onetape Turing machines
.
Proceedings of the 24^{th} Allerton Conference on Communications, Control and Computing, pp. 749757 (1986). 
1986
An optimal lover bound for Turing machines with one work tape and a twoway input tape
.
Proceedings of The Structure in Complexity Theory Conference, Lecture Notes in Computer Science 223, Springer, pp. 249264 (1986). 
1983
On depth reduction and grates,
Proceedings of the 24^{th} FOCS, pp. 323327 (1983). 
1982
Three applications of Kolmogorovcomplexity
.
Proceedings of the 23^{rd} FOCS, pp. 4552 (1982). 
1982
A family of graphs with expensive depth reduction
Journal version: Theoretical Computer Science 18(1), pp. 8993 (1982).
Preliminary version: Proceedings of the 5^{th} GIConference on Theoretical Computer Science, (1981).
Book chapters
List of book chapters

On the computational power of analog neural networks
.
The Handbook of Brain Theory and Neural Networks, MIT Press, (M.A. Arbib, ed.),pp. 97100, (2002). 
Communication complexity and sequential computation
.
Proc. of the 22^{nd} MFCS, Springer LNCS, vol. 1295, pp. 7184, (1997). 
Theoretische Aspekte neuronaler Netzwerke
Highlights aus der Informatik, SpringerVerlag (I. Wegener, ed.), pp. 267286 (1996). 
On the computational power of sigmoid versus boolean threshold circuits
.
Theoretical Advances in Neural Computation and Learning, (V.P. Roychowdhury, K,Y. Siu, and A. Orlitzky, eds.), Kluwer Academic Publishers, pp. 127151, (1994). 
Communication complexity and lower bounds for sequential computation
.
Festschrift zum 60. Geburtstag von Gunter Hotz (J. Buchmann, H. Ganzinger, W.J. Paul, eds.), Teubner Verlag, pp. 253268, (1992).