? DoesP=NP. In just ?ve symbols Dick Karp -in 1972-captured one of the deepest and most important questions of all time. When he ?rst wrote his famous paper, I think it's fair to say he did not know the depth and importance of his question. Now over three decades later, we know P=NP is central to our understanding of compu- tion, it is a very hard problem, and its resolution will have potentially tremendous consequences. This book is a collection of some of the most popular posts from my blog- Godel Lost Letter andP=NP-which I started in early 2009. The main thrust of the blog, especially when I started, was to explore various aspects of computational complexity around the famousP=NP question. As I published posts I branched out and covered additional material, sometimes a timely event, sometimes a fun idea, sometimes a new result, and sometimes an old result. I have always tried to make the posts readable by a wide audience, and I believe I have succeeded in doing this.

This book constitutes the refereed proceedings of the 7th International Conference on Similarity Search and Applications, SISAP 2014, held in A Coruna, Spain, in October 2014. The 21 full papers and 6 short papers presented were carefully reviewed and selected from 45 submissions. The papers are organized in topical sections on Improving Similarity Search Methods and Techniques; Indexing and Applications; Metrics and Evaluation; New Scenarios and Approaches; Applications and Specific Domains.

Computer Science and Operations Research continue to have a synergistic relationship and this book represents the results of the cross-fertilization between OR/MS and CS/AI. It is this interface of OR/CS that makes possible advances that could not have been achieved in isolation. Taken collectively, these articles are indicative of the state of the art in the interface between OR/MS and CS/AI and of the high-caliber research being conducted by members of the INFORMS Computing Society.

This is a revised edition of the ?rst printing which appeared in 2002. The book is based on lectures at the University of Bergen, Norway.Over the years these lectures have covered many different aspects and facets of the wonderful ?eld of geometry. Consequently it has never been possible to give a full and ?nal account of geometry as such, at an undergraduatelevel: A carefully consideredselection has always been necessary. The present book constitutes the main central themes of these selections. One of the groups I am aiming at, is future teachers of mathematics. All too oftenthe textsdealingwith geometrywhichgo intothe syllabusforteacher-students present the material in ways which appear pedantic and formalistic, suppressing the very powerful and dynamic character of this old ?eld, which at the same time so young. Geometry is a ?eld of mathematical insight, research, history and source of artistic inspiration. And not least important, an integral part of our common cultural heritage.

This volume contains 27 contributions to the Forth Russian-German Advanced Research Workshop on Computational Science and High Performance Computing presented in October 2009 in Freiburg, Germany. The workshop was organized jointly by the High Performance Computing Center Stuttgart (HLRS), the Institute of Computational Technologies of the Siberian Branch of the Russian Academy of Sciences (ICT SB RAS) and the Section of Applied Mathematics of the University of Freiburg (IAM Freiburg) The contributions range from computer science, mathematics and high performance computing to applications in mechanical and aerospace engineering. They show a wealth of theoretical work and simulation experience with a potential of bringing together theoretical mathematical modelling and usage of high performance computing systems presenting the state of the art of computational technologies.

Hybrid systems are models for complex physical systems and have become a widely used concept for understanding their behavior. Many applications are safety-critical, including car, railway, and air traffic control, robotics, physical-chemical process control, and biomedical devices. Hybrid systems analysis studies how we can build computerized controllers for physical systems which are guaranteed to meet their design goals. The author gives a unique, logic-based perspective on hybrid systems analysis. It is the first book that leverages the power of logic for hybrid systems. The author develops a coherent logical approach for systematic hybrid systems analysis, covering its theory, practice, and applications. It is further shown how the developed verification techniques can be used to study air traffic and railway control systems. This book is intended for researchers, postgraduates, and professionals who are interested in hybrid systems analysis, cyberphysical or embedded systems design, logic and theorem proving, or transportation and automation.

Logic circuits are becoming increasingly susceptible to probabilistic behavior caused by external radiation and process variation. In addition, inherently probabilistic quantum- and nano-technologies are on the horizon as we approach the limits of CMOS scaling. Ensuring the reliability of such circuits despite the probabilistic behavior is a key challenge in IC design---one that necessitates a fundamental, probabilistic reformulation of synthesis and testing techniques. This monograph will present techniques for analyzing, designing, and testing logic circuits with probabilistic behavior.

