×

zbMATH — the first resource for mathematics

Schnitger, Georg

Compute Distance To:
Author ID: schnitger.georg Recent zbMATH articles by "Schnitger, Georg"
Published as: Schnitger, Georg; Schnitger, G.
Documents Indexed: 56 Publications since 1981, including 1 Book

Publications by Year

Citations contained in zbMATH Open

48 Publications have been cited 370 times in 318 Documents Cited by Year
The probabilistic communication complexity of set intersection. Zbl 0760.68040
Kalyanasundaram, Bala; Schnitger, Georg
63
1992
Checking local optimality in constrained quadratic programming is NP- hard. Zbl 0644.90067
Pardalos, P. M.; Schnitger, G.
54
1988
On the complexity of approximating the independent set problem. Zbl 0804.90121
Berman, Piotr; Schnitger, Georg
29
1992
Parallel computation with threshold functions. Zbl 0652.68064
Parberry, Ian; Schnitger, Georg
26
1988
Communication complexity method for measuring nondeterminism in finite automata. Zbl 1009.68067
Hromkovič, Juraj; Seibert, Sebastian; Karhumäki, Juhani; Klauck, Hartmut; Schnitger, Georg
26
2002
On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata. Zbl 1007.68065
Hromkovič, Juraj; Schnitger, Georg
17
2001
A comparison of two lower-bound methods for communication complexity. Zbl 0874.68150
Dietzfelbinger, Martin; Hromkovič, Juraj; Schnitger, Georg
13
1996
Minimizing nfa’s and regular expressions. Zbl 1152.68459
Gramlich, Gregor; Schnitger, Georg
12
2007
Nondeterminism versus determinism for two-way finite automata: Generalizations of Sipser’s separation. Zbl 1039.68068
Hromkovič, Juraj; Schnitger, Georg
12
2003
Lower bounds on communication complexity. Zbl 0635.68034
Duris, Pavol; Galil, Zvi; Schnitger, Georg
11
1987
Minimizing NFA’s and regular expressions. Zbl 1118.68525
Gramlich, Gregor; Schnitger, Georg
8
2005
Regular expressions and NFAs without \(\epsilon \)-transitions (extended abstract). Zbl 1136.68422
Schnitger, Georg
8
2006
Measures of nondeterminism in finite automata. Zbl 0973.68114
Hromkovič, Juray; Karhumäki, Juhani; Klauck, Hartmut; Schnitger, Georg; Seibert, Sebastian
6
2000
On multi-partition communication complexity. Zbl 1073.68030
Ďuriš, Pavol; Hromkovič, Juraj; Jukna, Stasys; Sauerhoff, Martin; Schnitger, Georg
6
2004
On the power of Las Vegas II: Two-way finite automata. Zbl 0983.68098
Hromkovič, J.; Schnitger, G.
6
2001
A comparison of the computational power of sigmoid and Boolean threshold circuits. Zbl 0835.68042
Maass, W.; Schnitger, G.; Sontag, E. D.
5
1994
Greedy algorithms for the maximum satisfiability problem: simple algorithms and inapproximability bounds. Zbl 1372.68305
Poloczek, Matthias; Schnitger, Georg; Williamson, David P.; van Zuylen, Anke
5
2017
On the power of Las Vegas. II: Two-way finite automata. Zbl 0939.68071
Hromkovič, Juraj; Schnitger, Georg
4
1999
On probabilistic pushdown automata. Zbl 1205.68202
Hromkovič, Juraj; Schnitger, Georg
4
2010
Comparing the size of NFAs with and without \(\epsilon\)-transitions. Zbl 1115.68098
Hromkovič, Juraj; Schnitger, Georg
4
2007
Randomized variants of Johnson’s algorithm for MAX SAT. Zbl 1373.68455
Poloczek, Matthias; Schnitger, Georg
3
2011
Ambiguity and communication. Zbl 1246.68146
Hromkovič, Juraj; Schnitger, Georg
3
2011
Nondeterministic communication with a limited number of advice bits. Zbl 0922.68060
Hromkovic, J.; Schnitger, G.
3
1996
Nondeterministic communication with a limited number of advice bits. Zbl 1040.68046
Hromkovic, Juraj; Schnitger, Georg
3
2003
Fast equality test for straight-line compressed strings. Zbl 1243.68324
Schmidt-Schauß, Manfred; Schnitger, Georg
3
2012
On the hardness of determining small NFA’s and of proving lower bounds on their sizes. Zbl 1159.68017
Hromkovič, Juraj; Schnitger, Georg
3
2008
The complexity of matrix transposition on one-tape off-line Turing machines. Zbl 0731.68042
Dietzfelbinger, Martin; Maass, Wolfgang; Schnitger, Georg
3
1991
The communication complexity of several problems in matrix computation. Zbl 0768.68036
Chu, Jeff I.; Schnitger, Georg
2
1991
Two tapes versus one for off-line Turing machines. Zbl 0802.68048
Maass, Wolfgang; Schnitger, Georg; Szemerédi, Endre; Turán, György
2
1993
On the power of randomized multicounter machines. Zbl 1078.68037
Hromkovič, Juraj; Schnitger, Georg
2
2005
On the greedy superstring conjecture. Zbl 1115.68163
Weinard, Maik; Schnitger, Georg
2
2006
Triangle-freeness is hard to detect. Zbl 1013.05033
Jukna, S.; Schnitger, G.
2
2002
Communication complexity and sequential computation. Zbl 0941.68090
Hromkovič, Juraj; Schnitger, Georg
2
1997
On the power of randomized pushdown automata. Zbl 1073.68047
Hromkovič, Juraj; Schnitger, Georg
2
2002
NFAs with and without \(\epsilon\)-transitions. Zbl 1082.68052
Hromkovič, Juraj; Schnitger, Georg
2
2005
Pushdown automata and multicounter machines, a comparison of computation modes. Zbl 1039.68554
Hromkovič, Juraj; Schnitger, Georg
2
2003
Min-rank conjecture for log-depth circuits. Zbl 1247.94074
Jukna, Stasys; Schnitger, Georg
1
2011
A family of graphs with expensive depth-reduction. Zbl 0485.68054
Schnitger, Georg
1
1982
On the greedy superstring conjecture. Zbl 1205.68528
Weinard, Maik; Schnitger, Georg
1
2003
Lower bounds on the size of sweeping automata. Zbl 1192.68413
Hromkovič, Juraj; Schnitger, Georg
1
2009
On the limits of the communication complexity technique for proving lower bounds on the size of minimal NFA’s. Zbl 1173.68035
Hromkovič, Juraj; Petersen, Holger; Schnitger, Georg
1
2009
An optimal lower bound for Turing machines with one work tape and a two- way input tape. Zbl 0611.68023
Maass, Wolfgang; Schnitger, Georg
1
1986
Parallel computation with threshold functions. Zbl 0611.68024
Parberry, Ian; Schnitger, Georg
1
1986
On the performance of the minimum degree ordering for Gaussian elimination. Zbl 0703.65016
Berman, Piotr; Schnitger, Georg
1
1990
On the optimality of Bellman-Ford-Moore shortest path algorithm. Zbl 1339.90327
Jukna, Stasys; Schnitger, Georg
1
2016
Ambiguity and communication. Zbl 1236.68169
Hromkovič, Juraj; Schnitger, Georg
1
2009
On multipartition communication complexity (extended abstract). Zbl 0976.68514
Duriš, Pavol; Hromkovič, Juraj; Jukna, Stasys; Sauerhoff, Martin; Schnitger, Georg
1
2001
Rounds versus time for the two person pebble game. Zbl 0721.90096
Kalyanasundaram, Bala; Schnitger, Georg
1
1990
Greedy algorithms for the maximum satisfiability problem: simple algorithms and inapproximability bounds. Zbl 1372.68305
Poloczek, Matthias; Schnitger, Georg; Williamson, David P.; van Zuylen, Anke
5
2017
On the optimality of Bellman-Ford-Moore shortest path algorithm. Zbl 1339.90327
Jukna, Stasys; Schnitger, Georg
1
2016
Fast equality test for straight-line compressed strings. Zbl 1243.68324
Schmidt-Schauß, Manfred; Schnitger, Georg
3
2012
Randomized variants of Johnson’s algorithm for MAX SAT. Zbl 1373.68455
Poloczek, Matthias; Schnitger, Georg
3
2011
Ambiguity and communication. Zbl 1246.68146
Hromkovič, Juraj; Schnitger, Georg
3
2011
Min-rank conjecture for log-depth circuits. Zbl 1247.94074
Jukna, Stasys; Schnitger, Georg
1
2011
On probabilistic pushdown automata. Zbl 1205.68202
Hromkovič, Juraj; Schnitger, Georg
4
2010
Lower bounds on the size of sweeping automata. Zbl 1192.68413
Hromkovič, Juraj; Schnitger, Georg
1
2009
On the limits of the communication complexity technique for proving lower bounds on the size of minimal NFA’s. Zbl 1173.68035
Hromkovič, Juraj; Petersen, Holger; Schnitger, Georg
1
2009
Ambiguity and communication. Zbl 1236.68169
Hromkovič, Juraj; Schnitger, Georg
1
2009
On the hardness of determining small NFA’s and of proving lower bounds on their sizes. Zbl 1159.68017
Hromkovič, Juraj; Schnitger, Georg
3
2008
Minimizing nfa’s and regular expressions. Zbl 1152.68459
Gramlich, Gregor; Schnitger, Georg
12
2007
Comparing the size of NFAs with and without \(\epsilon\)-transitions. Zbl 1115.68098
Hromkovič, Juraj; Schnitger, Georg
4
2007
Regular expressions and NFAs without \(\epsilon \)-transitions (extended abstract). Zbl 1136.68422
Schnitger, Georg
8
2006
On the greedy superstring conjecture. Zbl 1115.68163
Weinard, Maik; Schnitger, Georg
2
2006
Minimizing NFA’s and regular expressions. Zbl 1118.68525
Gramlich, Gregor; Schnitger, Georg
8
2005
On the power of randomized multicounter machines. Zbl 1078.68037
Hromkovič, Juraj; Schnitger, Georg
2
2005
NFAs with and without \(\epsilon\)-transitions. Zbl 1082.68052
Hromkovič, Juraj; Schnitger, Georg
2
2005
On multi-partition communication complexity. Zbl 1073.68030
Ďuriš, Pavol; Hromkovič, Juraj; Jukna, Stasys; Sauerhoff, Martin; Schnitger, Georg
6
2004
Nondeterminism versus determinism for two-way finite automata: Generalizations of Sipser’s separation. Zbl 1039.68068
Hromkovič, Juraj; Schnitger, Georg
12
2003
Nondeterministic communication with a limited number of advice bits. Zbl 1040.68046
Hromkovic, Juraj; Schnitger, Georg
3
2003
Pushdown automata and multicounter machines, a comparison of computation modes. Zbl 1039.68554
Hromkovič, Juraj; Schnitger, Georg
2
2003
On the greedy superstring conjecture. Zbl 1205.68528
Weinard, Maik; Schnitger, Georg
1
2003
Communication complexity method for measuring nondeterminism in finite automata. Zbl 1009.68067
Hromkovič, Juraj; Seibert, Sebastian; Karhumäki, Juhani; Klauck, Hartmut; Schnitger, Georg
26
2002
Triangle-freeness is hard to detect. Zbl 1013.05033
Jukna, S.; Schnitger, G.
2
2002
On the power of randomized pushdown automata. Zbl 1073.68047
Hromkovič, Juraj; Schnitger, Georg
2
2002
On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata. Zbl 1007.68065
Hromkovič, Juraj; Schnitger, Georg
17
2001
On the power of Las Vegas II: Two-way finite automata. Zbl 0983.68098
Hromkovič, J.; Schnitger, G.
6
2001
On multipartition communication complexity (extended abstract). Zbl 0976.68514
Duriš, Pavol; Hromkovič, Juraj; Jukna, Stasys; Sauerhoff, Martin; Schnitger, Georg
1
2001
Measures of nondeterminism in finite automata. Zbl 0973.68114
Hromkovič, Juray; Karhumäki, Juhani; Klauck, Hartmut; Schnitger, Georg; Seibert, Sebastian
6
2000
On the power of Las Vegas. II: Two-way finite automata. Zbl 0939.68071
Hromkovič, Juraj; Schnitger, Georg
4
1999
Communication complexity and sequential computation. Zbl 0941.68090
Hromkovič, Juraj; Schnitger, Georg
2
1997
A comparison of two lower-bound methods for communication complexity. Zbl 0874.68150
Dietzfelbinger, Martin; Hromkovič, Juraj; Schnitger, Georg
13
1996
Nondeterministic communication with a limited number of advice bits. Zbl 0922.68060
Hromkovic, J.; Schnitger, G.
3
1996
A comparison of the computational power of sigmoid and Boolean threshold circuits. Zbl 0835.68042
Maass, W.; Schnitger, G.; Sontag, E. D.
5
1994
Two tapes versus one for off-line Turing machines. Zbl 0802.68048
Maass, Wolfgang; Schnitger, Georg; Szemerédi, Endre; Turán, György
2
1993
The probabilistic communication complexity of set intersection. Zbl 0760.68040
Kalyanasundaram, Bala; Schnitger, Georg
63
1992
On the complexity of approximating the independent set problem. Zbl 0804.90121
Berman, Piotr; Schnitger, Georg
29
1992
The complexity of matrix transposition on one-tape off-line Turing machines. Zbl 0731.68042
Dietzfelbinger, Martin; Maass, Wolfgang; Schnitger, Georg
3
1991
The communication complexity of several problems in matrix computation. Zbl 0768.68036
Chu, Jeff I.; Schnitger, Georg
2
1991
On the performance of the minimum degree ordering for Gaussian elimination. Zbl 0703.65016
Berman, Piotr; Schnitger, Georg
1
1990
Rounds versus time for the two person pebble game. Zbl 0721.90096
Kalyanasundaram, Bala; Schnitger, Georg
1
1990
Checking local optimality in constrained quadratic programming is NP- hard. Zbl 0644.90067
Pardalos, P. M.; Schnitger, G.
54
1988
Parallel computation with threshold functions. Zbl 0652.68064
Parberry, Ian; Schnitger, Georg
26
1988
Lower bounds on communication complexity. Zbl 0635.68034
Duris, Pavol; Galil, Zvi; Schnitger, Georg
11
1987
An optimal lower bound for Turing machines with one work tape and a two- way input tape. Zbl 0611.68023
Maass, Wolfgang; Schnitger, Georg
1
1986
Parallel computation with threshold functions. Zbl 0611.68024
Parberry, Ian; Schnitger, Georg
1
1986
A family of graphs with expensive depth-reduction. Zbl 0485.68054
Schnitger, Georg
1
1982
all top 5

