Georg Schnitger

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