13th of November 2003, Musik- und Kongresshalle (MuK) Lübeck, Willy-Brandt-Allee 10
Let k be a positive integer and let E and f be functions. The function E is said to be a k-enumerator for f if, for all x, E(x) is a k-element list containing f(x). The notion of enumerators as an alternative to the traditional concept of approximation was proposed by Cai and Hemachandra in the late 1980s. We study the complexity of two elementary problems in linear algebra, the matrix rank and the matrix determinant, with respect to their approximability using enumerators. We show that, for all constants k and for all finite fields F, if there exists a k-enumerator for the matrix rank over F then the matrix rank over F is AC0-computable with oracle access to the enumerator. For the matrix determinant we show the following two results: (1) If the determinant of integer matrices is polynomial-enumerable by a logspace computable function, then the determinant is logspace computable. (2) For all primes p, if the matrix determinant over Z_p is (p-1)-enumerable in logspace, then the determinant over Z_p is logspace computable. These results shed some light on the complexity of elementary linear algebra problems that are equivalent to the rank or the determinant. Because of the close connection between the determinant and #L, and between the matrix rank and C=L, these results may also offer a better understanding of the power of counting logspace classes, and the relationships among the complexity classes that reside between NL and logspace-uniform TC1.
Short CV of Prof. Ogihara: b. 1963. Ph.D. (1993) Tokyo Institute of Technology. Assistant Professor of Computer Science (1991-93), University of Electro-Communications. Visiting Assistant Professor of Computer Science (1992), State University of New York at Buffalo. Assistant and then Associate Professor of Computer Science (1994- 2002), University of Rochester. Chair of the Department of Computer Science (1999-), University of Rochester. Professor of Computer Science (2002-), University of Rochester.
Research interests: computational complexity, knowledge discovery and data-mining, DNA-based computation.
Die Entwicklung sicherer kryptographischer Protokolle, wie sie z.B. für Online-Banking und Kreditkartentransaktionen eingesetzt werden, ist äusserst fehleranfällig. Eine formale Analyse solcher Protokolle ist deshalb unerlaesslich. Die dazu bisher entwickelten Methoden und Werkzeuge sind jedoch meist nur auf einfache Authentifizierungs- und Schlüsselaustauschprotokolle beschränkt. Zum Beispiel ist die Analyse von Gruppenprotokollen mit bisherigen Mitteln noch nicht in zufriedenstellender Weise möglich. In diesem Vortrag wird zunächst ein Überblick über die Forschung auf dem Gebiet der Analyse kryptographischer Protokolle gegeben, wobei der Schwerpunkt auf Entscheidbarkeits- und Komplexitätsresultaten liegt. Es wird dann ein auf Baum-Transducern basierendes Protokollmodell vorgestellt werden, welches es u.a. erlaubt, bestimmte Aspekte von Gruppenprotokollen zu beschreiben. Schliesslich wird gezeigt, dass für dieses Protokollmodell Sicherheit entscheidbar ist.
Can you distribute n points in the unit square such that each rectangle contains a fraction of the points proportional to its volume? Can you round a non-integral solution of a linear program to an integer one without violating the constraints? Can you split a collection of objects having some specified properties into two in such a way that the properties are evenly split among the resulting two parts? Discrepancy theory tells us that, in general, this is not possible. More over, usually one is even far from reaching these objectives. Nevertheless, for a number of problems interesting solutions exist. In this talk we give an overview of this field and then study a discrepancy problem arising in digital image processing. We use a modification of the well-known randomized rounding technique to obtain significant progress over previoussolutions.
Our interest lies in identifying the distinguishing features of the different genera based on their 16S rDNA sequence data, which could be used further for generating genus specific probes. Pseudomonas, a soil bacterium has been used as a model genus since has been observed as a dominant genus that survives in different habitats with hostile environmental conditions and also has clinical imoprtance. Initialy, we discriminated genus Pseudomonas from Moraxella, Acinetobactor, Burkholderia, and Alcaligene closely related genus based on their dinucleotide composition. The exercise suggested that there exists distinguishing features that could be used to generate genus specific patterns through some pattern generating algorithm. We had a basic assumption that the species level variation in 16S rDNA sequences of a bacterial genus is mainly due to substitutions rather than insertion or deletion of bases. Hence, repeating patterns that are highly conserved across different species of Pseudomonas were considered as guiding markers to a region within the 16S rDNAgene. A sample sequence set of 50 different species for this genus has been retrived. Four repeating patterns showing more than 80% consistency across fifty different species of Pseudomonas were identified. The sub-sequences between the repeating patterns yielded a indel free region of 495 bases. The sub-sequences after alignment and using Shanon's entropy measure yielded consensus and mismatched strings. Also a theoretical primer generation exercise was done using one of the most specific pattern and mismatched strings, which resulted into a PCR product of 150 bp. The species level diversity associated with the expected product was observed. The deisgned PCR primers were used in the wet experiments and has shown the genus level specificity in the priliminary experiments. To validate further different Pseudomonas isolates were evaluated for the specificity of the primer pair.