This volume contains the articles presented at the 21st International Meshing Roundtable (IMR) organized, in part, by Sandia National Laboratories and was held on October 7-10, 2012 in San Jose, CA, USA. The first IMR was held in 1992, and the conference series has been held annually since. Each year the IMR brings together researchers, developers, and application experts in a variety of disciplines, from all over the world, to present and discuss ideas on mesh generation and related topics. The technical papers in this volume present theoretical and novel ideas and algorithms with practical potential, as well as technical applications in science and engineering, geometric modeling, computer graphics, and visualization.

This book constitutes the thoroughly refereed conference proceedings of the 9th International Conference on Rough Sets and Knowledge Technology, RSKT 2014, held in Shanghai, China, in October 2014. The 70 papers presented were carefully reviewed and selected from 162 submissions. The papers in this volume cover topics such as foundations and generalizations of rough sets, attribute reduction and feature selection, applications of rough sets, intelligent systems and applications, knowledge technology, domain-oriented data-driven data mining, uncertainty in granular computing, advances in granular computing, big data to wise decisions, rough set theory, and three-way decisions, uncertainty, and granular computing.

In January 2012 an Oberwolfach workshop took place on the topic of recent developments in the numerics of partial differential equations. Focus was laid on methods of high order and on applications in Computational Fluid Dynamics. The book covers most of the talks presented at this workshop.

This book constitutes the refereed proceedings of the 8th International Conference on Combinatorial Optimization and Applications, COCOA 2014, held on the island of Maui, Hawaii, USA, in December 2014. The 56 full papers included in the book were carefully reviewed and selected from 133 submissions. Topics covered include classic combinatorial optimization; geometric optimization; network optimization; optimization in graphs; applied optimization; CSoNet; and complexity, cryptography, and games.

The Applied Mathematics, Modelling, and Computational Science (AMMCS) conference aims to promote interdisciplinary research and collaboration. The contributions in this volume cover the latest research in mathematical and computational sciences, modeling, and simulation as well as their applications in natural and social sciences, engineering and technology, industry, and finance. The 2013 conference, the second in a series of AMMCS meetings, was held August 26-30 and organized in cooperation with AIMS and SIAM, with support from the Fields Institute in Toronto, and Wilfrid Laurier University. There were many young scientists at AMMCS-2013, both as presenters and as organizers. This proceedings contains refereed papers contributed by the participants of the AMMCS-2013 after the conference. This volume is suitable for researchers and graduate students, mathematicians and engineers, industrialists, and anyone who would like to delve into the interdisciplinary research of applied and computational mathematics and its areas of applications.

This timely text presents a comprehensive overview of fault tolerance techniques for high-performance computing (HPC). The text opens with a detailed introduction to the concepts of checkpoint protocols and scheduling algorithms, prediction, replication, silent error detection and correction, together with some application-specific techniques such as ABFT. Emphasis is placed on analytical performance models. This is then followed by a review of general-purpose techniques, including several checkpoint and rollback recovery protocols. Relevant execution scenarios are also evaluated and compared through quantitative models. Features: provides a survey of resilience methods and performance models; examines the various sources for errors and faults in large-scale systems; reviews the spectrum of techniques that can be applied to design a fault-tolerant MPI; investigates different approaches to replication; discusses the challenge of energy consumption of fault-tolerance methods in extreme-scale systems.

This book discusses recent developments in semigroup theory and its applications in areas such as operator algebras, operator approximations and category theory. All contributing authors are eminent researchers in their respective fields, from across the world. Their papers, presented at the 2014 International Conference on Semigroups, Algebras and Operator Theory in Cochin, India, focus on recent developments in semigroup theory and operator algebras. They highlight current research activities on the structure theory of semigroups as well as the role of semigroup theoretic approaches to other areas such as rings and algebras. The deliberations and discussions at the conference point to future research directions in these areas. This book presents 16 unpublished, high-quality and peer-reviewed research papers on areas such as structure theory of semigroups, decidability vs. undecidability of word problems, regular von Neumann algebras, operator theory and operator approximations. Interested researchers will find several avenues for exploring the connections between semigroup theory and the theory of operator algebras.

