Mathematik
Refine
Year of publication
Document Type
- Article (112)
- Doctoral Thesis (76)
- Preprint (48)
- diplomthesis (39)
- Book (25)
- Report (22)
- Conference Proceeding (18)
- Bachelor Thesis (8)
- Contribution to a Periodical (8)
- Diploma Thesis (8)
Has Fulltext
- yes (377)
Is part of the Bibliography
- no (377)
Keywords
- Kongress (6)
- Kryptologie (5)
- Mathematik (5)
- Stochastik (5)
- Doku Mittelstufe (4)
- Doku Oberstufe (4)
- Online-Publikation (4)
- Statistik (4)
- Finanzmathematik (3)
- LLL-reduction (3)
Institute
- Mathematik (377)
- Informatik (56)
- Präsidium (22)
- Physik (6)
- Psychologie (6)
- Geschichtswissenschaften (5)
- Sportwissenschaften (5)
- Biochemie und Chemie (3)
- Biowissenschaften (3)
- Geographie (3)
Integral equations for the mean-square estimate are obtained for the linear filtering problem, in which the noise generating the signal is a fractional Brownian motion with Hurst index h∈(3/4,1) and the noise in the observation process includes a fractional Brownian motion as well as a Wiener process. AMS subject classifications: 93E11, 60G20, 60G35.
In der vorliegenden Arbeit wird ein interaktives Beweisprotokoll für das Problem der "überprüfbaren Verschlüsselung" (verifiable encyption) vorgestellt. Mit Hilfe eines Verifiable Encryption Protokolls (VEP) beweist eine Person (der Prover) einer anderen Person (dem Verifier) effizient, daß ein vorher gesendeter Wert alpha die Verschlüsselung eines geheimen Wertes s ist. Den geheimen Wert s muß er dazu nicht offenlegen. Zur Verschlüsselung von s wird ein Public-Key-Verfahren und ein öffentlicher Schlüssel PK benutzt. PK gehört zum Schlüsselpaar einer dritten Partei, die nicht aktiv an der Protokollausführung beteiligt ist und die Rolle eines Notars einnimmt. Dem Verifier steht ein Wert d zur Verfügung, anhand dessen er entscheidet, ob er den Beweis akzeptiert oder verwirft. Akzeptiert der Verifier den Beweis des Provers, so kann er zwar mit an Sicherheit grenzender Wahrscheinlichkeit sagen, daß alpha eine Verschlüsselung von s unter dem öffentlichen Schlüssel PK ist. Er kann s jedoch nicht rekonstruieren, da er nicht im Besitz des zu PK gehörigen geheimen Schlüssels SK ist und der Beweis keine Informationen über s preisgibt.
Wir werden uns in dieser Arbeit vorwiegend mit einem Modell befassen, das Y. Peres, C. Kenyon, W. Evans und L.J. Schulman 1998 in ihrem Artikel \Broadcasting on trees and the Ising-Modell" eingeführt haben.
In diesem Modell wird ein Signal, das die Werte +1 oder -1 annehmen kann, von der Wurzel eines Baumes aus entlang der Äste eines unendlichgroßen Baumes übertragen. Die Kanten des Baumes agieren dabei als Übertragungskanäle zwischen den Knoten. Jede Kante kann das Signal korrekt übertragen oder es flippen, das heißt, das Vorzeichen des Signals umkehren.
Das Übertragungsverhalten der Kanten ist zufällig. Mit einer festen Wahrscheinlichkeit ϵ, mit 0 < ϵ <= 1/2 , verfälscht eine Kante das Signal. Dies geschieht an allen Kanten unabhängig mit der gleichen Wahrscheinlichkeit. Es stellt sich nun die Frage, wie groß diese Fehlerwahrscheinlichkeit höchstens sein darf, damit das, was in der Krone des Baumes ankommt, noch etwas zu tun hat mit dem, was in der Wurzel eingespeist wird. Mit anderen Worte: Sind die Signale auf Knoten, die einen Abstand >= n von der Wurzel haben, für n -> ∞ asymptotisch unabhängig vom Signal in der Wurzel? Eine Möglichkeit, den Grad der Abhängigkeit zu messen, ist die sogenannte Information, der Kullback-Leibler-Abstand von gemeinsamer Verteilung zur Produkt-Verteilung, die in Definition 16 eingeführt wird.
Wir werden sehen, daß es eine kritische Schwelle ϵc;I für Informationsübertragung gibt. Ist die Fehlerwahrscheinlichkeit größer als ϵc;I , so ist die Information, die zwischen Wurzel und Krone übertragen wird, 0. Ist die Fehlerwahrscheinlichkeit kleiner als ϵc;I , so wird Information übertragen. Dieser kritische Wert ϵc;I hängt nur von der Branching-Number, einer Art mittleren Verzweigungszahl, des Baumes (vgl. Definition 1) ab.
Wir werden sehen, daß das Broadcasting-Modell eine elegante Formulierung eines wohlbekannten Modells, des Ising-Modells, mit freien Randbedingungen, ist.
Im Ising-Modell hat jeder Knoten des Baumes einen "magnetischen" Spin, der entweder +1 oder -1 sein kann. Spins direkt benachbarter Knoten beeinflussen sich, in dem sie versuchen, den gleichen Wert anzunehmen. Diesem Effekt wirkt ein thermischer Einfluß entgegen, der mittels eines als Temperatur bezeichneten Parameters modelliert wird.
Die klassische Frage im Ising-Modell ist, ob Phasenübergang stattfindet. Wir wollen Phasenübergang als das Phänomen verstehen, daß die Wurzel des Baumes die Vorgabe von Randbedingungen auf der Krone des Baumes spürt. Ist dies der Fall, so sagen wir, daß Phasenübergang stattfindet. Auch dies ist eine
Form der gegenseitigen Beeinflussung zwischen Wurzel und Krone des Baumes. Russel Lyons hat 1989 in seinem Artikel \The Ising-Model on trees and treelike Graphs" das Ising-Modell auf Bäumen untersucht und gezeigt, daß es eine kritische Temperatur tc für Phasenübergang gibt. Ist die Temperatur höher als tc, so spürt die Wurzel nichts von den Randbedingungen der Krone; ist die Temperatur geringer als tc, so haben die Randbedingungen Einfluß auf die Wurzel. Auch hier hängt die kritische Temperatur nur von der Branching-Number des Baumes ab.
In der Broadcasting-Formulierung des Modells ist der Fluß von Information ein naheliegendes Werkzeug, um die Beeinflussung von Wurzel und Krone zu messen, in der Ising-Formulierung ist die Existenz von Phasenübergang ein ebenso naheliegendes Werkzeug, ebendiesen Einfluß zu messen.
Wir werden die beiden Arten der Beeinflussung miteinander vergleichen und können zeigen, daß für die Übertragung von Information stets eine stärkere Interaktion zwischen den Knoten notwendig ist, als für den Einfluß der Randbedingungen aus der Krone.
Als letztes Phänomen werden wir untersuchen, ob es einen Pfad im Baum gibt, der in der Wurzel startend nur Knoten gleichen Spins besucht und die unendlich weit entfernte Krone erreicht. Wir bezeichnen dieses Phänomen als Spinperkolation.
Wir werden die Berechnung der kritischen Interaktion für Spinperkolation in einem Bernoulli-Feld auf den Kanten rekapitulieren und dann zeigen, daß die Existenz eines Perkolationspfades nur von der Interaktionsstärke des Modells und nicht von etwaigen Randbedingungen abhängt. Dabei kombinieren wir Ergebnisse aus zwei Arbeiten von Lyons und die Erkenntnis, daß Broadcasting- Modell und freies Ising-Modell identisch sind. Wir erhalten so einen neuen, einfachen Beweis über die kritische Interaktion für Spinperkolation in der Plus-Phase des Ising-Modells, die Lyons bereits in [7] berechnet hat.
New conditions of solvability based on a general theorem on the calculation of the index at infinity for vector fields that have degenerate principal linear part as well as degenerate ... next order ... terms are obtained for the 2 Pi-periodic problem for the scalar equation x'' +n2x=g(|x|)+f(t,x)+b(t) with bounded g(u) and f(t,x) -> 0 as |x| -> 0. The result is also applied to the solvability of a two-point boundary value problem and to resonant problems for equations arising in control theory.
AMS subject classifications: 47Hll, 47H30.
Assuming a cryptographically strong cyclic group G of prime order q and a random hash function H, we show that ElGamal encryption with an added Schnorr signature is secure against the adaptive chosen ciphertext attack, in which an attacker can freely use a decryption oracle except for the target ciphertext. We also prove security against the novel one-more-decyption attack. Our security proofs are in a new model, corresponding to a combination of two previously introduced models, the Random Oracle model and the Generic model. The security extends to the distributed threshold version of the scheme. Moreover, we propose a very practical scheme for private information retrieval that is based on blind decryption of ElGamal ciphertexts.
Let G be a group of prime order q with generator g. We study hardcore subsets H is include in G of the discrete logarithm (DL) log g in the model of generic algorithms. In this model we count group operations such as multiplication, division while computations with non-group data are for free. It is known from Nechaev (1994) and Shoup (1997) that generic DL-algorithms for the entire group G must perform p2q generic steps. We show that DL-algorithms for small subsets H is include in G require m/ 2 + o(m) generic steps for almost all H of size #H = m with m <= sqrt(q). Conversely, m/2 + 1 generic steps are su±cient for all H is include in G of even size m. Our main result justifies to generate secret DL-keys from seeds that are only 1/2 * log2 q bits long.
Es steht außer Zweifel, daß digitale Signaturen schon bald zu unserem Alltag gehören wer- den. Spätestens mit dem Inkrafttreten des Gesetzes zur digitalen Signatur (siehe [BMB]) sind sie zu einem wichtigen Instrument in der Telekommunikation geworden. Dabei kommt der Verwendung von Chipkarten eine wichtige Bedeutung zu: In ihnen lassen sich die sensiblen Daten (z.B. der geheime Schlüssel) auslesesicher aufbewahren; gleichzeitig können sie bequem mitgeführt werden. Aus diesen Gründen erlebt die Verwendung von Chipkarten zur Erzeugung von digitalen Signaturen zur Zeit einen enormen Aufschwung. Problematisch ist jedoch der oft unverhältnismäßig große Berechnungsaufwand für die Erzeugung von digitalen Signaturen. Ziel dieser Arbeit ist es, Methoden zu entwickeln und/oder zu untersuchen, welche die Berechnung digitaler Unterschriften wesentlich beschleunigen. Dabei spiegelt sich die Zweiteilung der in der Praxis hauptsächlich verwendeten Typen von Signaturverfahren in der Struktur der Arbeit wider. Der erste Teil dieser Arbeit untersucht Verfahren zur effizienten Berechnung von RSA-Unterschriften. Dabei entstanden die Untersuchungen in den Abschnitten 3.2.3 und 3.2.4 in Zusammenarbeit mit R. Werchner und der Inhalt der Abschnitte 3.1 - 3.2.4 ist bereits in [MW98] veröffentlicht. Im zweiten Teil entwickeln wir Verfahren zur effizienteren Generierung von Unterschriften, die auf dem diskreten Logarithmus basieren, und untersuchen deren Sicherheit. Dabei entstanden die Untersuchungen in den Abschnitten 4.2 (bis auf 4.2.2) und 4.3.1 in Zusammenarbeit mit C. P. Schnorr und sind teilweise in [MS98] zusammengefaßt. Obwohl diese Arbeit eine mathematische Abhandlung darstellt, versuchen wir, die praktische Anwendung nicht aus den Augen zu verlieren. So orientieren sich die betrachteten Verfahren stets an den durch die verfügbare Technologie gegebenen Rahmenbedingungen. Darüber hinaus richten wir unser Augenmerk weniger auf das asymptotische Verhalten der betrachteten Verfahren, als vielmehr auf konkrete, für die Anwendung relevante Beispiele.
In this paper, a translation of the visual description technique HyCharts to Hybrid Data-Flow Graphs (HDFG) is given. While HyCharts combine a data-flow and a control-flow oriented formalism for the specification of the architecture and the behavior of hybrid systems, HDFG allow the efficient and homogeneous internal representation of hybrid systems in computers and their automatic manipulation. HDFG represent a system as a data-flow network built from a set of fundamental functions.
The translation permits to combine the advantages of the different description techniques: The use of HyCharts for specification supports the abstract and formal interactive specification of hybrid systems, while HDFG permit the tool based optimization of hybrid systems and the synthesis of mixed-signal prototypes.
We present efficient non-malleable commitment schemes based on standard assumptions such as RSA and Discrete-Log, and under the condition that the network provides publicly available RSA or Discrete-Log parameters generated by a trusted party. Our protocols require only three rounds and a few modular exponentiations. We also discuss the difference between the notion of non-malleable commitment schemes used by Dolev, Dwork and Naor [DDN00] and the one given by Di Crescenzo, Ishai and Ostrovsky [DIO98].
Gitter
(2000)
Komplexität von Gitterproblemen : Nicht-Approximierbarkeit und Grenzen der Nicht-Approximierbarkeit
(2000)
Ein Gitter vom Rang n ist die Menge der ganzzahligen Linerkombinationen von n linear unabhängigen Vektoren im Rm. Unter der Annahme P <> NP beweisen wir, daß kein Polynomialzeit-Algorithmus existiert, der eine kürzeste Gitterbasis bis auf einen Faktor nO exp(1/log log n) berechnet, wobei die Länge einer Menge von Vektoren durch die maximale Euklidische Länge der Vektoren definiert ist. Weiter zeigen wir, daß eine Verbesserung dieses Resultates bis hin zu einem Faktor n/ sqrt(log n) unter plausiblen Annahmen nicht möglich ist. Ein simultaner Diophantischer Best Approximations Nenner für reelle Zahlen alpha1, .... , alpha n und Hauptnennerschranke N ist eine natürliche Zahl q mit 1 <= q >= N, so daß maxi minp2Z |q alpha i - p| minimal ist. Unter der Annahme, daß die Klasse NP keine fast-polynomiellen Algorithmen besitzt, beweisen wir, daß kein Polynomialzeit-Algorithmus existiert, der für gegebene rationale Zahlen. Ein Gitter vom Rang n ist die Menge der ganzzahligen Linerkombinationen von n linear unabhängigen Vektoren im Rm. Unter der Annahme P 6= NP beweisen wir, daß kein Polynomialzeit-Algorithmus existiert, der eine kürzeste Gitterbasis bis auf einen Faktor nO(1= log log n) berechnet, wobei die Länge einer Menge von Vektoren durch die maximale Euklidische Länge der Vektoren definiert ist. Weiter zeigen wir, daß eine Verbesserung dieses Resultates bis hin zu einem Faktor n=plog n unter plausiblen Annahmen nicht möglich ist. Ein simultaner Diophantischer Best Approximations Nenner für reelle Zahlen alpha1, .... , alpha n und Hauptnennerschranke N ist eine natürliche Zahl q mit 1 <= q <= N, so daß maxi ...... minimal ist. Unter der Annahme, daß die Klasse NP keine fast-polynomiellen Algorithmen besitzt, beweisen wir, daß kein Polynomialzeit-Algorithmus existiert, der für gegebene rationale Zahlen alpha1,......, alphan und eine Hauptnennerschranke N einen Nenner ~q mit 1 <= ~q <= f(n)N berechnet, so daß ~q bis auf einen Faktor f(n) = nO(1= log0:5+epsilon n) ein Best Approximations Nenner ist, wobei epsilon > 0 eine beliebige Konstante ist. Wir zeigen, daß eine Verbesserung dieses Resultates bis hin zu einem Faktor n=log n unter plausiblen Annahmen nicht mölich ist. Wir untersuchen die Konsequenzen dieser Resultate zur Konstruktion von im Durchschnitt schwierigen Gitterproblemen.
Linear-implicit versions of strong Taylor numerical schemes for finite dimensional Itô stochastic differential equations (SDEs) are shown to have the same order as the original scheme. The combined truncation and global discretization error of an gamma strong linear-implicit Taylor scheme with time-step delta applied to the N dimensional Itô-Galerkin SDE for a class of parabolic stochastic partial differential equation (SPDE) with a strongly monotone linear operator with eigenvalues lambda 1 <= lambda 2 <= ... in its drift term is then estimated by K(lambda N -½ + 1 + delta gamma) where the constant K depends on the initial value, bounds on the other coefficients in the SPDE and the length of the time interval under consideration.
AMS subject classifications: 35R60, 60H15, 65M15, 65U05.
Diese Arbeit befasst sich mit der Zerlegung von Irrfahrten und Lévy Prozessen an ihrem Minimum. Bis auf rudimentäre Vorkenntnisse der höheren Stochastik und einige wenige aber wichtige Sätze stellt die Arbeit alle notwendigen Begriffe und Sätze zur Verfügung, die für das Verständnis und die Beweise benötigt werden. Diese bewusste Entscheidung zur Ausführlichkeit auch bei grundlegenden Dingen hat zwei Hintergründe: Zum einen bleibt die Arbeit damit auch für Leser mit geringen Vorkenntnissen interessant, und zum anderen entsteht so keine lange und unübersichtliche Kette von Verweisen und Zitaten, die das Verständnis des dargestellten Themas erschwert und die logischen Schlüsse nur noch von Spezialisten vollständig nachvollzogen werden können. Ein weiterer Nebeneffekt ist die Tatsache, dass Verwirrungen aufgrund unterschiedlicher Interpretationen eines Begriffs vermieden werden. Das weitere Vorwort teilt sich in zwei Abschnitte; zum einen in den Abschnitt der Irrfahrten und zum anderen in den Abschnitt der Lévy-Prozesse. Diese Einteilung spiegelt auch die Strukturierung der Arbeit selber wieder; ein Blick in das Inhaltsverzeichnis verrät, dass zuerst Irrfahrten und danach Lévy Prozesse behandelt werden.
Bei der Untersuchung des Langzeitverhaltens von Verzweigungsprozessen und räumlich verzweigenden Populationen ist die Betrachtung von Stammbäumen zunehmend in den Vordergrund gerückt. Probabilistische Methoden haben die in der Theorie vorherrschenden analytischen Techniken ergänzt und zu wesentlichen neuen Einsichten geführt. Die vorliegende Synopse diskutiert eine Auswahl meiner Veröffentlichungen der letzten Jahre. Den Arbeiten ist gemeinsam, dass durch das Studium der genealogischen Verhältnisse in der Population Aussagen über deren Langzeitverhalten gewonnen werden konnten. Zwei dieser Arbeiten behandeln den klassischen Galton-Watson Prozess. Eine weitere Arbeit befasst sich mit Verzweigungsprozessen in zufälliger Umgebung, sie ist technische wesentlich anspruchsvoller. Die vierte der hier besprochenen Arbeiten beschäftigt sich mit dem Wählermodell, einem der Prototypen interagierender Teilchensysteme.
We present a novel parallel one-more signature forgery against blind Okamoto-Schnorr and blind Schnorr signatures in which an attacker interacts some times with a legitimate signer and produces from these interactions signatures. Security against the new attack requires that the following ROS-problem is intractable: find an overdetermined, solvable system of linear equations modulo with random inhomogenities (right sides). There is an inherent weakness in the security result of POINTCHEVAL AND STERN. Theorem 26 [PS00] does not cover attacks with 4 parallel interactions for elliptic curves of order 2200. That would require the intractability of the ROS-problem, a plausible but novel complexity assumption. Conversely, assuming the intractability of the ROS-problem, we show that Schnorr signatures are secure in the random oracle and generic group model against the one-more signature forgery.
We present a practical algorithm that given an LLL-reduced lattice basis of dimension n, runs in time O(n3(k=6)k=4+n4) and approximates the length of the shortest, non-zero lattice vector to within a factor (k=6)n=(2k). This result is based on reasonable heuristics. Compared to previous practical algorithms the new method reduces the proven approximation factor achievable in a given time to less than its fourthth root. We also present a sieve algorithm inspired by Ajtai, Kumar, Sivakumar [AKS01].
Informally, commitment schemes can be described by lockable steely boxes. In the commitment phase, the sender puts a message into the box, locks the box and hands it over to the receiver. On one hand, the receiver does not learn anything about the message. On the other hand, the sender cannot change the message in the box anymore. In the decommitment phase the sender gives the receiver the key, and the receiver then opens the box and retrieves the message. One application of such schemes are digital auctions where each participant places his secret bid into a box and submits it to the auctioneer. In this thesis we investigate trapdoor commitment schemes. Following the abstract viewpoint of lockable boxes, a trapdoor commitment is a box with a tiny secret door. If someone knows the secret door, then this person is still able to change the committed message in the box, even after the commitment phase. Such trapdoors turn out to be very useful for the design of secure cryptographic protocols involving commitment schemes. In the first part of the thesis, we formally introduce trapdoor commitments and extend the notion to identity-based trapdoors, where trapdoors can only be used in connection with certain identities. We then recall the most popular constructions of ordinary trapdoor protocols and present new solutions for identity-based trapdoors. In the second part of the thesis, we show the usefulness of trapdoors in commitment schemes. Deploying trapdoors we construct efficient non-malleable commitment schemes which basically guarantee indepency of commitments. Furthermore, applying (identity-based) trapdoor commitments we secure well-known identification protocols against a new kind of attack. And finally, by means of trapdoors, we show how to construct composable commitment schemes that can be securely executed as subprotocols within complex protocols.
We propose a new security measure for commitment protocols, called Universally Composable (UC) Commitment. The measure guarantees that commitment protocols behave like an \ideal commitment service," even when concurrently composed with an arbitrary set of protocols. This is a strong guarantee: it implies that security is maintained even when an unbounded number of copies of the scheme are running concurrently, it implies non-malleability (not only with respect to other copies of the same protocol but even with respect to other protocols), it provides resilience to selective decommitment, and more. Unfortunately two-party uc commitment protocols do not exist in the plain model. However, we construct two-party uc commitment protocols, based on general complexity assumptions, in the common reference string model where all parties have access to a common string taken from a predetermined distribution. The protocols are non-interactive, in the sense that both the commitment and the opening phases consist of a single message from the committer to the receiver.
Based on the quadratic residuosity assumption we present a non-interactive crypto-computing protocol for the greater-than function, i.e., a non-interactive procedure between two parties such that only the relation of the parties' inputs is revealed. In comparison to previous solutions our protocol reduces the number of modular multiplications significantly. We also discuss applications to conditional oblivious transfer, private bidding and the millionaires' problem.
In dieser Arbeit werden Darstellungen der Artinschen Zopfgruppen als Gruppen von Automorphismen der Homologie iterativ konstruierter äquivarianter Kettenkomplexe betrachtet. Es werden azyklische Komplexe freier Moduln bzw. freie Auflösungen der ganzen Zahlen für nichtpermutierte Artinsche Zopfgruppen konstruiert, die als iterierte semidirekte Produkte freier Gruppen darstellbar sind. Als Tensorprodukte der freien Auflösungen mit Moduln zu den fraglichen iterierten semidirekten Produkten freier Gruppen erhält man äquivariante Komplexe, deren von Eigenschaften der Koeffizientenmoduln abhängige Homologiegruppen bestimmt werden. Diese Homologiegruppen erlauben Automorphismendarstellungen der (permutierten) Artinschen Zopfgruppe, die gewissermaßen die Artinschen Darstellungen als Automorphismengruppen freier Gruppen iterieren und linearisieren. Insbesondere werden Darstellungen gewonnen, die die bekannten Burau- und Gassner-Darstellungen der Zopfgruppen verallgemeinern und die als Monodromiegruppen verallgemeinerter hypergeometrischer Integrale interpretiert werden können.
Bipartite graphs occur in many parts of mathematics, and their embeddings into orientable compact surfaces are an old subject. A new interest comes from the fact that these embeddings give dessins d’enfants providing the surface with a unique structure as a Riemann surface and algebraic curve. In this paper, we study the (surprisingly many different) dessins coming from the graphs of finite cyclic projective planes. It turns out that all reasonable questions about these dessins — uniformity, regularity, automorphism groups, cartographic groups, defining equations of the algebraic curves, their fields of definition, Galois actions — depend on cyclic orderings of difference sets for the projective planes. We explain the interplay between number theoretic problems concerning these cyclic ordered difference sets and topological properties of the dessin like e.g. the Wada property that every vertex lies on the border of every cell.
Es wird eine Einführung in den Satz von Belyi und Grothendiecks Dessins d'enfants gegeben, hier Kinderzeichnungen genannt. Dieses Arbeitsgebiet ist in den letzten zwanzig Jahren entstanden und weist viele reizvolle Querverbindungen auf von der inversen Galoistheorie über die Teichm llerräume bis hin zur Mathematischen Physik. Das Schwergewicht des folgenden Beitrags liegt in den Beziehungen zu den Fuchsschen Gruppen und der Uniformisierungstheorie: Kinderzeichnungen bieten die Möglichkeit, für arithmetisch interessante Riemannsche Flächen - die als algebraische Kurven über Zahlkörpern definiert sind - Überlagerungsgruppen explizit zu beschreiben und umgekehrt aus gewissen Typen von Überlagerungsgruppen Kurvengleichungen zu gewinnen. Was hier aufgeschrieben ist, behandelt eigentlich nur bekanntes Material, gelegentlich mit neuen Beweisvarianten und Beispielen. Da aber noch keine zusammenfassende Einführung in das Thema existiert, hoffe ich, dass es als Vorlage für ein Seminar oder eine fortgeschrittene Vorlesung nützlich sein mag.
This thesis exhibits skeins based on the Homfly polynomial and their relations to Schur functions. The closures of skein-theoretic idempotents of the Hecke algebra are shown to be specializations of Schur functions. This result is applied to the calculation of the Homfly polynomial of the decorated Hopf link. A closed formula for these Homfly polynomials is given. Furthermore, the specialization of the variables to roots of unity is considered. The techniques are skein theory on the one side, and the theory of symmetric functions in the formulation of Schur functions on the other side. Many previously known results have been proved here by only using skein theory and without using knowledge about quantum groups.
This extended write-up of a talk gives an introductory survey of mathematical problems of the quantization of gauge systems. Using the Schwinger model as an exactly tractable but nontrivial example which exhibits general features of gauge quantum field theory, I cover the following subjects: The axiomatics of quantum field theory, formulation of quantum field theory in terms of Wightman functions, reconstruction of the state space, the local formulation of gauge theories, indefiniteness of the Wightman functions in general and in the special case of the Schwinger model, the state space of the Schwinger model, special features of the model. New results are contained in the Mathematical Appendix, where I consider in an abstract setting the Pontrjagin space structure of a special class of indefinite inner product spaces - the so called quasi-positive ones. This is motivated by the indefinite inner product space structure appearing in the above context and generalizes results of Morchio and Strocchi [J. Math. Phys. 31 (1990) 1467], and Dubin and Tarski [J. Math. Phys. 7 (1966) 574]. See the corresponding paper: Schmidt, Andreas U.: "Infinite Infrared Regularization and a State Space for the Heisenberg Algebra" and the presentation "Infinite Infrared Regularization in Krein Spaces".
We present an efficient variant of LLL-reduction of lattice bases in the sense of Lenstra, Lenstra, Lov´asz [LLL82]. We organize LLL-reduction in segments of size k. Local LLL-reduction of segments is done using local coordinates of dimension 2k. Strong segment LLL-reduction yields bases of the same quality as LLL-reduction but the reduction is n-times faster for lattices of dimension n. We extend segment LLL-reduction to iterated subsegments. The resulting reduction algorithm runs in O(n3 log n) arithmetic steps for integer lattices of dimension n with basis vectors of length 2O(n), compared to O(n5) steps for LLL-reduction.
Staatsexamensarbeit 2002. In der nachfolgenden Arbeit werde ich im zweiten Kapitel theoretisch fraktionale Ableitungen vorstellen, um dann im dritten Kapitel praktisch mit MAPLE fraktionale Ableitungen zu veranschaulichen. Genauso werde ich auch das Gebiet der fraktionalen Differentialgleichungen einführen, d.h. zuerst wird ein theoretischer Teil über Lösungsmethoden behandelt und darauf folgend ein praktischer Teil, in dem mittels MAPLE diverse Gleichungen gelöst werden. Das zweite Dokument enthält MAPLE Programme aus der Arbeit (ZIP-Format, 145154 Bytes).
The dynamical quantum Zeno effect is studied in the context of von Neumann algebras. It is shown that the Zeno dynamics coincides with the modular dynamics of a localized subalgebra. This relates the modular operator of that subalgebra to the modular operator of the original algebra by a variant of the Kato-Lie-Trotter product formula.
We reconsider estimates for the heat kernel on weighted graphs recently found by Metzger and Stollmann. In the case that the weights satisfy a positive lower bound as well as a finite upper bound, we obtain a specialized lower estimate and a proper generalization of a previous upper estimate. Reviews: Math. Rev. 1979406, Zbl. Math. 0934.46042
In der vorliegenden Arbeit werden Aspekte autonomer und nichtautonomer dynamischer Systeme behandelt, wobei Attraktoren und verwandte Objekte eine wichtige Rolle spielen werden. Zunächst findet man in einem Kapitel über dynamische Systeme die Definition der grundlegenden Begriffe Attraktor, Repeller und Schiefproduktfluss, gefolgt von zwei hinreichenden Bedingungen für die Existenz von Attraktoren. Mit den Attraktoren und Repellern können dann im nächsten Kapitel Morsemengen eingeführt werden. Dadurch kann das Verhalten eines dynamischen Systems qualitativ beschrieben werden. Des weiteren wird auf die Bedeutung der Kettenrekurrenzmenge für die Morsemengen eingegangen. Im Kapitel über Kontrolltheorie wird, nach einer kurzen Einführung in dieses Gebiet, gezeigt, dass der dort definierte Lift einer Kettenkontrollmenge unter gewissen Voraussetzungen eine Morsemenge ist. Im letzten Kapitel geht es um Pullback-Attraktoren, die unter den angegebenen Bedingungen als Attraktoren für den Schiefproduktfluss interpretiert werden können.
Die vorliegende Arbeit beschäftigt sich mit der Ermittlung des Preises von Optionen. Optionen sind spezielle Derivate, die wiederum Hull in seinem Buch definiert als: Ein Derivat ist ein Finanzinstrument, dessen Wert von einem anderen, einfacheren zu Grunde liegenden Finanzinstrument (underlying) abhängt . Ein underlying kann unter anderem auch eine Anleihe, eine Aktie oder der Umtauschkurs zweier Währungen sein....
We show that P(n)*(P(n)) for p = 2 with its geometrically induced structure maps is not an Hopf algebroid because neither the augmentation Epsilon nor the coproduct Delta are multiplicative. As a consequence the algebra structure of P(n)*(P(n)) is slightly different from what was supposed to be the case. We give formulas for Epsilon(xy) and Delta(xy) and show that the inversion of the formal group of P(n) is induced by an antimultiplicative involution Xi : P(n) -> P(n). Some consequences for multiplicative and antimultiplicative automorphisms of K(n) for p = 2 are also discussed.
We show that non-interactive statistically-secret bit commitment cannot be constructed from arbitrary black-box one-to-one trapdoor functions and thus from general public-key cryptosystems. Reducing the problems of non-interactive crypto-computing, rerandomizable encryption, and non-interactive statistically-sender-private oblivious transfer and low-communication private information retrieval to such commitment schemes, it follows that these primitives are neither constructible from one-to-one trapdoor functions and public-key encryption in general. Furthermore, our separation sheds some light on statistical zeroknowledge proofs. There is an oracle relative to which one-to-one trapdoor functions and one-way permutations exist, while the class of promise problems with statistical zero-knowledge proofs collapses in P. This indicates that nontrivial problems with statistical zero-knowledge proofs require more than (trapdoor) one-wayness.
We review the representation problem based on factoring and show that this problem gives rise to alternative solutions to a lot of cryptographic protocols in the literature. And, while the solutions so far usually either rely on the RSA problem or the intractability of factoring integers of a special form (e.g., Blum integers), the solutions here work with the most general factoring assumption. Protocols we discuss include identification schemes secure against parallel attacks, secure signatures, blind signatures and (non-malleable) commitments.
Motivation: The topic of this paper is the estimation of alignments and mutation rates based on stochastic sequence-evolution models that allow insertions and deletions of subsequences ("fragments") and not just single bases. The model we propose is a variant of a model introduced by Thorne, Kishino, and Felsenstein (1992). The computational tractability of the model depends on certain restrictions in the insertion/deletion process; possible effects we discuss.
Results: The process of fragment insertion and deletion in the sequence-evolution model induces a hidden Markov structure at the level of alignments and thus makes possible efficient statistical alignment algorithms. As an example we apply a sampling procedure to assess the variability in alignment and mutation parameter estimates for HVR1 sequences of human and orangutan, improving results of previous work. Simulation studies give evidence that estimation methods based on the proposed model also give satisfactory results when applied to data for which the restrictions in the insertion/deletion process do not hold.
Availability: The source code of the software for sampling alignments and mutation rates for a pair of DNA sequences according to the fragment insertion and deletion model is freely available from www.math.uni-frankfurt.de/~stoch/software/mcmcsalut under the terms of the GNU public license (GPL, 2000).
Okamoto (Crypto 1992) hat die RSA-Repräsentation als Basis eines gegen aktive Angreifer sicheren Identifikationsschemas eingeführt. Eine RSA- Repräsentation von X E Z * N ist ein Paar (x; r) E Z e x Z * N mit X = g x r e (mod N) für vorgegebenes g E ZN , RSA-Modul N und primen RSA- Exponenten e. Das zugehörige Repräsentationsproblem, also das Auffinden eines Wertes X samt zweier verschiedener Darstellungen, ist äquivalent zum RSA-Problem, der Berechnung einer e-ten Wurzel von g modulo N . Von Brassard, Chaum und Crépeau (Journal Computing System Science, 1988) sowie Damgard (Journal of Cryptology, 1995) stammt eine analoge Konstruktion der Form X = g x r 2 t (mod N) mit x E Z 2 t für den Spezialfall der Blum-Zahlen als Modul N und gegebenes t größer gleich 1, wo die Möglichkeit, zwei verschiedene Repräsentationen zu berechnen, gleichbedeutend zur Zerlegung des Moduls in die Primfaktoren ist. Im ersten Abschnitt der vorliegenden Arbeit verallgemeinern wir dieses Konzept systematisch auf beliebige (RSA-)Module durch die Einführung eines Anpassungsparameters r:= r (N ), so dass X = g x r 2 r t (mod N) mit x E Z 2 t. Basierend auf dieser als Faktorisierungsrepräsentation bezeichneten Darstellung leiten wir Identifikations-, Signatur- und Blinde-Unterschriften-Verfahren her. Im zweiten Teil verwenden wir sowohl RSA- als auch Faktorisierungsrepräsentation als Grundlage sogenannter non-malleable Commitment-Schemata zur Hinterlegung (Verbriefung) einer geheimen Nachricht. Bei dem von Dolev, Dwork und Naor (SIAM Journal on Computing, 2000) eingeführten Begriff der Non-Malleability soll ein Angreifer außer Stande sein, die Hinterlegung einer Nachricht m so abzuändern, dass er diese später dann mit einem in Relation zu m stehenden Wert, man denke zum Beispiel an m 1, aufdecken kann. Von Dolev, Dwork und Naor stammt ein allgemeiner Ansatz zur Konstruktion von non-malleable Commitment-Schemata aufbauend auf einem sogenannten Knowledge-Extraktor. Für die RSA-Darstellung verfügt das von Okamoto entworfene Protokoll als Proof-Of-Knowledge über einen solchen Extraktor, bei dem im Fall der Faktorisierungsrepräsentation von uns entwickelten Verfahren fehlt allerdings der Extraktor. Aus diesem Grund stellen wir mit Hilfe des Chinesischen Restsatzes ein neues, auf Commitments zugeschnittenes Protokoll mit Knowledge-Extraktor vor, das in Verbindung mit der Faktorisierungsrepräsentation ein effizientes Hinterlegungsschema ergibt. Zum Abschluß wird bei einem Commitment- Verfahren mit abgeschwächter Non-Malleability-Eigenschaft von Di Crescenzo, Katz, Ostrovsky und Smith (Eurocrypt 2001) die RSA- durch die Faktorisierungsrepräsentation ersetzt und das Schema vereinfacht.
Ein Mathematiker mit universalem Anspruch : über Max Dehn und sein Wirken am Mathematischen Seminar
(2002)
Für eine erste Blüte der Mathematik in Frankfurt gab Max Dehn (1878 –1952) in den Jahren ab 1921 bis 1935 entscheidende Impulse. Seine völlig neuen Ideen zur Knotentheorie und zur Topologie beeinflussten die Entwicklung der Mathematik weit über Deutschland hinaus. 1935 fand sein Wirken in Frankfurt durch den Terror der Nationalsozialisten ein jähes Ende. Nach einer gefahrvollen Flucht über Norwegen, Finnland, die Sowjetunion und Japan erreichte Dehn schließlich, 62-jährig, die Vereinigten Staaten von Nordamerika. Eine seinen Fähigkeiten entsprechende Stellung konnte er dort nicht mehr erlangen. Sein fünfzigster Todestag in diesem Jahr ist Anlass für diese Rückschau.
The synchronization of neuronal firing activity is considered an important mechanism in cortical information processing. The tendency of multiple neurons to synchronize their joint firing activity can be investigated with the 'unitary event' analysis (Grün, 1996). This method is based on the nullhypothesis of independent Bernoulli processes and can therefore not tell whether coincidences observed between more than two processes can be considered "genuine" higher- order coincidences or whether they might be caused by coincidences of lower order that coincide by chance ("chance coincidences"). In order to distinguish between genuine and chance coincidences, a parametric model of independent interaction processes (MIIP) is presented. In the framework of this model, Maximum-Likelihood estimates are derived for the firing rates of n single processes and for the rates with which genuine higher order correlations occur. The asymptotic normality of these estimates is used to derive their asymptotic variance and in order to investigate whether higher order coincidences can be considered genuine or whether they can be explained by chance coincidences. The empirical test power of this procedure for n=2 and n=3 processes and for finite analysis windows is derived with simulations and compared to the asymptotic values. Finally, the model is extended in order to allow for the analysis of correlations that are caused by jittered coincidences.
We consider the long-time behaviour of spatially extended random populations with locally dependent branching. We treat two classes of models: 1) Systems of continuous-time random walks on the d-dimensional grid with state dependent branching rate. While there are k particles at a given site, a branching event occurs there at rate s(k), and one of the particles is replaced by a random number of offspring (according to a fixed distribution with mean 1 and finite variance). 2) Discrete-time systems of branching random walks in random environment. Given a space-time i.i.d. field of random offspring distributions, all particles act independently, the offspring law of a given particle depending on its position and generation. The mean number of children per individual, averaged over the random environment, equals one The long-time behaviour is determined by the interplay of the motion and the branching mechanism: In the case of recurrent symmetrised individual motion, systems of the second type become locally extinct. We prove a comparison theorem for convex functionals of systems of type one which implies that these systems also become locally extinct in this case, provided that the branching rate function grows at least linearly. Furthermore, the analysis of a caricature model leads to the conjecture that local extinction prevails generically in this case. In the case of transient symmetrised individual motion the picture is more complex: Branching random walks with state dependent branching rate converge towards a non-trivial equilibrium, which preserves the initial intensity, whenever the branching rate function grows subquadratically. Systems of type 1) and systems of type 2) with quadratic branching rate function show very similar behaviour. They converge towards a non-trivial equilibrium if a conditional exponential moment of the collision time of two random walks of an order that reflects the variability in the branching mechanism is finite almost surely. The equilibrium population has finite variance of the local particle number if the corresponding unconditional exponential moment is finite. These results are proved by means of genealogical representations of the locally size-biased population. Furthermore, we compute the threshold values for existence of conditional exponential moments of the collision time of two random walks in terms of the entropy of the transition functions, using tools from large deviations theory. Our results prove in particular that - in contrast to the classical case of independent branching - there is a regime of equilibria with variance of the local number of particles.
Große Stammbäume
(2003)
Sei T ein kritischer oder subkritischer Galton-Watson Stammbaum (GW-Baum) mit einer Kinderzahlverteilung endlicher oder unendlicher Varianz. Wir sind an der Struktur von T , bedingt darauf, dass T "groß" ist, interessiert. Der klassische sowie naheliegende Zugang ist, T auf eine große Gesamtgröße oder eine große Höhe zu bedingen. In dieser Arbeit werden drei, zum GW-Baum eng verwandte Typen von zufälligen Stammbäumen vorgestellt, deren Analyse aufschlussreiche Einsichten über große GW-Stammbäume liefert. Zur Untersuchung dieser auf große Gesamtgröße bedingten Stammbäume schlagen wir eine Familie von zufälligen, größenverzerrten Bäumen vor, deren auf Größe bedingte Verteilung mit der des, auf gegebener Größe bedingten, Baumes T übereinstimmt. Diese zufälligen Stammbäume besitzen eine einfache probabilistische Struktur, wenn man sie entlang der Ahnenlinien von rein zufällig gezogenen Knoten zerlegt. Die Verwandschaftsstruktur des von den gezogenen Knoten und der Wurzel aufgespannten Teilbaumes hängt im wesentlichen von dem asymptotischen Verhalten der Kinderzahlverteilung ab. Während bei endlicher Varianz diese Teilbäume asymptotisch binär sind, können bei unendlicher Varianz im Limes auch andere Formen auftreten. Wir zeigen, dass diese Teilbäume GW-Bäume bedingt auf ihre Gesamtblätterzahl sind. Mit Hilfe der Zerlegung entlang der Ahnenlinien erhalten wir zudem einen Grenzwertsatz für die reskalierte Gesamtgröße des Baumes mit einer Gamma-Verteilung als Limes. Die Analyse großer Bäume führen wir unter dem Aspekt des Größenverzerrens fort, indem wir eine weitere Familie zufälliger Bäume vorschlagen. Diese erhalten wir durch Größenverzerrung in der n-ten Generationsgröße. Wir werden sehen, dass der dadurch gewonnene zufällige Stammbaum eine ähnliche probabilistische Struktur wie der in der Gesamtgröße größenverzerrte Baum besitzt. Hier beweisen wir mit einfachen Überlegungen Aussagen über die Generation des jüngsten gemeinsamen Vorfahren (MRCA) von uniform aus Generation n gezogenen Knoten, sowie die Struktur des von diesen Knoten aufgespannten Skeletts. Schließlich betrachten wir die in [15] vorgestellte probabilistische Zerlegung des auf Mindesthöhe n bedingten GW-Baumes. Damit werden wir klassische Sätze über die Höhe des MRCA und die Grenzverteilung der reskalierten n-ten Generationsgröße für den Fall einer Kinderzahlverteilung mit unendlicher Varianz auf alternativem und anschaulichem Weg beweisen. Zudem erhalten wir eine Grenzverteilung für die Anzahl der Kinder des MRCA.