Ambiguity and Communication (2009)
Hromkovic, Juraj, Schnitger, Georg
The ambiguity of a nondeterministic finite automaton (NFA) N for input size n is the maximal number of accepting computations of N for an input of size n. For all k, r 2 N we construct languages Lr,k...
Communication complexity method for measuring nondeterminism (2009)
Hromkovic, Juraj, Karhumäki, Juhani, Klauck, Hartmut, Schnitger, Georg, Seibert, Sebastian
Ambiguity and Communication (2009)
Hromkovic, Juraj, Schnitger, Georg
The ambiguity of a nondeterministic finite automaton (NFA) N for input size n is the maximal number of accepting computations of N for an input of size n. For all k, r 2 N we construct languages Lr,k...
Ambiguity and Communication (2009)
Hromkovic, Juraj, Schnitger, Georg
The ambiguity of a nondeterministic finite automaton (NFA) N for input size n is the maximal number of accepting computations of N for an input of size n. For all k, r 2 N we construct languages Lr,k...
Ambiguity and Communication (2009)
Hromkovic, Juraj, Schnitger, Georg
The ambiguity of a nondeterministic finite automaton (NFA) $N$ for input size $n$ is the maximal number of accepting computations of $N$ for an input of size $n$. For all $k,r in mathbb{N}$ we...
A Note on the Complexity of Reliability in Neural Networks (2008)
Piotr Berman, Ian Parberry, Georg Schnitger
It is shown that in a standard discrete neural network model with small fan-in, tolerance to random malicious faults can be achieved with a log-linear increase in the number of neurons and a constant...
On Multi-Partition Communication Complexity (2008)
Martin Sauerhoff, Georg Schnitger
Abstract. We study k-partition communication protocols, an extension of the standard two-party best-partition model to k input partitions. The main results are as follows. 1. A strong explicit...
Bhaskar Dasgupta, Georg Schnitger
We compare activation functions in terms of the approximation power of their feedforward nets. We consider the case of analog as well as boolean input. 1
08381 Executive Summary -- Computational Complexity of Discrete Problems (2008)
Miltersen, Peter Bro, Reischuk, Rüdiger, Schnitger, Georg, Van Melkebeek, Dieter
Estimating the computational complexity of discrete problems constitutes one of the central and classical topics in the theory of computation. Mathematicians and computer scientists have long tried...
08381 Abstracts Collection -- Computational Complexity of Discrete Problems (2008)
Miltersen, Peter Bro, Reischuk, Rüdiger, Schnitger, Georg, Van Melkebeek, Dieter
From the 14th of September to the 19th of September, the Dagstuhl Seminar 08381 ``Computational Complexity of Discrete Problems'' was held in Schloss Dagstuhl - Leibniz Center for Informatics. During...
Juraj Hromkovic, Juhani Karhumaki, Hartmut Klauck, Georg Schnitger, Sebastian Seibert
While deterministic finite automata seem to be well understood, surprisingly many important problems concerning nondeterministic finite automata (nfa's) remain open. One such problem area is the...
Bala Kalyanasundaram, Georg Schnitger
We construct a family fG p: pg of directed acyclic graphs such that any black pebble strategy for G p requires p 2 pebbles whereas 3p + 1 pebbles are sufficient when white pebbles are allowed. 1
proposed running head: THE TWO PERSON PEBBLE GAME (2007)
Bala Kalyanasundaram, Georg Schnitger
Abstract. We show the following results for rounds/time tradeoffs in the two person pebble game. 1. For every R and n (R =O (n /logn)), there is a bounded degree graph of n vertices for which the...
Pavol Duri S, Juraj Hromkovi C, Stasys Jukna, Martin Sauerhoff, Georg Schnitger
Abstract. We study k-partition communication protocols, an extension of the standard two-party best-partition model to k input partitions. The main results are as follows. 1. A strong explicit...
Bhaskar Dasgupta, Georg Schnitger
We compare different gate functions in terms of the approximation power of their circuits. Evaluation criteria are circuit size s, circuit depth d and the approximation error e(s; d). We consider two...
aus der Technisch-Naturwissenschaftlichen Fakultät (2006)
Jan Arpe, Jan Arpe, Berichterstatter Prof, Dr. Rüdiger Reischuk, Prof Dr, ...
In the first place, I would like to thank my Doktorvater Rüdiger Reischuk for giving me the opportunity to work and to carry out my research at the Institut für Theoretische Informatik of the...
Regular Expressions and NFAs Without ε-Transitions (2006)
Abstract. We consider the problem of converting regular expressions into ε-free NFAs with as few transitions as possible. If the regular expression has length n and is defined over an alphabet of...
Minimizing NFA's and Regular Expressions (2005)
Gregor Gramlich, Georg Schnitger
We show inapproximability results concerning minimization of nondeterministic finite automata (nfa's) as well as regular expressions relative to given nfa's, regular expressions or...
On the Greedy Superstring Conjecture (2003)
We investigate the greedy algorithm for the shortest common superstring problem. We show that the length of the greedy superstring is upper-bounded by the sum of the lengths of an optimal superstring...
On the greedy superstring conjecture (2003)
Maik Weinard, Georg Schnitger, Johann Wolfgang
Abstract. We investigate the greedy algorithm for the shortest common superstring problem. We show that the length of the greedy superstring is upper-bounded by the sum of the lengths of an optimal...
On the greedy superstring conjecture (2003)
Abstract. We investigate the greedy algorithm for the shortest common superstring problem. We show that the length of the greedy superstring is upper-bounded by the sum of the lengths of an optimal...
On the Greedy Superstring Conjecture (2003)
We investigate the greedy algorithm for the shortest common superstring problem. For a restricted class of orders in which strings are merged, we show that the length of the greedy superstring is...
Triangle-Freeness is Hard to Detect \Lambda (2002)
Abstract We show that recognizing the K3-freeness and K4-freeness of graphs is hard, respectively, for two-player nondeterministic communication protocols using exponentially many partitions and for...
On Multi-Partition Communication Complexity (2001)
Pavol Duris, Juraj Hromkovic, Stasys Jukna, Martin Sauerhoff, Georg Schnitger
We study k-partition communication protocols, an extension of the standard two-party best-partition model to k input partitions. The main results are as follows.
On multipartition communication complexity (2001)
Juraj Hromkovič, Stasys Jukna, Martin Sauerhoff, Georg Schnitger
Abstract. We study k-partition communication protocols, an extension of the standard two-party best-partition model to k input partitions. The main results are as follows. 1. A strong explicit...
On multi-partition communication complexity (2001)
Pavol Duris, Juraj Hromkovič, Stasys Jukna, Martin Sauerhoff, Georg Schnitger
We study k-partition communication protocols, an extension of the standard two-party best-partition model to k input partitions. The main results are as follows. 1. A strong explicit hierarchy on the...
Communication Complexity Method for Measuring Nondeterminism in Finite Automata (2000)
Hromkovic, Juraj, Karhumäki, Juhani, Klauck, Hartmut, Schnitger, Georg, Seibert, Sebastian
http://www.tucs.fi/Publications/techreports/TR387.php
Communication Complexity Method for Measuring Nondeterminism in Finite Automata (2000)
Hartmut Klauck, Hartmut Klauck, Georg Schnitger, Georg Schnitger, Sebastian Seibert, Sebastian Seibert
While deterministic nite automata seem to be well understood, surprisingly many important problems concerning nondeterministic nite automata (nfa's) remain open. One such problem area is the...
On the Computational Power of Analog Neural Networks (1999)
Bhaskar Dasgupta, Georg Schnitger
Introduction Artificial neural networks are proposed as a tool for machine learning and many results have been obtained regarding their application to practical problems in robotics control, vision,...
On the Computational Power of Analog Neural Networks (1999)
By Bhaskar Dasgupta, Bhaskar Dasgupta, Georg Schnitger
We survey the computational power of analog neural networks. 1 Introduction Artificial neural networks are proposed as a tool for machine learning and many results have been obtained regarding their...
On the Computational Power of Analog Neural Networks Proposed running head: (1999)
Bhaskar Dasgupta, Georg Schnitger
Artificial neural networks are proposed as a tool for machine learning and many results have been obtained regarding their application to practical problems in robotics control, vision, pat-tern...
Practical Issues in the Complexity of Neural Networks. (1998)
Parberry, Ian, Berman, Piotr, Schnitger, Georg
The equipment purchased under this Grant was used to supplement the theoretical work done under AFOSR-87-0400 with experimental results. The primary use of the equipment was to perform experiments to...
A Complexity Theory of Neural Networks. (1998)
Parberry, Ian, Berman, Piotr, Schnitger, Georg
Significant results have been obtained on the computation complexity of analog neural networks, and distribute voting. The computing power and learning algorithms for limited precision analog neural...
A Complexity Theory of Neural Networks. (1998)
Berman, Piotr, Schnitger, Georg, Parberry, Ian
Significant progress has been made in laying the foundations of a complexity theory of neural networks. The fundamental complexity classes have been identified and studied. The class of problems...
Pavol Duris, Juraj Hromkovic, Georg Schnitger
The study of the computational power of randomized computations is one of the central tasks of complexity theory. The main goal of this paper is the comparison of the power of Las Vegas computation...
Analog versus Discrete Neural Networks (1996)
Bhaskar Dasgupta, Georg Schnitger
We show that neural networks with three-times continuously differentiable activation functions are capable of computing a certain family of n-bit Boolean functions with two gates, whereas networks...
Analog versus discrete neural networks (1996)
Bhaskar Dasgupta, Georg Schnitger
We show that neural networks with three-times continuously di erentiable activation functions are capable of computing a certain family of n-bit Boolean functions with two gates, whereas networks...
A Comparison of the Computational Power of Sigmoid and Boolean Threshold Circuits (1994)
Wolfgang Maass, Georg Schnitger, Eduardo D. Sontag
We examine the power of constant depth circuits with sigmoid (i.e. smooth) threshold gates for computing boolean functions. It is shown that, for depth 2, constant size circuits of this type are...
A comparison of the computational power of sigmoid and Boolean threshold circuits (1994)
Wolfgang Maass, Georg Schnitger, Eduardo D. Sontag
We examine the power of constant depth circuits with sigmoid (i.e. smooth) threshold gates for computing boolean functions. It is shown that, for depth 2, constant size circuits of this type are...
The Power of Approximating: a Comparison of Activation Functions (1993)
Bhaskar Dasgupta, Georg Schnitger
We compare activation functions in terms of the approximation power of their feedforward nets. We consider the case of analog as well as boolean input. 1 Introduction We consider efficient...
The Power of Approximating: a Comparison of Activation Functions (1993)
Bhaskar Dasgupta, Georg Schnitger
We compare activation functions in terms of the approximation power of their feedforward nets. We consider the case of analog as well as boolean input. 1 Introduction We consider efficient...
Efficient Approximation with Neural Networks: A Comparison of Gate Functions (1992)
Bhaskar Dasgupta, Georg Schnitger
We compare di#erent gate functions in terms of the approximation power of their circuits. Evaluation criteria are circuit size s, circuit depth d and the approximation error e(s, d). Informally, gate...
Efficient approximation with neural networks: a comparison of gate functions (1680)
Bhaskar Dasgupta, Georg Schnitger
We compare different gate functions in terms of the approximation power of their circuits. Evaluation criteria are circuit size s, circuit depth d and the approximation error e(s, d). Informally,...