In this dissertation, new theoretical results are obtained for bounding convergence and mean-square error in conditional coding. Further new statistical methods for the practical application of conditional coding are developed. Criteria for the uniform convergence are first examined. Conditional coding Markov chains are aperiodic, π-irreducible, and Harris recurrent. By applying the general theories of uniform ergodicity of Markov chains on genera l state space, one can conclude that conditional coding Markov cha ins are uniformly ergodic and further, theoretical convergence rates based on Doeblin's condition can be found. Conditional coding Markov chains can be also viewed as having finite state space. This allows use of techniques to get bounds on the second largest eigenvalue which lead to bounds on convergence rate and the mean-square error of sample averages. The results are applied in two examples showing that these bounds are useful in practice. Next some algorithms for perfect sampling in conditional coding are studied. An application of exact sampling to the independence sampler is shown to be equivalent to standard rejection sampling. In case of single-site updating, traditional perfect sampling is not directly applicable when the state space has large cardinality and is not stochastically ordered, so a new procedure is developed that gives perfect samples at a predetermined confidence interval. In last chapter procedures and possibilities of applying conditional coding to mixture models are explored. Conditional coding can be used for analysis of a finite mixture model. This methodology is general and easy to use.

In this thesis, we consider the planning problem for first-order mean-field games (MFG). These games degenerate into optimal transport when there is no coupling between players. Our aim is to extend the concept of displacement convexity from optimal transport to MFGs. This extension gives new estimates for solutions of MFGs. First, we introduce the Monge-Kantorovich problem and examine related results on rearrangement maps. Next, we present the concept of displacement convexity. Then, we derive first-order MFGs, which are given by a system of a Hamilton-Jacobi equation coupled with a transport equation. Finally, we identify a large class of functions, that depend on solutions of MFGs, which are convex in time. Among these, we find several norms. This convexity gives bounds for the density of solutions of the planning problem.

Memory-safe execution of C programs has been well researched but the ability to find memory-safety violations before execution has often been overlooked. One approach for memory-safe C is SoftBoundCETS which infer some memory-accesses as statically safe and others become runtime-checked. One problem with this approach is that it is not obvious to the programmer which checks are runtime-checked and which are inferred as safe. This report analyses the approach taken by SoftBoundCETS by implementing a runtime bounds-checks lister for SoftBoundCETS.The resulting runtime bounds-checks-listing program that can track 99% of the inlined runtime bounds-checks to user program source code lines in programs compiled with -O3 and link-time-optimisation. Analysing SoftBoundCETS with this tool reveals SoftBoundCETS can eliminate about 35% of the memory loads and stores as statically safe in Coreutils 8.27. / Mycket forskning har utförts om minnessäker exekvering av C-program men förmågan att hitta minnessäkerhetsöverträdelser har ofta förbisetts. En approach för minnessäker C är Softbound-Cets som härleder vissa minnesaccesser som statiskt säkra och andra blir kontrollerade vid körtid. Ett problem med denna approach är att det inte är uppenbart för programmeraren vilka kontroller som utförs vid körtid och vilka som härleds som säkra. Denna rapport analyserar Softbound-Cets approach genom att implementera ett program som listar fältaccesser för Softbound-Cets. Det färdiga programmet som listar fältaccesser vid körtid kan spåra 99% av inline-expanderade accesskontroller vid körtid till kodrader i användarprogram kompilerade med -O3 och länktidsoptimering. Analysen av Softbound-Cets med detta verktyg avslöjar att Softbound-Cets kan eliminera runt 35% av minnesaccesserna som statiskt säkra bland programmeni Coreutils 8.27.

Consider infecting a subset $A_0 \subseteq V(G)$ of the vertices of a graph $G$. Let an uninfected vertex $v \in V(G)$ become infected if $|N_G(v) \cap A_0| \geq r$, for some integer $r$. Define $A_t = A_{t-1} \cup \{v \in V(G) : |N_G(v) \cap A_{t-1}| \geq r \},$ and say that the set $A_0$ is \emph{lethal} under $r$-neighbor percolation if there exists a $t$ such that $A_t = V(G)$. For a graph $G$, let $m(G,r)$ be the size of the smallest lethal set in $G$ under $r$-neighbor percolation. The problem of determining $m(G,r)$ has been extensively studied for grids $G$ of various dimensions. We define $$m(a_1, \dots, a_d, r) = m\left (\prod_{i=1}^d [a_i], r\right )$$ for ease of notation. Famously, a lower bound of $m(a_1, \dots, a_d, d) \geq \frac{\sum_{j=1}^d \prod_{i \neq j} a_i}{d}$ is given by a beautiful argument regarding the high-dimensional ``surface area" of $G = [a_1] \times \dots \times [a_d]$. While exact values of $m(G,r)$ are known in some specific cases, general results are difficult to come by. In this thesis, we introduce a novel technique for viewing $3$-neighbor lethal sets on three-dimensional grids in terms of lethal sets in two dimensions. We also provide a strategy for recursively building up large lethal sets from existing small constructions. Using these techniques, we determine the exact size of all lethal sets under 3-neighbor percolation in three-dimensional grids $[a_1] \times [a_2] \times [a_3]$, for $a_1,a_2,a_3 \geq 11$. The problem of determining $m(n,n,3)$ is discussed by Benevides, Bermond, Lesfari and Nisse in \cite{benevides:2021}. The authors determine the exact value of $m(n,n,3)$ for even $n$, and show that, for odd $n$, $$\ceil*{\frac{n^2+2n}{3}} \leq m(n,n,3) \leq \ceil*{\frac{n^2+2n}{3}} + 1.$$ We prove that $m(n,n,3) = \ceil*{\frac{n^2+2n}{3}}$ if and only if $n = 2^k-1$, for some $k >0$. Finally, we provide a construction to prove that for $a_1,a_2,a_3 \geq 12$, bounds on the minimum lethal set on the the torus $G = C_{a_1} \square C_{a_2} \square C_{a_3}$ are given by $$2 \le m(G,3) - \frac{a_1a_2 + a_2a_3 + a_3a_1 -2(a_1+a_2+a_3)}{3} \le 3.$$ / Graduate

