Published: 13 Oct 2015
c 2015 S. Gharibian, Y. Huang, Z. Landau, and S. W. Shin
Computational complexity, Design and analysis of algorithms, Quantum Computation
Constraint satisfaction problems are a central pillar of modern computational complexity theory. This survey provides an introduction to the rapidly growing field of Quantum Hamiltonian Complexity, which includes the study of quantum constraint satisfaction problems. Over the past decade and a half, this field has witnessed fundamental breakthroughs, ranging from the establishment of a “Quantum Cook-Levin Theorem” to deep insights into the structure of 1D low-temperature quantum systems via so-called area laws. Our aim here is to provide a computer science-oriented introduction to the subject in order to help bridge the language barrier between computer scientists and physicists in the field. As such, we include the following in this survey: (1) The motivations and history of the field, (2) a glossary of condensed matter physics terms explained in computer-science friendly language, (3) overviews of central ideas from condensed matter physics, such as indistinguishable particles, mean field theory, tensor networks, and area laws, and (4) brief expositions of selected computer science-based results in the area. For example, as part of the latter, we provide a novel information theoretic presentation of Bravyi’s polynomial time algorithm for Quantum 2-SAT.
1. Introduction
2. Preliminaries
3. Roadmap and Organization
4. A Brief History
5. Motivations From Physics
6. Physics Concepts in Greater Depth
7. Reviews of Selected Results
Acknowledgments
References
Published: 18 Dec 2015
c 2015 J. H. Manton and P.-O. Amblard
Adaptive control and signal processing, Kernel methods, Classification and prediction, Adaptive signal processing, Statistical signal processing, Filtering, Estimation, Identification
Reproducing kernel Hilbert spaces are elucidated without assuming prior familiarity with Hilbert spaces. Compared with extant pedagogic material, greater care is placed on motivating the definition of reproducing kernel Hilbert spaces and explaining when and why these spaces are efficacious. The novel viewpoint is that reproducing kernel Hilbert space theory studies extrinsic geometry, associating with each geometric configuration a canonical overdetermined coordinate system. This coordinate system varies continuously with changing geometric configurations, making it well-suited for studying problems whose solutions also vary continuously with changing geometry. This primer can also serve as an introduction to infinite-dimensional linear algebra because reproducing kernel Hilbert spaces have more properties in common with Euclidean spaces than do more general Hilbert spaces.
1. Introduction
2. Finite-dimensional RKHSs
3. Function Spaces
4. Infinite-dimensional RKHSs
5. Geometry by Design
6. Applications to Linear Equations and Optimisation
7. Applications to Stochastic Processes
8. Embeddings of Random Realisations
9. Applications of Embeddings
References
Published: 17 Dec 2015
c 2015 P. Bolzern and P. Colaneri
Systems Theory, Optimal Control, Control of Stochastic Systems
This paper presents a comprehensive study of continuous-time Positive Markov Jump Linear Systems (PMJLS). A PMJLS can be seen as a dynamical system that switches within a finite set of linear time-invariant subsystems according to a stochastic switching signal modelled as a Markov chain, and describes the time-evolution of nonnegative variables under nonnegative inputs. Contrary to the well-studied general class of Markov Jump Linear Systems (MJLS), positivity endows the model with peculiar properties. The paper collects some existing results together with original developments on the stability analysis of PMJLS and the study of their input-output properties. In particular, conditions for stability of PMJLS are discussed, mainly based on Linear Programming problems. Similar computational tools are derived to analyze performance measures, such as L1, L2 and L∞ costs and the respective input-output induced gains. The second part of the paper is devoted to the class of Dual switching Positive Markov Jump Linear Systems (D-PMJLS), namely PMJLS affected by an additional switching variable which can be either an unknown disturbance or a control signal available to the designer for stabilization and performance optimization. We discuss several problems, including stability, performance analysis, stabilization via switching control, and optimization. Some application examples are introduced to motivate the interest in PMJLS and D-PMJLS.
In this article:
1. Introduction and Motivations
2. Positive Markov Jump Linear Systems
3. Dual Switching
4. Concluding Remarks
References
Abstract
The book constitutes an elementary course on Plane Euclidean Geometry, pitched at pre-university or at advanced high school level. It is a concise book treating the subject axiomatically, but since it is meant to be a first introduction to the subject, excessive rigour is avoided, making it appealing to a younger audience as well. The aim is to cover the basics of the subject, while keeping the subject lively by means of challenging and interesting exercises. This makes it relevant also for students participating in mathematics circles and in mathematics olympiads.
Each section contains several problems, which are not purely drill exercises, but are intended to introduce a sense of "play" in mathematics, and inculcate appreciation of the elegance and beauty of geometric results. There is an abundance of colour pictures illustrating results and their proofs. A section on hints and a further section on detailed solutions to all the exercises appear at the end of the book, making the book ideal also for self-study.
Geometric Figures
Congruent Triangles
Quadrilaterals
Similar Triangles
Circles
Readership: Undergraduate students in mathematics.
288pp Feb 2016
ISBN: 978-981-4740-43-2 (hardcover)
ISBN: 978-981-4740-44-9 (softcover)
The book gives a detailed account of the development of the theory of algebraic equations, from its origins in ancient times to its completion by Galois in the nineteenth century. The appropriate parts of works by Cardano, Lagrange, Vandermonde, Gauss, Abel, and Galois are reviewed and placed in their historical perspective, with the aim of conveying to the reader a sense of the way in which the theory of algebraic equations has evolved and has led to such basic mathematical notions as "group" and "field".
A brief discussion of the fundamental theorems of modern Galois theory and complete proofs of the quoted results are provided, and the material is organized in such a way that the more technical details can be skipped by readers who are interested primarily in a broad survey of the theory.
In this second edition, the exposition has been improved throughout and the chapter on Galois has been entirely rewritten to better reflect Galois' highly innovative contributions. The text now follows more closely Galois' memoir, resorting as sparsely as possible to anachronistic modern notions such as field extensions. The emerging picture is a surprisingly elementary approach to the solvability of equations by radicals, and yet is unexpectedly close to some of the most recent methods of Galois theory.
Quadratic Equations
Cubic Equations
Quartic Equations
The Creation of Polynomials
A Modern Approach to Polynomials
Alternative Methods for Cubic and Quartic Equations
Roots of Unity
Symmetric Functions
The Fundamental Theorem of Algebra
Lagrange
Vandermonde
Gauss on Cyclotomic Equations
Ruffini and Abel on General Equations
Galois
Epilogue
Readership: Upper level undergraduates, graduate students and mathematicians in algebra.
324pp Feb 2016
ISBN: 978-981-4704-69-4 (hardcover)