Imagine yourself as a military officer in a conflict zone trying to identify locations of weapons caches supporting road-side bomb attacks on your country's troops. Or imagine yourself as a public health expert trying to identify the location of contaminated water that is causing diarrheal diseases in a local population. Geospatial abduction is a new technique introduced by the authors that allows such problems to be solved. Geospatial Abduction provides the mathematics underlying geospatial abduction and the algorithms to solve them in practice; it has wide applicability and can be used by practitioners and researchers in many different fields. Real-world applications of geospatial abduction to military problems are included. Compelling examples drawn from other domains as diverse as criminology, epidemiology and archaeology are covered as well. This book also includes access to a dedicated website on geospatial abduction hosted by University of Maryland. Geospatial Abduction targets practitioners working in general AI, game theory, linear programming, data mining, machine learning, and more. Those working in the fields of computer science, mathematics, geoinformation, geological and biological science will also find this book valuable.

This book constitutes the refereed proceedings of the 4th International Symposium on Model-Based Safety and Assessment, IMBSA 2014, held in Munich, Germany, in October 2014. The 15 revised full papers presented were carefully reviewed and selected from numerous submissions. The papers are organized in topical sections on modeling paradigms, validation and testing, fault detection and handling, safety assessment in the automotive domain, and case studies.

This book reviews the state-of-the-art in combinatorial testing, with particular emphasis on the automatic generation of test data. It describes the most commonly used approaches in this area - including algebraic construction, greedy methods, evolutionary computation, constraint solving and optimization - and explains major algorithms with examples. In addition, the book lists a number of test generation tools, as well as benchmarks and applications. Addressing a multidisciplinary topic, it will be of particular interest to researchers and professionals in the areas of software testing, combinatorics, constraint solving and evolutionary computation.

Due to the fast growth of the Web and the difficulties in finding desired information, efficient and effective information retrieval systems have become more important than ever, and the search engine has become an essential tool for many people. The ranker, a central component in every search engine, is responsible for the matching between processed queries and indexed documents. Because of its central role, great attention has been paid to the research and development of ranking technologies. In addition, ranking is also pivotal for many other information retrieval applications, such as collaborative filtering, definition ranking, question answering, multimedia retrieval, text summarization, and online advertisement. Leveraging machine learning technologies in the ranking process has led to innovative and more effective ranking models, and eventually to a completely new research area called "learning to rank". Liu first gives a comprehensive review of the major approaches to learning to rank. For each approach he presents the basic framework, with example algorithms, and he discusses its advantages and disadvantages. He continues with some recent advances in learning to rank that cannot be simply categorized into the three major approaches - these include relational ranking, query-dependent ranking, transfer ranking, and semisupervised ranking. His presentation is completed by several examples that apply these technologies to solve real information retrieval problems, and by theoretical discussions on guarantees for ranking performance. This book is written for researchers and graduate students in both information retrieval and machine learning. They will find here the only comprehensive description of the state of the art in a field that has driven the recent advances in search engine development.

Information theory has proved to be effective for solving many computer vision and pattern recognition (CVPR) problems (such as image matching, clustering and segmentation, saliency detection, feature selection, optimal classifier design and many others). Nowadays, researchers are widely bringing information theory elements to the CVPR arena. Among these elements there are measures (entropy, mutual information...), principles (maximum entropy, minimax entropy...) and theories (rate distortion theory, method of types...). This book explores and introduces the latter elements through an incremental complexity approach at the same time where CVPR problems are formulated and the most representative algorithms are presented. Interesting connections between information theory principles when applied to different problems are highlighted, seeking a comprehensive research roadmap. The result is a novel tool both for CVPR and machine learning researchers, and contributes to a cross-fertilization of both areas.

This book constitutes the refereed proceedings of the 13th International Scientific Conference on Information Technologies and Mathematical Modeling, named after A.F. Terpugov, ITMM 2014, Anzhero-Sudzhensk, Russia, held in Anzhero-Sudzhensk, Russia, in November 2014. The 50 full papers included in this volume were carefully reviewed and selected from 254 submissions. The papers focus on probabilistic methods and models, queueing theory, telecommunication systems, and software engineering.

This book is devoted to Professor Jurgen Lehn, who passed away on September 29, 2008, at the age of 67. It contains invited papers that were presented at the Wo- shop on Recent Developments in Applied Probability and Statistics Dedicated to the Memory of Professor Jurgen Lehn, Middle East Technical University (METU), Ankara, April 23-24, 2009, which was jointly organized by the Technische Univ- sitat Darmstadt (TUD) and METU. The papers present surveys on recent devel- ments in the area of applied probability and statistics. In addition, papers from the Panel Discussion: Impact of Mathematics in Science, Technology and Economics are included. Jurgen Lehn was born on the 28th of April, 1941 in Karlsruhe. From 1961 to 1968 he studied mathematics in Freiburg and Karlsruhe, and obtained a Diploma in Mathematics from the University of Karlsruhe in 1968. He obtained his Ph.D. at the University of Regensburg in 1972, and his Habilitation at the University of Karlsruhe in 1978. Later in 1978, he became a C3 level professor of Mathematical Statistics at the University of Marburg. In 1980 he was promoted to a C4 level professorship in mathematics at the TUD where he was a researcher until his death.

