No description available.

In this thesis, we study the existence of random periodic solutions of random dynamical systems (RDS) by geometric and topological approach. We employed an extension of ergodic theory to random setting to prove that a random invariant set with some kind of dissipative structure, can be expressed as union of random periodic curves. We extensively characterize the dissipative structure by random invariant measures and Lyapunov exponents. For stochastic flows induced by stochastic differential equations (SDEs), we studied the dissipative structure by two point motion of the SDE and prove the existence exponential stable random periodic solutions.

<p>This thesis studies non-nearest-neighbor random walks in random environments (RWRE) on the integers and on the d-dimensional integer lattic that are drawn in an i.i.d. way according to a Dirichlet distribution. We complete a characterization of recurrence and transience in a given direction for random walks in Dirichlet environments (RWDE) by proving directional recurrence in the case where the Dirichlet parameters are balanced and the annealed drift is zero. As a step toward this, we prove a 0-1 law for directional transience of i.i.d. RWRE on the 2-dimensional integer lattice with bounded jumps. Such a 0-1 law was proven by Zerner and Merkl for nearest-neighbor RWRE in 2001, and Zerner gave a simpler proof in 2007. We modify the latter argument to allow for bounded jumps. We then characterize ballisticity, or nonzero liiting velocity, of transienct RWDE on the integers. It turns out that ballisticity is controlled by two parameters, kappa0 and kappa1. The parameter kappa0, which controls finite traps, is known to characterize ballisticity for nearest-neighbor RWDE on the d-dimensional integer lattice for dimension d at least 3, where transient walks are ballistic if and only if kappa0 is greater than 1. The parameter kappa1, which controls large-scale backtracking, is known to characterize ballisticity for nearest-neighbor RWDE on the one-dimensional integer lattice, where transient walks are ballistic if and only if the absolute value of kappa1 is greater than 1. We show that in our model, transient walks are ballistic if and only if both parameters are greater than 1. Our characterization is thus a mixture of known characterizations of ballisticity for nearest-neighbor one-dimensional and higher-dimensional cases. We also prove more detailed theorems that help us better understand the phenomena affecting ballisticity.</p>

In this dissertation, we study the complicated dynamics of two classes of systems: Anosov systems driven by an external force and partially hyperbolic systems driven by an external force. For smooth Anosov systems driven by an external force, we first study the random specification property, which is on the approximation of an N−spaced arbitrary long finite random orbit segments within given precision by a random periodic point. We prove that if such system is topological mixing on fibers, then it has the random specification property. Furthermore, we prove that the homeomorphism induced by such a system on the space of random probability measures also has the specification property. We note that the random specification property implies the positivity of topological fiber entropy. Secondly, we show that if the system is topological mixing on fibers, then its past and future random correlation for Hölder observable functions decay exponentially with respect to the system and the unique random SRB measure. For smooth partially hyperbolic systems driven by an external force, we prove the existence of the random Gibbs u−state, which has absolutely continuous conditional measure on the strong unstable manifolds.

Recently, there has been a renewed interest in code based cryptosystems. Amongst the reasons for this interest is that they have shown to be resistant to quantum at- tacks, making them candidates for post-quantum cryptosystems. In fact, the National Institute of Standards and Technology is currently considering candidates for secure communication in the post-quantum era. Three of the proposals are code based cryp- tosystems. Other reasons for this renewed interest include e cient encryption and decryption. In this dissertation, new code based cryptosystems (symmetric key and public key) are presented that use high rate codes and have small key sizes. Hence they overcome the drawbacks of code based cryptosystems (low information rate and very large key size). The techniques used in designing these cryptosystems include random bit/block deletions, random bit insertions, random interleaving, and random bit ipping. An advantage of the proposed cryptosystems over other code based cryp- tosystems is that the code can be/is not secret. These cryptosystems are among the rst with this advantage. Having a public code eliminates the need for permutation and scrambling matrices. The absence of permutation and scrambling matrices results in a signi cant reduction in the key size. In fact, it is shown that with simple random bit ipping and interleaving the key size is comparable to well known symmetric key cryptosystems in use today such as Advanced Encryption Standard (AES). The security of the new cryptosystems are analysed. It is shown that they are immune against previously proposed attacks for code based cryptosystems. This is because scrambling or permutation matrices are not used and the random bit ipping is beyond the error correcting capability of the code. It is also shown that having a public code still provides a good level of security. This is proved in two ways, by nding the probability of an adversary being able to break the cryptosystem and showing that this probability is extremely small, and showing that the cryptosystem has indistinguishability against a chosen plaintext attack (i.e. is IND-CPA secure). IND-CPA security is among the primary necessities for a cryptosystem to be practical. This means that a ciphertext reveals no information about the corresponding plaintext other than its length. It is also shown that having a public code results in smaller key sizes. / Graduate

