A stochastic shortest path (SSP) problem is an undiscounted Markov decision process with an absorbing and zero-cost target state, where the objective is to reach the target state with minimum expected cost. This problem provides a foundation for algorithms for decision-theoretic planning and probabilistic model checking, among other applications. This thesis describes an implementation and evaluation of recently developed error bounds for SSP problems. The bounds can be used in a test for convergence of iterative dynamic programming algorithms for solving SSP problems, as well as in action elimination procedures that can accelerate convergence by excluding provably suboptimal actions that do not need to be re-evaluated each iteration. The techniques are shown to be effective for both decision-theoretic planning and probabilistic model checking.

<p>Let S be a polynomial ring K[x1,...,xn] over a field K and let F be a non-negatively graded free module over S generated by m basis elements. In this thesis, we study four kinds of upper bounds: degree bounds for Gröbner bases of submodules of F, bounds for arithmetic degrees of S-ideals, regularity bounds for radicals of S-ideals, and Stillman bounds. </p> <p><br></p> <p>Let M be a submodule of F generated by elements with degrees bounded above by D and dim(F/M)=r. We prove that if M is graded, the degree of the reduced Gröbner basis of M for any term order is bounded above by 2[1/2((Dm)^{n-r}m+D)]^{2^{r-1}}. If M is not graded, the bound is 2[1/2((Dm)^{(n-r)^2}m+D)]^{2^{r}}. This is a generalization of bounds for ideals in a polynomial ring due to Dubé (1990) and Mayr-Ritscher (2013).</p> <p><br></p> <p>Our next results are concerned with a homogeneous ideal I in S generated by forms of degree at most d with dim(S/I)=r. In Chapter 4, we show how to derive from a result of Hoa (2008) an upper bound for the regularity of sqrt{I}, which denotes the radical of I. More specifically we show that reg(sqrt{I})<= d^{(n-1)2^{r-1}}. In Chapter 5, we show that the i-th arithmetic degree of I is bounded above by 2*d^{2^{n-i-1}}. This is done by proving upper bounds for arithmetic degrees of strongly stable ideals and ideals of Borel type.</p> <p><br></p> <p>In the last chapter, we explain our progress in attempting to make Stillman bounds explicit. Ananyan and Hochster (2020) were the first to show the existence of Stillman bounds. Together with G. Caviglia, we observe that a possible way of making their results explicit is to find an effective bound for an invariant called D(k,d) and supplement it into their proof. Although we are able to obtain this bound D(k,d) and realize Stillman bounds via an algorithm, it turns out that the computational complexity of Ananyan and Hochster's inductive proof would make the bounds too large to be meaningful. We explain the bad behavior of these Stillman bounds by giving estimates up to degree 3.</p>

No description available.

In engineering, materials are often assumed to be homogeneous and isotropic; in actuality, material properties do change with sample direction and location. This variation is due to the anisotropy of the individual grains and their spatial distribution in the material. Currently there is a lack of communication between the design engineer, material scientist, and processor for solving multi-objective/constrained designs. If communication existed between these groups then materials could be designed for applications, instead of the reverse. Microstructure sensitive design introduces a common language, a spectral representation, where both design properties and microstructures are expressed. Using Hill bounds, effective elastic properties are expressed within the spectral representation. For the elastic properties, two FCC materials, copper and nickel, were chosen for computation and to demonstrate how symmetry enters into the methodology. This spectral representation renders properties as hyper-surfaces that translate through a multi-dimensional Fourier space depending on the property value of the hyper-surface. Property closures are generated by condensing the information contained within the multi-dimensional Fourier space into a 2-D representation. This compaction of information is beneficial for a quick determination of property limits for a particular alloy system. The design engineer can now dictate the critical design properties and receive sets of microstructures that satisfy the design objectives.

Ray tracing is a well-know technique for producing realistic graphics. However, the time necessary to generate images is unacceptably long. When producing the many frames that are necessary for animations, the time is magnified. Many methods have been proposed to reduce the calculations necessary in ray tracing. Much of the effort has attempted to reduce the number of rays cast or to reduce the number of intersection calculations. Both of these techniques exploit spatial coherence. These acceleration techniques are expanded not only to exploit spatial coherence but also to exploit temporal coherence in order to reduce calculations by treating animation information as a whole as opposed to isolating calculations to each individual frame. Techniques for exploiting temporal coherence are explored along with associated temporal bounding methods. By first ray tracing a temporally expanded scene, we are able to avoid traversal calculations in associated frames where object intersection is limited. This reduces the rendering times of the associated frames.