Over time, basic research tends to lead to specialization - increasingly narrow t- ics are addressed by increasingly focussed communities, publishing in increasingly con ned workshops and conferences, discussing increasingly incremental contri- tions. Already the community of programming languages is split into various s- communities addressing different aspects and paradigms (functional, imperative, relational, and object-oriented). Only a few people manage to maintain a broader view, and even fewer step back in order to gain an understanding about the basic principles, their interrelation, and their impact in a larger context. The pattern calculus is the result of a profound re-examination of a 50-year - velopment. It attempts to provide a unifying approach, bridging the gaps between different programming styles and paradigms according to a new slogan - compu- tion is pattern matching. It is the contribution of this book to systematically and elegantly present and evaluate the power of pattern matching as the guiding paradigm of programming. Patterns are dynamically generated, discovered, passed, applied, and automatically adapted, based on pattern matching and rewriting technology, which allows one to elegantly relate things as disparate as functions and data structures. Of course, pattern matching is not new. It underlies term rewriting - it is, for example, inc- porated in, typically functional, programming languages, like Standard ML - but it has never been pursued as the basis of a unifying framework for programming.

This book covers local search for combinatorial optimization and its extension to mixed-variable optimization. Although not yet understood from the theoretical point of view, local search is the paradigm of choice for tackling large-scale real-life optimization problems. Today's end-users demand interactivity with decision support systems. For optimization software, this means obtaining good-quality solutions quickly. Fast iterative improvement methods, like local search, are suited to satisfying such needs. Here the authors show local search in a new light, in particular presenting a new kind of mathematical programming solver, namely LocalSolver, based on neighborhood search.

First, an iconoclast methodology is presented to design and engineer local search algorithms. The authors' concern about industrializing local search approaches is of particular interest for practitioners. This methodology is applied to solve two industrial problems with high economic stakes. Software based on local search induces extra costs in development and maintenance in comparison with the direct use of mixed-integer linear programming solvers. The authors then move on to present the LocalSolver project whose goal is to offer the power of local search through a model-and-run solver for large-scale 0-1 nonlinear programming. They conclude by presenting their ongoing and future work on LocalSolver toward a full mathematical programming solver based on local search.

This book constitutes the refereed proceedings of the 7th International Conference on Software Language Engineering, SLE 2014, held in Vasteras, Sweden, in September 2014. The 19 revised full papers presented together with 1 invited paper were carefully reviewed and selected from 61 initial submissions. The papers observe software languages from different and yet complementary perspectives: programming languages, model driven engineering, domain specific languages, semantic web, and from different technological spaces: context-free grammars, object-oriented modeling frameworks, rich data, structured data, object-oriented programming, functional programming, logic programming, term-rewriting, attribute grammars, algebraic specification, etc.

Information is an important concept that is studied extensively across a range of disciplines, from the physical sciences to genetics to psychology to epistemology. Information continues to increase in importance, and the present age has been referred to as the "Information Age." One may understand information in a variety of ways. For some, information is found in facts that were previously unknown. For others, a fact must have some economic value to be considered information. Other people emphasize the movement through a communication channel from one location to another when describing information. In all of these instances, information is the set of characteristics of the output of a process. Yet Information has seldom been studied in a consistent way across different disciplines. Information from Processes provides a discipline-independent and precise presentation of both information and computing processes. Information concepts and phenomena are examined in an effort to understand them, given a hierarchy of information processes, where one process uses others. Research about processes and computing is applied to answer the question of what information can and cannot be produced, and to determine the nature of this information (theoretical information science). The book also presents some of the basic processes that are used in specific domains (applied information science), such as those that generate information in areas like reasoning, the evolution of informative systems, cryptography, knowledge, natural language, and the economic value of information. Written for researchers and graduate students in information science and related fields, Information from Processes details a unique information model independent from other concepts in computer or archival science, which is thus applicable to a wide range of domains. Combining theoretical and empirical methods as well as psychological, mathematical, philosophical, and economic techniques, Losee's book delivers a solid basis and starting point for future discussions and research about the creation and use of information.