Despite much work over the previous decade, the Satisfiability Threshold Conjecture remains open. Random k-SAT, for constant k >= 3, is just one family of a large number of constraint satisfaction problems that are conjectured to have exact satisfiability thresholds, but for which the existence and location of these thresholds has yet to be proven. Of those problems for which we are able to prove an exact satisfiability threshold, each seems to be fundamentally different than random 3-SAT. This thesis defines a new family of constraint satisfaction problems with constant size constraints and domains and which contains problems that are NP-complete and a.s.\ have exponential resolution complexity. All four of these properties hold for k-SAT, k >= 3, and the exact satisfiability threshold is not known for any constraint satisfaction problem that has all of these properties. For each problem in the family defined in this thesis, we determine a value c such that c is an exact satisfiability threshold if a certain multi-variable function has a unique maximum at a given point in a bounded domain. We also give numerical evidence that this latter condition holds. In addition to studying the satisfiability threshold, this thesis finds exact thresholds for the efficient behavior of DPLL using the unit clause heuristic and a variation of the generalized unit clause heuristic, and this thesis proves an analog of a conjecture on the satisfiability of (2+p)-SAT. Besides having similar properties as k-SAT, this new family of constraint satisfaction problems is interesting to study in its own right because it generalizes the XOR-SAT problem and it has close ties to quasigroups.

Despite much work over the previous decade, the Satisfiability Threshold Conjecture remains open. Random k-SAT, for constant k >= 3, is just one family of a large number of constraint satisfaction problems that are conjectured to have exact satisfiability thresholds, but for which the existence and location of these thresholds has yet to be proven. Of those problems for which we are able to prove an exact satisfiability threshold, each seems to be fundamentally different than random 3-SAT. This thesis defines a new family of constraint satisfaction problems with constant size constraints and domains and which contains problems that are NP-complete and a.s.\ have exponential resolution complexity. All four of these properties hold for k-SAT, k >= 3, and the exact satisfiability threshold is not known for any constraint satisfaction problem that has all of these properties. For each problem in the family defined in this thesis, we determine a value c such that c is an exact satisfiability threshold if a certain multi-variable function has a unique maximum at a given point in a bounded domain. We also give numerical evidence that this latter condition holds. In addition to studying the satisfiability threshold, this thesis finds exact thresholds for the efficient behavior of DPLL using the unit clause heuristic and a variation of the generalized unit clause heuristic, and this thesis proves an analog of a conjecture on the satisfiability of (2+p)-SAT. Besides having similar properties as k-SAT, this new family of constraint satisfaction problems is interesting to study in its own right because it generalizes the XOR-SAT problem and it has close ties to quasigroups.

The paper is dedicated to the modeling and the simulation of random processes and fields. Using the concept and the theory of weakly correlated functions a consistent representation of sufficiently smooth random processes will be derived. Special applications will be given with respect to the simulation of road surfaces in vehicle dynamics and to the confirmation of theoretical results with respect to the zeros of random polynomials.

No description available.

Je présente dans ce mémoire mes travaux sur les limites d'échelle de grandes structures aléatoires. Il s'agit de décrire les structures combinatoires dans la limite des grandes tailles en prenant un point de vue objectif dans le sens où on cherche des limites des objets, et non pas seulement de paramètres caractéristiques (même si ce n'est pas toujours le cas dans les résultats que je présente). Le cadre général est celui des structures critiques pour lesquelles on a typiquement des distances caractéristiques polynomiales en la taille, et non concentrées. Sauf exception, ces structures ne sont en général pas adaptées aux applications informatiques. Elles sont cependant essentielles de part l'universalité de leurs propriétés asymptotiques, prouvées ou attendues. Je parle en particulier d'arbres uniformément choisis, de graphes aléatoires, d'arbres couvrant minimaux et de partitions récursives de domaines du plan:<br/> <strong>Arbres aléatoires uniformes.</strong> Il s'agit ici de mieux comprendre un objet limite essentiel, l'arbre continu brownien (CRT). Je présente quelques résultats de convergence pour des modèles combinatoires ''non-branchants'' tels que des arbres sujets aux symétries et les arbres à distribution de degrés fixée. Je décris enfin une nouvelle décomposition du CRT basée sur une destruction partielle.<br/> <strong>Graphes aléatoires.</strong> J'y décris la construction algorithmique de la limite d'échel-le des graphes aléatoires du modèle d'Erdös--Rényi dans la zone critique, et je fais le lien avec le CRT et donne des constructions de l'espace métrique limite. <strong>Arbres couvrant minimaux.</strong> J'y montre qu'une connection avec les graphes aléatoires permet de quantifier les distances dans un arbre convrant aléatoire. On obtient non seulement l'ordre de grandeur de l'espérance du diamètre, mais aussi la limite d'échelle en tant qu'espace métrique mesuré. Partitions récursives. Sur deux exemples, les arbres cadrant et les laminations du disque, je montre que des idées basées sur des théorèmes de point fixe conduisent à des convergences de processus, où les limites sont inhabituelles, et caractérisées par des décompositions récursives.