Georg Schnitger

Publication Activity (10 Years)

Years Active: 1981-2018
Publications (10 Years): 4

Top Venues

Oper. Res. Lett.

Adventures Between Lower Bounds and Higher Altitudes

Inf. Process. Lett.

Electron. Colloquium Comput. Complex.

Bielefeld University, Germany (PHD)

Education History

Bielefeld University, Germany

PHD

Publications

Georg Schnitger
Probabilism versus Alternation for Automata. Adventures Between Lower Bounds and Higher Altitudes (2018)
Matthias Poloczek, Georg Schnitger, David P. Williamson, Anke van Zuylen
Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds. SIAM J. Comput. 46 (3) (2017)
Stasys Jukna, Georg Schnitger
On the optimality of Bellman-Ford-Moore shortest path algorithm. Theor. Comput. Sci. 628 (2016)
Stasys Jukna, Georg Schnitger
On the Optimality of Bellman-Ford-Moore Shortest Path Algorithm. Electron. Colloquium Comput. Complex. 22 (2015)
Manfred Schmidt-Schauß, Georg Schnitger
Fast equality test for straight-line compressed strings. Inf. Process. Lett. 112 (8-9) (2012)
Stasys Jukna, Georg Schnitger
Cutting planes cannot approximate some integer programs. Oper. Res. Lett. 40 (4) (2012)
Stasys Jukna, Georg Schnitger
Min-rank conjecture for log-depth circuits. J. Comput. Syst. Sci. 77 (6) (2011)
Matthias Poloczek, Georg Schnitger
Randomized Variants of Johnson's Algorithm for MAX SAT. SODA (2011)
Stasys Jukna, Georg Schnitger
Yet harder knapsack problems. Theor. Comput. Sci. 412 (45) (2011)
Juraj Hromkovic, Georg Schnitger
Ambiguity and Communication. Theory Comput. Syst. 48 (3) (2011)
Stasys Jukna, Georg Schnitger
Circuits with arbitrary gates for random operators CoRR (2010)
Juraj Hromkovic, Georg Schnitger
On probabilistic pushdown automata. Inf. Comput. 208 (8) (2010)
Stasys Jukna, Georg Schnitger
Min-Rank Conjecture for Log-Depth Circuits CoRR (2010)
Juraj Hromkovic, Holger Petersen, Georg Schnitger
On the limits of the communication complexity technique for proving lower bounds on the size of minimal NFA's. Theor. Comput. Sci. 410 (30-32) (2009)
Juraj Hromkovic, Georg Schnitger
Lower Bounds on the Size of Sweeping Automata. J. Autom. Lang. Comb. 14 (1) (2009)
Stasys Jukna, Georg Schnitger
Min-Rank Conjecture for Log-Depth Circuits. Electron. Colloquium Comput. Complex. 16 (2009)
Juraj Hromkovic, Georg Schnitger
Ambiguity and Communication CoRR (2009)
Juraj Hromkovic, Georg Schnitger
Ambiguity and Communication. STACS (2009)
Peter Bro Miltersen, Rüdiger Reischuk, Georg Schnitger, Dieter van Melkebeek
08381 Executive Summary - Computational Complexity of Discrete Problems. Computational Complexity of Discrete Problems (2008)
Juraj Hromkovic, Georg Schnitger
On the Hardness of Determining Small NFA's and of Proving Lower Bounds on Their Sizes. Developments in Language Theory (2008)
Peter Bro Miltersen, Rüdiger Reischuk, Georg Schnitger, Dieter van Melkebeek
08381 Abstracts Collection - Computational Complexity of Discrete Problems. Computational Complexity of Discrete Problems (2008)
Juraj Hromkovic, Georg Schnitger
Comparing the size of NFAs with and without epsilon-transitions. Theor. Comput. Sci. 380 (1-2) (2007)
Gregor Gramlich, Georg Schnitger
Minimizing nfa's and regular expressions. J. Comput. Syst. Sci. 73 (6) (2007)
Georg Schnitger
-Transitions. STACS (2006)
Maik Weinard, Georg Schnitger
On the Greedy Superstring Conjecture. SIAM J. Discret. Math. 20 (2) (2006)
Gregor Gramlich, Georg Schnitger
Minimizing NFA's and Regular Expressions. STACS (2005)
Juraj Hromkovic, Georg Schnitger
Communication Complexity Method for Proving Lower Bounds on Descriptional Complexity in Automata and Formal Language Theory. DCFS (2005)
Juraj Hromkovic, Georg Schnitger
-Transitions. ICALP (2005)
Juraj Hromkovic, Georg Schnitger
On the power of randomized multicounter machines. Theor. Comput. Sci. 330 (1) (2005)
Pavol Duris, Juraj Hromkovic, Stasys Jukna, Martin Sauerhoff, Georg Schnitger
On multi-partition communication complexity. Inf. Comput. 194 (1) (2004)
Juraj Hromkovic, Georg Schnitger
Pushdown Automata and Multicounter Machines, a Comparison of Computation Modes. ICALP (2003)
Maik Weinard, Georg Schnitger
On the Greedy Superstring Conjecture. FSTTCS (2003)
Juraj Hromkovic, Georg Schnitger
Nondeterministic Communication with a Limited Number of Advice Bits. SIAM J. Comput. 33 (1) (2003)
Juraj Hromkovic, Georg Schnitger
Nondeterminism versus Determinism for Two-Way Finite Automata: Generalizations of Sipser's Separation. ICALP (2003)
Juraj Hromkovic, Sebastian Seibert, Juhani Karhumäki, Hartmut Klauck, Georg Schnitger
Communication Complexity Method for Measuring Nondeterminism in Finite Automata. Inf. Comput. 172 (2) (2002)
Stasys Jukna, Georg Schnitger
Triangle-Freeness Is Hard To Detect. Comb. Probab. Comput. 11 (6) (2002)
Juraj Hromkovic, Georg Schnitger
On the power of Las Vegas II: Two-way finite automata. Theor. Comput. Sci. 262 (1) (2001)
Juraj Hromkovic, Georg Schnitger
On the Power of Las Vegas for One-Way Communication Complexity, OBDDs, and Finite Automata. Inf. Comput. 169 (2) (2001)
Pavol Duris, Juraj Hromkovic, Stasys Jukna, Martin Sauerhoff, Georg Schnitger
On Multipartition Communication Complexity. STACS (2001)
Stasys Jukna, Georg Schnitger
On Multi-Partition Communication Complexity of Triangle-Freeness Electron. Colloquium Comput. Complex. 8 (49) (2001)
Pavol Duris, Juraj Hromkovic, Stasys Jukna, Martin Sauerhoff, Georg Schnitger
On Multipartition Communication Complexity Electron. Colloquium Comput. Complex. 8 (066) (2001)
Juraj Hromkovic, Georg Schnitger
On the Power of Randomized Pushdown Automata. Developments in Language Theory (2001)
Juraj Hromkovic, Juhani Karhumäki, Hartmut Klauck, Georg Schnitger, Sebastian Seibert
Measures of Nondeterminism in Finite Automata. ICALP (2000)
Juraj Hromkovic, Juhani Karhumäki, Hartmut Klauck, Georg Schnitger, Sebastian Seibert
Measures of Nondeterminism in Finite Automata Electron. Colloquium Comput. Complex. 7 (76) (2000)
Juraj Hromkovic, Georg Schnitger
On the Power of Las Vegas II. Two-Way Finite Automata. ICALP (1999)
Juraj Hromkovic, Georg Schnitger
On the Power of Las Vegas II: Two-Way Finite Automata Electron. Colloquium Comput. Complex. 6 (7) (1999)
Matthias Miltrup, Georg Schnitger
Neural Networks and Efficient Associative Memory. COLT (1998)
Juraj Hromkovic, Georg Schnitger
Communication Complexity and Sequential Compuation. MFCS (1997)
Pavol Duris, Juraj Hromkovic, José D. P. Rolim, Georg Schnitger
On the Power of Las Vegas for One-way Communication Complexity, Finite Automata, and Polynomial-time Computations Electron. Colloquium Comput. Complex. 4 (29) (1997)
Pavol Duris, Juraj Hromkovic, José D. P. Rolim, Georg Schnitger
Las Vegas Versus Determinism for One-way Communication Complexity, Finite Automata, and Polynomial-time Computations. STACS (1997)
Juraj Hromkovic, Georg Schnitger
Nondeterministic Communication with a Limited Number of Advice Bits. STOC (1996)
Bhaskar DasGupta, Georg Schnitger
Analog versus discrete neural networks. Neural Comput. 8 (4) (1996)
Martin Dietzfelbinger, Juraj Hromkovic, Georg Schnitger
A Comparison of Two Lower-Bound Methods for Communication Complexity. Theor. Comput. Sci. 168 (1) (1996)
Jeff I. Chu, Georg Schnitger
Communication Complexity of Matrix Computation over Finite Fields. Math. Syst. Theory 28 (3) (1995)
Martin Dietzfelbinger, Juraj Hromkovic, Georg Schnitger
A Comparison of Two Lower Bound Methods for Communication Complexity. MFCS (1994)
Wolfgang Maass, Georg Schnitger, Endre Szemerédi, György Turán
Two Tapes Versus One for Off-Line Turing Machines. Comput. Complex. 3 (1993)
Piotr Berman, Ian Parberry, Georg Schnitger
A note on the complexity of reliability in neural networks. IEEE Trans. Neural Networks 3 (6) (1992)
Piotr Berman, Georg Schnitger
On the Complexity of Approximating the Independent Set Problem Inf. Comput. 96 (1) (1992)
Bala Kalyanasundaram, Georg Schnitger
The Probabilistic Communication Complexity of Set Intersection. SIAM J. Discret. Math. 5 (4) (1992)
Bhaskar DasGupta, Georg Schnitger
The Power of Approximation: A Comparison of Activation Functions. NIPS (1992)
Martin Dietzfelbinger, Wolfgang Maass, Georg Schnitger
The Complexity of Matrix Transposition on One-Tape Off-Line Turing Machines. Theor. Comput. Sci. 82 (1) (1991)
Wolfgang Maass, Georg Schnitger, Eduardo D. Sontag
On the Computational Power of Sigmoid versus Boolean Threshold Circuits FOCS (1991)
Jeff I. Chu, Georg Schnitger
The communication complexity of several problems in matrix computation. J. Complex. 7 (4) (1991)
Bala Kalyanasundaram, Georg Schnitger
On the power of white pebbles. Comb. 11 (2) (1991)
Bala Kalyanasundaram, Georg Schnitger
Rounds Versus Time for the Two Person Pebble Game Inf. Comput. 88 (1) (1990)
Bala Kalyanasundaram, Georg Schnitger
Rounds versus Time for the Two Person Pebble Game (Extended Abstract). STACS (1989)
Jeff I. Chu, Georg Schnitger
The Communication Complexity of Several Problems in Matrix Computation. SPAA (1989)
Ian Parberry, Georg Schnitger
Relating Boltzmann machines to conventional models of computation. Neural Networks 2 (1) (1989)
Piotr Berman, Georg Schnitger
On the Complexity of Approximating the Independent Set Problem. STACS (1989)
Ian Parberry, Georg Schnitger
Parallel Computation with Threshold Functions. J. Comput. Syst. Sci. 36 (3) (1988)
Bala Kalyanasundaram, Georg Schnitger
On the Power of White Pebbles (Extended Abstract) STOC (1988)
Pavol Duris, Zvi Galil, Georg Schnitger
Lower Bounds on Communication Complexity Inf. Comput. 73 (1) (1987)
Georg Schnitger, Bala Kalyanasundaram
The probabilistic communication complexity of set intersection. Computational Complexity Conference (1987)
Ian Parberry, Georg Schnitger
Relating Boltzmann Machines to Conventional Models of Computation. ISMIS (1987)
Wolfgang Maass, Georg Schnitger, Endre Szemerédi
Two Tapes Are Better than One for Off-Line Turing Machines STOC (1987)
Wolfgang Maass, Georg Schnitger
An Optimal Lower Bound for Turing Machines with One Work Tape and a Two- way Input Tape. Computational Complexity Conference (1986)
Ian Parberry, Georg Schnitger
Parallel Computation with Threshold Functions. Computational Complexity Conference (1986)
Pavol Duris, Zvi Galil, Georg Schnitger
Lower Bounds on Communication Complexity STOC (1984)
Georg Schnitger
On Depth-Reduction and Grates FOCS (1983)
Georg Schnitger
A Family of Graphs with Expensive Depth Reduction. Theor. Comput. Sci. 18 (1982)
Stefan Reisch, Georg Schnitger
Three Applications of Kolmogorov-Complexity FOCS (1982)
Georg Schnitger
A Family of Graphs with Expensive Depth-Reduction. Theoretical Computer Science (1981)

Georg Schnitger.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Georg Schnitger