Catalogue Search | MBRL
Are you sure you want to remove the book from the shelf?
{{itemTitle}}
11,358
result(s) for
"Computational complexity."
Sort by:
On the Complexity of Target Set Selection in Simple Geometric Networks
We study the following model of disease spread in a social network. At first, all individuals are either infected or healthy. Next, in discrete rounds, the disease spreads in the network from infected to healthy individuals such that a healthy individual gets infected if and only if a sufficient number of its direct neighbors are already infected. We represent the social network as a graph. Inspired by the real-world restrictions in the current epidemic, especially by social and physical distancing requirements, we restrict ourselves to networks that can be represented as geometric intersection graphs. We show that finding a minimal vertex set of initially infected individuals to spread the disease in the whole network is computationally hard, already on unit disk graphs. Hence, to provide some algorithmic results, we focus ourselves on simpler geometric graph classes, such as interval graphs and grid graphs.
Journal Article
Multilevel Monte Carlo Path Simulation
We show that multigrid ideas can be used to reduce the computational complexity of estimating an expected value arising from a stochastic differential equation using Monte Carlo path simulations. In the simplest case of a Lipschitz payoff and a Euler discretisation, the computational cost to achieve an accuracy of O ( ) is reduced from O ( –3 ) to O ( –2 (log ) 2 ). The analysis is supported by numerical results showing significant computational savings.
Journal Article
Representing Matroids over the Reals is$\\exists \\mathbb R$ -complete
A matroid$M$is an ordered pair$(E,I)$ , where$E$is a finite set called the ground set and a collection$I\\subset 2^{E}$called the independent sets which satisfy the conditions: (i)$\\emptyset \\in I$ , (ii)$I'\\subset I \\in I$implies$I'\\in I$ , and (iii)$I_1,I_2 \\in I$and$|I_1| < |I_2|$implies that there is an$e\\in I_2$such that$I_1\\cup \\{e\\} \\in I$ . The rank$rank(M)$of a matroid$M$is the maximum size of an independent set. We say that a matroid$M=(E,I)$is representable over the reals if there is a map$\\varphi \\colon E \\rightarrow \\mathbb{R}^{rank(M)}$such that$I\\in I$if and only if$\\varphi(I)$forms a linearly independent set. We study the problem of matroid realizability over the reals. Given a matroid$M$ , we ask whether there is a set of points in the Euclidean space representing$M$ . We show that matroid realizability is$\\exists \\mathbb R$ -complete, already for matroids of rank 3. The complexity class$\\exists \\mathbb R$can be defined as the family of algorithmic problems that is polynomial-time is equivalent to determining if a multivariate polynomial with integers coefficients has a real root. Our methods are similar to previous methods from the literature. Yet, the result itself was never pointed out and there is no proof readily available in the language of computer science.
Journal Article
Scalable importance tempering and Bayesian variable selection
We propose a Monte Carlo algorithm to sample from high dimensional probability distributions that combines Markov chain Monte Carlo and importance sampling. We provide a careful theoretical analysis, including guarantees on robustness to high dimensionality, explicit comparison with standard Markov chain Monte Carlo methods and illustrations of the potential improvements in efficiency. Simple and concrete intuition is provided for when the novel scheme is expected to outperform standard schemes. When applied to Bayesian variable-selection problems, the novel algorithm is orders of magnitude more efficient than available alternative sampling schemes and enables fast and reliable fully Bayesian inferences with tens of thousand regressors.
Journal Article
Mathematics and computation: a theory revolutionizing technology and science
\"An introduction to computational complexity theory, its connections and interactions with mathematics, and its central role in the natural and social sciences, technology, and philosophy, Mathematics and Computation provides a broad, conceptual overview of computational complexity theorythe mathematical study of efficient computation. With important practical applications to computer science and industry, computational complexity theory has evolved into a highly interdisciplinary field, with strong links to most mathematical areas and to a growing number of scientific endeavors. Avi Wigderson takes a sweeping survey of complexity theory, emphasizing the field's insights and challenges. He explains the ideas and motivations leading to key models, notions, and results. In particular, he looks at algorithms and complexity, computations and proofs, randomness and interaction, quantum and arithmetic computation, and cryptography and learning, all as parts of a cohesive whole with numerous cross-influences. Wigderson illustrates the immense breadth of the field, its beauty and richness, and its diverse and growing interactions with other areas of mathematics. He ends with a comprehensive look at the theory of computation, its methodology and aspirations, and the unique and fundamental ways in which it has shaped and will further shape science, technology, and society.\"- publisher
Book
Randomness Revisited Using the V Programming Language
This book aims to educate the practitioner on pseudo-randomness in particular and discusses a few modern algorithms for random number generation. We attempt to describe what it means for a phenomenon to be random, discuss an approach to quantifying the amount of randomness and testing for statistical quality. A software testing suite is introduced to measure the performance and quality of arbitrary pseudo-random number generators, which are implemented in the V programming language.
eBook