15th of November 2001, Musik- und Kongresshalle (MuK) Lübeck, Willy-Brandt-Allee 10
In theory branching programs (BP-s ) are useful for investigation the amount of space necessary to compute various functions.
Developments in the field of digital design and verification have led to the restricted forms of branching programs. A most common model used for verifying circuits is a polynomial size ordered read-once branching program also called an ordered binary decision diagram (for short OBDD). The importance of OBDD for practice based on the following fact: Boolean manipulations with OBDD (equivalence checking, ...) can be performed deterministically in polynomial time. But many important functions (such as multiplication) can not be presented by polynomial size OBDD-s. So, important problem is to investigate the power of "slightly" more general models than OBDD-s.
In the talk we review results on randomized OBDD-s (ROBDD). It was proved
in 1996 that ROBDD-s are more powerful than their deterministic
counterparts.
We present lower bounds proof methods (based on communication games)
and lower bound results for restricted branching programs, namely
OBDD-s, k-OBDD.
Next we present a generalization of read-once branching program, which we call regular (1,+k )-branching program. We present proof methods and new lower bound results for regular (1,+k )-branching program models based on communication complexity techniques.
Quantum computations became intensively growing reseach area in the last decade. We would like to refer to a famous Shor result. The model of classical Branching programs is well known in Practical and Theoretical Computer science. In the talk we introduce a model of a Quantum Branching Program (QBP) and study its computational power. We define several natural restrictions of a general QBP model, such as a read-once and a read-k-times QBP, noting that obliviousness is inherent in a quantum nature of such programs.
In particular we show that any Boolean function can be computed deterministically (exactly) by a read-once QBP in width O(2n), contrary to the analogous situation for quantum finite automata. Further we display known symmetric Boolean function MODpn which is computable by a read-once QBP with O(log pn) width, which requires a width Omega (pn) on any deterministic read-once BP and (classical) randomized read-once BP with permanent transitions in each levels.
We present a general lower bound for the width of read-once QBPs, showing that the upper bound for the considered symmetric function is almost tight.
Seit über 100 Jahren kümmern sich die Naturwissenschaften um die Gesetzmäßigkeiten der Rohstoffe "Materie" und "Energie", während Bauwesen, Maschinenbau, Elektrotechnik usw. dieses Wissen in (hochkomplexe) Geräte und Werkzeuge umsetzen. Ist eine ähnliche Arbeitsteilung beim Rohstoff "Informatik" zu erwarten, d.h., wird die Informatik in Zukunft vorwiegend Grundlagen erforschen, während ingenieurmäßig arbeitende Fächer wie Softwaretechnik, Netzwerktechnik, CAE, Geoinformatik, Kommunikationstechnik usw. die Umsetzung in Systeme, Werkzeuge und deren Instandhaltung realisieren? Werden Dutzende neuer Studiengänge in den nächsten Jahr(zehnt)en unter den verschiedensten Randbedingungen (Branchen, Ausbildungsstätten, Persönlichkeitsbildung, Langlebigkeit) vorbereitet, erprobt und eingerichtet? Welche Methoden, Inhalte und fachspezifischen Vermittlungsmethoden sind hierfür festzulegen? Im Vortrag werden für solche konstruktiv ausgerichteten Studiengänge geeignete Inhalte und Vermittlungstechniken vorgestellt, begründet und (auch im Kontext von e-Learning, Praxissemestern, Interdiszplinarität und Internationalisierung) diskutiert.
Wer ist das, ein(e) Informatiker(in)? Warum gibt es so wenige davon in einer Zeit, in der man sie in Gold aufwöge? Tests aus der Persönlichkeitspsychologie zeigen, dass Informatiker genau so "anders" sind, wie man sie sich gedacht hätte. Ihre Eigenschaften sind etwa die, die man sich intuitiv unter dem Stichwort "New Economy" vorstellen würde. Der Kampf der neuen gegen die alte Ökonomie ist aus dieser Sicht einer der verschiedenen Menschenarten. Der neue Mensch, "E-Man", bestimmt in immer stärkerem Maß, wie "der normale Mensch sein soll". Wird die typische Persönlichkeitsstruktur des Informatikers langsam ein Maß für den Rest der Menschen?
Neues und Querdenkerisches vom Autor der Monographie "Wild Duck, Empirische Philosohpie der Mensch-Computer-Vernetzung", Springer Verlag, 2000 (Kurzbeschreibung und Rezensionen findet man bei www.amazon.de).
Nach einer kurzen Einführung in den MBTI-Persönlichkeitstest werden Statistiken besprochen, welche "Menschen" typischerweise Manager, Computerarchitekten oder Hochschulabgänger oder Lehrer sind. Jede Gruppe ist schwerpunktmäßig anders. Der Vortrag bringt die Problematiken auf den Punkt, den die Verschiedenheiten im Berufsalltag erzeugen. ("Freiheit von Forschung" vs. "Evaluation der Professoren" oder "Ich erziehe gerne Kinder" vs. "Ich liebe Kinder" oder "Ein Projekt soll glänzen" vs. "Hauptsache, alle Termine sind eingehalten" oder "Dieser Mediziner ist eine Koryphäe beim Operieren" vs. "... bei der Diagnose" vs. "...als Seelenprofessor Brinkmann" vs. "...als Wissenschaftler")
Wer sich für diese Thematik vorbereiten möchte, kann sich vorher einem Selbsttest unterziehen.
The topic of set constraints is a pearl among the research topics on constraints. It combines theoretical investigations (ranging from logical expressiveness, decidability, algorithms and complexity analysis to program semantics and domain theory) with practical experiments in building systems for program analysis, addressing questions like implementation issues and scalability. The research has its direct applications in type inference, optimization and verification of imperative, functional, logic and reactive programs. Set constraints are first-order logic formulas interpreted over the domain of sets of trees. These sets of trees are possibly recursively defined. The first-order theory that they form is interesting on its own right. Essentially, we study it because the problem of computationally reasoning about sets (of trees) is fundamentally important. Thus, research on set constraints can be fundamental research. Research on set constraints can also be applied research. This is because set constraints form the algorithmic basis for a certain kind of program analysis that is called set-based. Here, the problem of reasoning about runtime properties of a programs is transferred to the problem of solving set constraints. Several systems have been built, each addressing a particular program analysis problem (obtained, for example, by the restriction to a particular class of programs). The latter means to single out a subclass of set constraints that fits with the analysis problem and to build a system solving set constraints in this subclass (efficiently). In my talk I shall define set constraints, present results concerning complexity of problems concerning set constraints and finally, I will show how set constraints apply to program analysis and to verification of cryptographic protocols.
