Georg Schnitger

Proceedings of the Adventures Between Lower Bounds and Higher Altitudes, 2018

2017

Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds.

[BibT_eX]

[DOI]

SIAM J. Comput., 2017

2015

On the Optimality of Bellman-Ford-Moore Shortest Path Algorithm.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

2012

Cutting planes cannot approximate some integer programs.

[BibT_eX]

[DOI]

Oper. Res. Lett., 2012

Fast equality test for straight-line compressed strings.

[BibT_eX]

[DOI]

Manfred Schmidt-Schauß

Inf. Process. Lett., 2012

2011

Yet harder knapsack problems.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2011

Randomized Variants of Johnson's Algorithm for MAX SAT.

[BibT_eX]

[DOI]

Matthias Poloczek

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

2010

On probabilistic pushdown automata.

[BibT_eX]

[DOI]

Inf. Comput., 2010

Circuits with arbitrary gates for random operators

[BibT_eX]

[DOI]

CoRR, 2010

2009

On the limits of the communication complexity technique for proving lower bounds on the size of minimal NFA's.

[BibT_eX]

[DOI]

Holger Petersen

Theor. Comput. Sci., 2009

Lower Bounds on the Size of Sweeping Automata.

[BibT_eX]

[DOI]

J. Autom. Lang. Comb., 2009

Min-Rank Conjecture for Log-Depth Circuits.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2009

Ambiguity and Communication.

[BibT_eX]

[DOI]

Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science, 2009

2008

On the Hardness of Determining Small NFA's and of Proving Lower Bounds on Their Sizes.

[BibT_eX]

[DOI]

Proceedings of the Developments in Language Theory, 12th International Conference, 2008

08381 Executive Summary - Computational Complexity of Discrete Problems.

[BibT_eX]

[DOI]

Proceedings of the Computational Complexity of Discrete Problems, 14.09. - 19.09.2008, 2008

08381 Abstracts Collection - Computational Complexity of Discrete Problems.

[BibT_eX]

[DOI]

Proceedings of the Computational Complexity of Discrete Problems, 14.09. - 19.09.2008, 2008

2007

Comparing the size of NFAs with and without epsilon-transitions.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2007

2006

Regular Expressions and NFAs Without <i>epsilon</i>-Transitions.

[BibT_eX]

[DOI]

Proceedings of the STACS 2006, 2006

2005

On the power of randomized multicounter machines.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2005

Minimizing NFA's and Regular Expressions.

[BibT_eX]

[DOI]

Gregor Gramlich

Proceedings of the STACS 2005, 2005

NFAs With and Without <i>epsilon</i>-Transitions.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 32nd International Colloquium, 2005

Communication Complexity Method for Proving Lower Bounds on Descriptional Complexity in Automata and Formal Language Theory.

[BibT_eX]

Proceedings of the 7th International Workshop on Descriptional Complexity of Formal Systems - DCFS 2005, Como, Italy, June 30, 2005

2004

On multi-partition communication complexity.

[BibT_eX]

[DOI]

Inf. Comput., 2004

2003

Nondeterminism versus Determinism for Two-Way Finite Automata: Generalizations of Sipser's Separation.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 30th International Colloquium, 2003

Pushdown Automata and Multicounter Machines, a Comparison of Computation Modes.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 30th International Colloquium, 2003

On the Greedy Superstring Conjecture.

[BibT_eX]

[DOI]

Maik Weinard

Proceedings of the FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science, 2003

2002

Communication Complexity Method for Measuring Nondeterminism in Finite Automata.

[BibT_eX]

[DOI]

Inf. Comput., 2002

Triangle-Freeness Is Hard To Detect.

[BibT_eX]

[DOI]

Comb. Probab. Comput., 2002

2001

On the Power of Las Vegas for One-Way Communication Complexity, OBDDs, and Finite Automata.

[BibT_eX]

[DOI]

Inf. Comput., 2001

On Multi-Partition Communication Complexity of Triangle-Freeness

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2001

On Multipartition Communication Complexity.

[BibT_eX]

[DOI]

Proceedings of the STACS 2001, 2001

On the Power of Randomized Pushdown Automata.

[BibT_eX]

[DOI]

Proceedings of the Developments in Language Theory, 5th International Conference, 2001

2000

Measures of Nondeterminism in Finite Automata.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 27th International Colloquium, 2000

1999

On the Power of Las Vegas II. Two-Way Finite Automata.

[BibT_eX]

[DOI]

Proceedings of the Automata, 1999

1998

Neural Networks and Efficient Associative Memory.

[BibT_eX]

[DOI]

Matthias Miltrup