Thermalization is ubiquitous to all physical systems and is an essential assumption for the postulates of statistical mechanics. Generally, every system evolves under its own dynamics and reaches thermal equilibrium. In the quantum realm, thermal equilibrium is described by the Eigenstate Thermalization Hypothesis (ETH); hence every system that thermalizes is expected to follow ETH. Moreover, the thermalization process is always manifested as transport of matter and quantum information across the system. Thermalizing quantum systems with local interactions are expected to show diffusive transport of global conserved quantities and ballistic information spreading. The vast majority of many-body systems show the typical behavior described above. In this thesis, we study two mechanisms that break the standard picture of quantum thermalization. On the one hand, information spreading may be faster in the presence of long-range interactions. By simulating the Lieb-Robinson bounds in a spin chain with power-law decaying interactions, we distinguish the regime where the long-range character of the interactions becomes irrelevant for information spreading. On the other hand, the interplay of disorder and interactions can slow down transport, entering a sub-diffusive regime. We study this dynamical regime in an Anderson model on random regular graphs, where the emergence of a sub-diffusive regime before the localization transition is highly debated. Looking at long-range spectral correlations, we found that the sub-diffusive regime may be extended over the whole thermal phase of the model. Moreover, when disorder is strong enough, quantum many-body systems can undergo an ergodicity breaking transition to a many-body localized (MBL) phase. These systems do not follow ETH, so they present a challenge for conventional statistical mechanics. In particular, we study how the structure of local operator eigenstate matrix elements (central assumption of ETH) change between the thermal and MBL phase. A complete characterization of matrix elements of correlation functions is achieved via strong disorder quasi-degenerate perturbation theory. Furthermore, we study the MBL transition mechanism, which is still an open question due to the limitations of the available techniques for addressing that regime. Focusing on the avalanche mechanism, we simulate MBL spin chains coupled to a finite and infinite thermal bath. We could estimate the thermalization rate, which behaves as an order parameter and provide bounds for the actual critical disorder in the thermodynamic limit. We propose the existence of an intermediate MBL ``regime' where the system is slowly de-localizing, but relevant time scales are out-of-reach for current experiments and numerical simulations.

Heteroscedastic metamodeling has gained popularity as an effective tool for analyzing and optimizing complex stochastic systems. A heteroscedastic metamodel provides an accurate approximation of the input-output relationship implied by a stochastic simulation experiment whose output is subject to input-dependent noise variance. Several challenges remain unsolved in this field. First, in-depth investigations into the consistency of heteroscedastic metamodeling techniques, particularly from the sequential prediction perspective, are lacking. Second, sequential heteroscedastic metamodel-based level-set estimation (LSE) methods are scarce. Third, the increasingly high computational cost required by heteroscedastic Gaussian process-based LSE methods in the sequential sampling setting is a concern. Additionally, when constructing a valid uniform bound for a heteroscedastic metamodel, the impact of noise variance estimation is not adequately addressed. This dissertation aims to tackle these challenges and provide promising solutions. First, we investigate the information consistency of a widely used heteroscedastic metamodeling technique, stochastic kriging (SK). Second, we propose SK-based LSE methods leveraging novel uniform bounds for input-point classification. Moreover, we incorporate the Nystrom approximation and a principled budget allocation scheme to improve the computational efficiency of SK-based LSE methods. Lastly, we investigate empirical uniform bounds that take into account the impact of noise variance estimation, ensuring an adequate coverage capability. / Doctor of Philosophy / In real-world engineering problems, understanding and optimizing complex systems can be challenging and prohibitively expensive. Computer simulation is a valuable tool for analyzing and predicting system behaviors, allowing engineers to explore different scenarios without relying on costly physical prototypes. However, the increasing complexity of simulation models leads to a higher computational burden. Metamodeling techniques have emerged to address this issue by accurately approximating the system performance response surface based on limited simulation experiment data to enable real-time decision-making. Heteroscedastic metamodeling goes further by considering varying noise levels inherent in simulation outputs, resulting in more robust and accurate predictions. Among various techniques, stochastic kriging (SK) stands out by striking a good balance between computational efficiency and statistical accuracy. Despite extensive research on SK, challenges persist in its application and methodology. These include little understanding of SK's consistency properties, an absence of sequential SK-based algorithms for level-set estimation (LSE) under heteroscedasticity, and the increasingly low computational efficiency of SK-based LSE methods in implementation. Furthermore, a precise construction of uniform bounds for the SK predictor is also missing. This dissertation aims at addressing these aforementioned challenges. First, the information consistency of SK from a prediction perspective is investigated. Then, sequential SK-based procedures for LSE in stochastic simulation, incorporating novel uniform bounds for accurate input-point classification, are proposed. Furthermore, a popular approximation technique is incorporated to enhance the computational efficiency of the SK-based LSE methods. Lastly, empirical uniform bounds are investigated considering the impact of noise variance estimation.

No description available.

No description available.

Civility has many critics. Some challenge its distinctness as a virtue, others its moral significance. In this essay, I attempt to meet both challenges by offering an account of civility that stands distinct from other concepts and holds great value, both intrinsically and instrumentally. I claim that we show civility toward others when we dispute their ideas in ways that respect those persons' intrinsic worth. My account pays particular attention to the connections between civility, clarity and reconciliation--connections that make civility vital for modern pluralistic societies. I then consider a recent alternative to this conception of civility advanced by Calhoun (2000), arguing that it secures distinctness at the cost of moral significance. / Master of Arts