No description available.

No description available.

In this thesis, we generate a lower bound on the security of quantum protocols for secure function evaluation. Central to our proof is the concept of gentle measurements of quantum states, which do not greatly disturb a quantum state if a certain outcome is obtained with high probability. We show how a cheating party can leverage gentle measurements to learn more information than should be allowable. To quantify our lower bound, we reduce a specific cryptographic task known as die-rolling to secure function evaluation and use the concept of gentle measurements to relate their security notions. Our lower bound is then obtained using a known security bound for die-rolling known as Kitaev's bound. Due to the generality of secure function evaluation, we are able to apply this lower bound to obtain lower bounds on the security of quantum protocols for many quantum tasks. In particular, we provide lower bounds for oblivious transfer, XOR oblivious transfer, the equality function, the inner product function, Yao's millionaires' problem, and the secret phrase problem. Note that many of these lower bounds are the first of their kind, which is a testament to the utility of our lower bound. As a consequence, these bounds prove that unconditional security for quantum protocols is impossible for these applications, and since these are constant lower bounds, this rules out any form of boosting toward perfect security. Our work lends itself to future research on designing optimal protocols for the above listed tasks, and potentially others, by providing constant lower bounds to approximate or improve. / Master of Science / Quantifying the cryptographic security of quantum applications is the focus of much research in the quantum cryptography discipline. Quantum protocols might have better security than their classical counterparts, and this advantage might make the adoption of quantum cryptographic protocols a viable option. In this thesis, we introduce a method for generating constant lower bounds on the security of a variety of quantum applications. This is accomplished through finding a lower bound on the security of a protocol that is general, and by virtue of its generality, can be scoped to quantum applications such that the lower bound can be applied, and constant lower bounds generated for these applications. The significance of the work in this thesis is that many of the constant lower bounds presented are the first of their kind for these quantum applications, thus proving the impossibility of them having unconditional security. This also proves that one cannot asymptotically boost towards perfect security in these quantum tasks by any means. These constant lower bounds also provide a foundation for future work in the study of these quantum applications, specifically in the search for upper and lower bounds on their cryptographic security, as well as in the search for protocols that approximate these bounds.

The purpose of this dissertation is to develop and demonstrate methods appropriate for the quantification and propagation of uncertainty in large, high-consequence engineering projects. The term "rigorous uncertainty quantification" refers to methods equal to the proposed task. The motivating practical example is uncertainty in a Mars atmosphere model due to the incompletely characterized presence of dust. The contributions made in this dissertation, though primarily mathematical and philosophical, are driven by the immediate needs of engineers applying uncertainty quantification in the field. Arguments are provided to explain how the practical needs of engineering projects like Mars lander missions motivate the use of the objective probability bounds approach, as opposed to the subjectivist theories which dominate uncertainty quantification in many research communities. An expanded formalism for Dempster-Shafer structures is introduced, allowing for the representation of continuous random variables and fuzzy variables as Dempster-Shafer structures. Then, the correctness and incorrectness of probability bounds analysis and the Cartesian product propagation method for Dempster-Shafer structures under certain dependency conditions are proven. It is also conclusively demonstrated that there exist some probability bounds problems in which the best-possible bounds on probability can not be represented using Dempster-Shafer structures. Nevertheless, Dempster-Shafer theory is shown to provide a useful mathematical framework for a wide range of probability bounds problems. The dissertation concludes with the application of these new methods to the problem of propagating uncertainty from the dust parameters in a Mars atmosphere model to uncertainty in that model's prediction of atmospheric density. A thirty-day simulation of the weather at Holden Crater on Mars is conducted using a meso-scale atmosphere model, MRAMS. Although this analysis only addresses one component of Mars atmosphere uncertainty, it demonstrates the applicability of probability bounds methods in practical engineering work. More importantly, the Mars atmosphere uncertainty analysis provides a framework in which to conclusively establish the practical importance of epistemology in rigorous uncertainty quantification. / Ph. D.

A sorted array is a fundamental algorithmic concept. Its on-line variant gives rise to the online labeling problem. In the online labeling problem we are given an array of size m and a stream of n integers from the universe {1, ..., r} coming in an arbitrary order. Our task is to maintain all received items in the array in sorted order. The inserted items do not have to be stored consecutively in the array. Since the final order of the items is not known until we see all the items, moves of already inserted items are allowed but should be minimized. We present two algorithms which together provide an optimal solution for almost all values of m as a function of n. We provide tight lower bounds for almost all ranges of m. We introduce a notion of the limited universe and prove lower bounds also in that setting. Some of our lower bounds also apply to randomized algorithms. Powered by TCPDF (www.tcpdf.org)

Thesis (MComm)--University of Stellenbosch, 2003. / Please refer to full text for abstract.