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
.
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
.
Journal version in: Theoretical Computer Science 412 (2011), 6351-6358.
[Abstract (HTML)] -
2011
Min-rank conjecture for log-depth circuits
.
Journal version in: Journal of Comput. Syst. Sci. 77:6 (2011), 1023-1038.
[Abstract (HTML)] -
2011
Ambiguity and communication
.
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
.
Journal version: Information and Computation 208(8): 982-995 (2010). -
2009
Lower Bounds on the size of sweeping automata
.
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
.
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
.
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
.
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
.
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
.
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
.
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
.
Proc. of 30th ICALP, Wien, Springer, pp. 66-80, (2003). -
2003
Nondeterminism versus determinism for two-way finite automata: generalizations
of Sipser's separation
.
Proc. of 30th ICALP, Wien, Springer, pp. 439-451, (2003). -
2003
Nondeterministic Communication with a Limited Number of Advice Bits
.
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
.
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
.
Proc. of DLT 2001, Springer, pp. 262-271, (2001). -
2001
On multipartition communication complexity
.
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
.
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
.
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 , Proc. of 14th STACS, Springer LNCS, vol. 1200, pp. 117-128 (1997). -
1998
Neural networks and efficient associative memory
.
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
.
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
.
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
.
Journal version: Math. Syst. Theory 28(3), pp. 215-228, (1995). -
1993
Two-tapes are better than one for off-line Turing machines
.
Journal version: Computational Complexity 3(4), pp. 392-401 (1993).
Preliminary version : Proceedings of 19th Annual ACM Symposium on Theory of Computing, pp. 94-100 (1987). -
1992
The probabilistic communication complexity of set intersection
.
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
.
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
.
Journal version: IEEE Transactions on Neural Networks 3 (6), pp. 998-1002, (1992). -
1991
On the computational power of sigmoid versus boolean threshold circuits
.
Proceedings of the 32nd Annual Symposium on Foundation of Computer Science, pp. 767-776, (1991). -
1991
On the power of white pebbles
.
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
.
Journal version: Theoretical Computer Science 82(1), pp. 113-129 (1991). -
1991
The communication complexity of several problems in matrix computation
.
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
.
Journal version: SIAM Journal on Matrix Analysis and Applications 11, pp. 83-88 (1990). -
1990
Rounds versus time for the two person pebble game
.
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
.
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
.
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
.
Journal version: Operations Research Letters 7(1), pp. 33-35 (1988). -
1987
Lower bounds on communication complexity
.
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
.
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
.
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
.
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
.
The Handbook of Brain Theory and Neural Networks, MIT Press, (M.A. Arbib, ed.),pp. 97-100, (2002). -
Communication complexity and sequential computation
.
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
.
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
.
Festschrift zum 60. Geburtstag von Gunter Hotz (J. Buchmann, H. Ganzinger, W.J. Paul, eds.), Teubner Verlag, pp. 253-268, (1992).