Cited by 476 Authors

12 Schnitger, Georg
10 Hromkovič, Juraj
10 Jirásková, Galina
10 Pardalos, Panos M.
9 Salomaa, Kai T.
8 Holzer, Markus
7 Kutrib, Martin
7 Pighizzini, Giovanni
5 Geffert, Viliam
5 Kapoutsis, Christos A.
4 Braverman, Mark
4 DasGupta, Bhaskar
4 Ďuriš, Pavol
4 Feige, Uriel
4 Gao, David Yang
4 Gruber, Hermann
4 Malcher, Andreas
4 Pitassi, Toniann
4 Theis, Dirk Oliver
4 Turán, Gyorgy
4 Wigderson, Avi
3 Alon, Noga M.
3 Ambainis, Andris
3 Anselmo, Marcella
3 Borodin, Allan B.
3 Guisewite, Geoffrey M.
3 Gur, Tom
3 Hager, William W.
3 Hungerford, James T.
3 Itsykson, Dmitry M.
3 Locatelli, Marco
3 Madonia, Maria
3 McGregor, Andrew
3 Mix Barrington, David A.
3 Petersen, Holger
3 Raz, Ran
3 Say, A. C. Cem
3 Schmidt-Schauß, Manfred
3 Sherstov, Alexander A.
3 Vavasis, Stephen A.
3 Weinreb, Enav
3 Yakaryılmaz, Abuzer
3 Ye, Yinyu
2 Aceto, Luca
2 Achilleos, Antonis
2 Acuña, Vicente
2 Akl, Selim G.
2 Amano, Kazuyuki
2 Beimel, Amos
2 Benson, Harold P.
2 Berman, Piotr
2 Björklund, Johanna
2 Bomze, Immanuel M.
2 Brody, Joshua E.
2 Cazaux, Bastien
2 Chakrabarti, Amit
2 Cleophas, Loek Gerard
2 Cormode, Graham
2 Dietzfelbinger, Martin
2 Domaratzki, Michael
2 Ferreira, Carlos Eduardo
2 Fiorini, Samuel
2 Francalanza, Adrian
2 Ganor, Anat
2 Gao, Yuelin
2 Göös, Mika
2 Han, Yo-Sub
2 Ingólfsdóttir, Anna
2 Jeřábek, Emil
2 Jirásek, Jozef jun.
2 Júdice, Joaquim João
2 Kann, Viggo
2 Kao, Ming-Yang
2 Kirsten, Daniel
2 Kjartansson, Sævar Örn
2 Klauck, Hartmut
2 Kontinen, Juha
2 Královič, Richard
2 Kucherov, Gregory
2 Kushilevitz, Eyal
2 Le Gall, François
2 Libkin, Leonid O.
2 Maass, Wolfgang
2 Maletti, Andreas
2 Maneth, Sebastian
2 Manurangsi, Pasin
2 McKenzie, Pierre
2 Moreno, Eduardo
2 Nanongkai, Danupon
2 Neumaier, Arnold
2 Okhotin, Alexander
2 Palioudakis, Alexandros
2 Pankratov, Denis
2 Parberry, Ian
2 Phillips, Jeff M.
2 Pinhas, Tamar
2 Poloczek, Matthias
2 Pourmoradnasseri, Mozhgan
2 Qiu, Daowen
2 Raber, Ulrich
...and 376 more Authors
all top 5

