Search Results

This chapter explores how spin glass concepts have found use in and, in some cases, further advanced areas such as computational complexity, combinatorial optimization, neural networks, protein conformational dynamics and folding, and computer science (through the introduction of new heuristic algorithms such as simulated annealing and neural-based computation, and through new approaches to analyzing hard combinatorial optimization problems). It also introduces some “short takes” on topics that space constraints prevent covering in detail, but should be at least mentioned: prebiotic evolution, Kauffman's NK model, and the maturation of the immune response. The chapter summarizes the heart of what most people mean when they refer to spin glasses as relevant to complexity. It focuses on the early, classic papers in each subject, giving the reader a flavor of each.

Combinatorial optimization offers a rigorous but powerful approach to user interface design problems, defining problems mathematically such that they can be algorithmically solved. Design is defined as algorithmic combination of design decisions to obtain an optimal solution defined by an objective function. There are strong rationale for this method. First, core concepts such as ’design task’, ’design objective’, and ’optimal design’ become explicit and actionable. Second, solutions work well in practice, even for some problems traditionally out of reach of manual solutions. The method can assist in the generation, refinement, and adaptation of design. However, mathematical expression of HCI problems has been challenging and curbed applications. This chapter introduces combinatorial optimisation from user interface design point of view, and addresses two core challenges: 1) mathematical definition of design problems and 2) expression of evaluative knowledge such as design heuristics and predictive models of interaction.

This chapter is a non-technical, elementary introduction to the theory of glassy phases and their ubiquity. The aim is to provide a guide and some kind of coherent view to the various topics that have been explored in recent years in this very diverse field, ranging from spin or structural glasses to protein folding, combinatorial optimization, neural networks, error correcting codes, and game theory.

In this chapter, a first, tentative attempt is made to define the nature and scope of what is meant by computable economics. From a study of the way economics was mathematized in the modern era, – i.e., since about the late 1920s – I try to extract those studies and examples that attempted recursion theoretic characterizations of economic theoretic problems. These are then distilled and codified as early examples of computable economics. The chapter also discusses, more specifically but concisely, the contributions of Herbert Simon from a recursion theoretic point of view.

Decision-making under uncertainty is a central topic of this book. A common scenario is the following: data is recorded from some (digital) sensor device, and we know (or assume) that there is some “underlying” signal contained in this data, which is obscured by noise. The goal is to extract this signal, but the noise causes this task to be impossible: we can never know the actual underlying signal. We must make mathematical assumptions that make this taskp possible at all. Uncertainty is formalized through the mathematical machinery of probability, and decisions are made that find the optimal choices under these assumptions. This chapter explores the main methods by which these optimal choices are made in DSP and machine learning.

The mathematical structure highlighted in this chapter by the factor graph representation is the locality of probabilistic dependencies between variables. Locality also emerges in many problems of probabilistic inference, which provides another unifying view of the field. This chapter describes coding theory, statistical physics, and combinatorial optimization as inference problems. It also explores one generic inference method, the use of Monte Carlo Markov chains (MCMC) in order to sample from complex probabilistic models. Many of the difficulties encountered in decoding, in constraint satisfaction problems, or in glassy phases, are connected to a dramatic slowing down of MCMC dynamics, which is explored through simple numerical experiments on some examples.

Chapter 6 examines one of the greatest unsolved challenges in mathematics - the problem of finding the best solution from a large number of possibilities. The Traveling Salesman Problem requires that the shortest tour of a group of cities is determined. Surprisingly, the only way to guarantee finding the shortest tour is to measure the length of all possible tours. Exhaustive search such as this is very slow. For centuries, mathematicians have sought to find fast algorithms for solving combinatorial search problems. The most famous was invented by Edsger Dijkstra in 1956. Dijkstra’s algorithm finds the shortest route between cities on a roadmap and is now used in all satellite navigation apps. The Gale-Shapley algorithm solves the problem of matching pairs of items according to user preferences. John Holland took the radical step of accelerating combinatorial search by mimicking natural evolution in a computer.