No description available.

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

No description available.

No description available.

Noble metal nanoparticles are of great interest due to their tunable optical and radiative properties. The specific wavelength of light at which the localized surface plasmon resonance occurs is dependent upon the shape, size and composition of the particle as well as the dielectric constant of the host medium. Thus, the optical properties of noble metal nanoparticles can be systematically tuned by altering these specific parameters. The purpose of this thesis is to investigate some of these properties related to metallic nanoparticles. The first several chapters focus on theoretical modeling to predict and explain various plasmonic properties of gold and silver nanoparticles while the later chapters focus on more accurately combining experimental and theoretical methods to explain the plasmonic properties of hollow gold nanoparticles of various shapes. The appendix contains a detailed description of the theoretical methods used throughout the thesis. It is intended to serve as a guide such that a user could carry out the various types of calculations discussed in this thesis simply by reading this appendix.

A recent line of works established a remarkable connection for antiferromagnetic 2-spin systems, including the Ising and hard-core models, showing that the computational complexity of approximating the partition function for graphs with maximum degree \Delta undergoes a computational transition that coincides with the statistical physics uniqueness/non-uniqueness phase transition on the infinite \Delta-regular tree. Despite this clear picture for 2-spin systems, there is little known for multi-spin systems. We present the first analog of the above inapproximability results for multi-spin systems. The main difficulty in previous inapproximability results was analyzing the behavior of the model on random \Delta-regular bipartite graphs, which served as the gadget in the reduction. To this end one needs to understand the moments of the partition function. Our key contribution is connecting: (i) induced matrix norms, (ii) maxima of the expectation of the partition function, and (iii) attractive fixed points of the associated tree recursions (belief propagation). We thus obtain a generic analysis of the Gibbs distribution of any multi-spin system on random regular bipartite graphs. We also treat in depth the k-colorings and the q-state antiferromagnetic Potts models. Based on these findings, we prove that for \Delta constant and even k<\Delta, it is NP-hard to approximate within an exponential factor the number of k-colorings on triangle-free \Delta-regular graphs. We also prove an analogous statement for the antiferromagnetic Potts model. Our hardness results for these models complement the conjectured regime where the models are believed to have efficient approximation schemes. We systematize the approach to obtain a general theorem for the computational hardness of counting in antiferromagnetic spin systems, which we ultimately use to obtain the inapproximability results for the k-colorings and q-state antiferromagnetic Potts models, as well as (the previously known results for) antiferromagnetic 2-spin systems. The criterion captures in an appropriate way the statistical physics uniqueness phase transition on the tree.

The first main focus in the present project was to analyse the boundary treatment of the linearised Korteweg-de Vries equation. The second main focus was to derive a stable numerical solution using a high-order finite difference method. Since the model involved a third derivative in space, the numerical treatment of the boundaries was highly nontrivial. To aid the boundary treatment high-order accurate first and third derivative finite difference operators were employed. The boundaries are based on the summation-by-parts (SBP) framework, thereby guaranteeing linear stability. The boundary conditions were imposed using a penalty technique. A convergence study was performed where the derived numerical solution was compared with an analytical one. Fourth order accurate Runge-Kutta was used to time-integrate the numerical approximation. Measuring the rate of convergence, q, yielded q = 4 for 4th order accurate SBP-operators and q = 5.5 for 6th order accurate SBP-operators. Thus the convergence study proved the accuracy and stability of the numerical solution derived with the SBP-methodology.