Proceedings of the Eleventh Annual Conference on Computational Learning Theory, 1998

1997

On the Power of Las Vegas for One-way Communication Complexity, Finite Automata, and Polynomial-time Computations

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1997

Las Vegas Versus Determinism for One-way Communication Complexity, Finite Automata, and Polynomial-time Computations.

[BibT_eX]

[DOI]

Proceedings of the STACS 97, 14th Annual Symposium on Theoretical Aspects of Computer Science, Lübeck, Germany, February 27, 1997

Communication Complexity and Sequential Compuation.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 1997, 1997

1996

Analog versus discrete neural networks.

[BibT_eX]

[DOI]

Bhaskar DasGupta

Neural Comput., 1996

Nondeterministic Communication with a Limited Number of Advice Bits.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

1995

Communication Complexity of Matrix Computation over Finite Fields.

[BibT_eX]

[DOI]

Jeff I. Chu

Math. Syst. Theory, 1995

1994

A Comparison of Two Lower Bound Methods for Communication Complexity.

[BibT_eX]

[DOI]

Martin Dietzfelbinger

Proceedings of the Mathematical Foundations of Computer Science 1994, 1994

1993

Two Tapes Versus One for Off-Line Turing Machines.

[BibT_eX]

[DOI]

Comput. Complex., 1993

1992

A note on the complexity of reliability in neural networks.

[BibT_eX]

[DOI]

Piotr Berman

Ian Parberry

IEEE Trans. Neural Networks, 1992

The Power of Approximation: A Comparison of Activation Functions.

[BibT_eX]

[DOI]

Bhaskar DasGupta

Proceedings of the Advances in Neural Information Processing Systems 5, [NIPS Conference, Denver, Colorado, USA, November 30, 1992

Communication Complexity and Lower Bounds for Sequential Computation.

[BibT_eX]

[DOI]

Proceedings of the Informatik, Festschrift zum 60. Geburtstag von Günter Hotz, 1992

1991

The Complexity of Matrix Transposition on One-Tape Off-Line Turing Machines.

[BibT_eX]

[DOI]

Martin Dietzfelbinger

Theor. Comput. Sci., 1991

On the power of white pebbles.

[BibT_eX]

[DOI]

Comb., 1991

On the Computational Power of Sigmoid versus Boolean Threshold Circuits

[BibT_eX]

[DOI]

Eduardo D. Sontag

Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

1990

Rounds Versus Time for the Two Person Pebble Game

[BibT_eX]

[DOI]

Inf. Comput., September, 1990

1989

Rounds versus Time for the Two Person Pebble Game (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the STACS 89, 1989

On the Complexity of Approximating the Independent Set Problem.

[BibT_eX]

[DOI]

Piotr Berman

Proceedings of the STACS 89, 1989

The Communication Complexity of Several Problems in Matrix Computation.

[BibT_eX]

[DOI]

Jeff I. Chu

Proceedings of the ACM Symposium on Parallel Algorithms and Architectures, 1989

1988

On the Power of White Pebbles (Extended Abstract)

[BibT_eX]

[DOI]

Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 1988

1987

Two Tapes Are Better than One for Off-Line Turing Machines

[BibT_eX]

[DOI]

Endre Szemerédi

Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987

Relating Boltzmann Machines to Conventional Models of Computation.

[BibT_eX]

Ian Parberry

Proceedings of the Methodologies for Intelligent Systems, 1987

The probabilistic communication complexity of set intersection.

[BibT_eX]

[DOI]

Proceedings of the Second Annual Conference on Structure in Complexity Theory, 1987

1986

Parallel Computation with Threshold Functions.

[BibT_eX]

[DOI]

Ian Parberry

Proceedings of the Structure in Complexity Theory, 1986

An Optimal Lower Bound for Turing Machines with One Work Tape and a Two- way Input Tape.

[BibT_eX]

[DOI]

Proceedings of the Structure in Complexity Theory, 1986

1984

Lower Bounds on Communication Complexity

[BibT_eX]

[DOI]

Pavol Duris

Zvi Galil

Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30, 1984

1983

On Depth-Reduction and Grates

[BibT_eX]

[DOI]

Proceedings of the 24th Annual Symposium on Foundations of Computer Science, 1983

1982

Elementare Analyse zweier probabilistischer Algorithmen und Tiefenreduktion azyklisch gerichteter Graphen.

[BibT_eX]

[DOI]

PhD thesis, 1982

Three Applications of Kolmogorov-Complexity

[BibT_eX]

[DOI]

Stefan Reisch

Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, 1982

1981

A Family of Graphs with Expensive Depth-Reduction.

[BibT_eX]

[DOI]