Cited in 65 Serials

49 Theoretical Computer Science
24 Journal of Computer and System Sciences
19 Information Processing Letters
15 Information and Computation
14 Computational Complexity
13 SIAM Journal on Computing
13 International Journal of Foundations of Computer Science
12 Journal of Global Optimization
9 Algorithmica
8 Journal of Optimization Theory and Applications
8 Mathematical Programming. Series A. Series B
7 Theory of Computing Systems
6 Discrete Applied Mathematics
6 RAIRO. Theoretical Informatics and Applications
5 Linear Algebra and its Applications
3 Applied Mathematics and Computation
3 Combinatorica
3 Annals of Operations Research
3 MSCS. Mathematical Structures in Computer Science
3 Optimization Letters
2 Mathematics of Operations Research
2 Mathematical Systems Theory
2 Computers & Operations Research
2 European Journal of Operational Research
2 Distributed Computing
2 Journal of Combinatorial Optimization
2 Mathematical Programming Computation
2 RAIRO. Theoretical Informatics and Applications
1 Acta Informatica
1 Computers & Mathematics with Applications
1 Acta Mathematica
1 BIT
1 Journal of Combinatorial Theory. Series A
1 Journal of Computational and Applied Mathematics
1 Journal of Economic Theory
1 The Journal of Symbolic Logic
1 Nonlinear Analysis. Theory, Methods & Applications. Series A: Theory and Methods
1 European Journal of Combinatorics
1 Operations Research Letters
1 Annals of Pure and Applied Logic
1 Physica D
1 Optimization
1 Journal of Computer Science and Technology
1 Applied Mathematics Letters
1 Journal of Cryptology
1 Economics Letters
1 Games and Economic Behavior
1 SIAM Review
1 Bulletin of the American Mathematical Society. New Series
1 Archive for Mathematical Logic
1 SIAM Journal on Optimization
1 Combinatorics, Probability and Computing
1 Optimization Methods & Software
1 Journal of the ACM
1 Optimization and Engineering
1 Lobachevskii Journal of Mathematics
1 Natural Computing
1 Journal of Discrete Algorithms
1 Acta Numerica
1 Science in China. Series F
1 Japanese Journal of Mathematics. 3rd Series
1 Algorithms
1 Croatian Operational Research Review (CRORR)
1 Computer Science Review
1 Journal of Logical and Algebraic Methods in Programming

Citations by Year