The focus of this thesis is on the design and analysis of algorithms for basic problems in Stochastic Optimization, specifically a class of fundamental combinatorial optimization problems where there is some form of uncertainty in the input. Since many interesting optimization problems are computationally intractable (NP-Hard), we resort to designing approximation algorithms which provably output good solutions. However, a common assumption in traditional algorithms is that the exact input is known in advance. What if this is not the case? What if there is uncertainty in the input? With the growing size of input data and their typically distributed nature (e.g., cloud computing), it has become imperative for algorithms to handle varying forms of input uncertainty. Current techniques, however, are not robust enough to deal with many of these problems, thus necessitating the need for new algorithmic tools. Answering such questions, and more generally identifying the tools for solving such problems, is the focus of this thesis. The exact problems we study in this thesis are the following: (a) the Survivable Network Design problem where the collection of (source,sink) pairs is drawn randomly from a known distribution, (b) the Stochastic Knapsack problem with random sizes/rewards for jobs, (c) the Multi-Armed Bandits problem, where the individual Markov Chains make random transitions, and finally (d) the Stochastic Orienteering problem, where the random tasks/jobs are located at different vertices on a metric. We explore different techniques for solving these problems and present algorithms for all the above problems with near-optimal approximation guarantees. We also believe that the techniques are fairly general and have wider applicability than the context in which they are used in this thesis.

In the Directed Steiner Tree problem, we are given a directed graph G = (V,E) with edge costs, a root vertex r ∈ V, and a terminal set X ⊆ V . The goal is to find the cheapest subset of edges that contains an r-t path for every terminal t ∈ X. The only known polylogarithmic approximations for Directed Steiner Tree run in quasi-polynomial time and the best polynomial time approximations only achieve a guarantee of O(|X|^ε) for any constant ε > 0. Furthermore, the integrality gap of a natural LP relaxation can be as bad as Ω(√|X|).  We demonstrate that l rounds of the Sherali-Adams hierarchy suffice to reduce the integrality gap of a natural LP relaxation for Directed Steiner Tree in l-layered graphs from Ω( k) to O(l · log k) where k is the number of terminals. This is an improvement over Rothvoss’ result that 2l rounds of the considerably stronger Lasserre SDP hierarchy reduce the integrality gap of a similar formulation to O(l · log k). We also observe that Directed Steiner Tree instances with 3 layers of edges have only an O(logk) integrality gap bound in the standard LP relaxation, complementing the fact that the gap can be as large as Ω(√k) in graphs with 4 layers. Finally, we consider quasi-bipartite instances of Directed Steiner Tree meaning no edge in E connects two Steiner nodes V − (X ∪ {r}). By a simple reduction from Set Cover, it is still NP-hard to approximate quasi-bipartite instances within a ratio better than O(log|X|). We present a polynomial-time O(log |X|)-approximation for quasi-bipartite instances of Directed Steiner Tree. Our approach also bounds the integrality gap of the natural LP relaxation by the same quantity. A novel feature of our algorithm is that it is based on the primal-dual framework, which typically does not result in good approximations for network design problems in directed graphs.

Photonic cavities are able to confine light to a volume of the order of wavelength of light and this ability can be described in terms of the cavity’s quality factor, which in turn, is proportional to the confinement time in units of optical period. This property of the photonic cavities have been found to be very useful in cavity quantum electrodynamics, for e.g., controlling emission from strongly coupled single photon sources like quantum dots. The smallest possible mode volume attainable by a dielectric cavity, however, poses a limit to the degree of coupling and therefore to the Purcell effect. As metal nanoparticles with plasmonic properties can have mode volumes far below the diffraction limit of light, these can be used to achieve stronger coupling, but the lossy nature of the metals can result in extremely poor quality factors. Hence a hybrid approach, where a high-quality dielectric cavity is combined with a low-quality metal nanoparticle, is being actively pursued. Such structures have been shown to have the potential to preserve the best of both worlds. This thesis describes the design, fabrication and characterization of hybrid plasmonic – photonic nanobeam cavities. Experimentally, we were able to achieve a quality factor of 1200 with the hybrid approach, which suggests that the results are promising for future single photon emission studies. It was found that modeling the behaviour (resonant frequencies, quality factors) of these hybrid cavities with conventional computation methods like FDTD can be tedious, for e.g., a comprehensive study of the electromagnetic fields inside a hybrid photonic nanobeam cavity has been found to take up to 48 hours with FDTD. Hence, we also present an alternate method of analysis using perturbation theory, showing good agreement with FDTD. / Graduate