Daniel L. Stein and Charles M. Newman
- Published in print:
- 2013
- Published Online:
- October 2017
- ISBN:
- 9780691147338
- eISBN:
- 9781400845637
- Item type:
- chapter
- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691147338.003.0007
- Subject:
- Sociology, Science, Technology and Environment
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 ...
More
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.Less
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.
Antti Oulasvirta and Andreas Karrenbauer
- Published in print:
- 2018
- Published Online:
- March 2018
- ISBN:
- 9780198799603
- eISBN:
- 9780191839832
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/oso/9780198799603.003.0005
- Subject:
- Mathematics, Logic / Computer Science / Mathematical Philosophy
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 ...
More
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.Less
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.
Daniel L. Stein and Charles M. Newman
- Published in print:
- 2013
- Published Online:
- October 2017
- ISBN:
- 9780691147338
- eISBN:
- 9781400845637
- Item type:
- book
- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691147338.001.0001
- Subject:
- Sociology, Science, Technology and Environment
Spin glasses are disordered magnetic systems that have led to the development of mathematical tools with an array of real-world applications, from airline scheduling to neural networks. This book ...
More
Spin glasses are disordered magnetic systems that have led to the development of mathematical tools with an array of real-world applications, from airline scheduling to neural networks. This book offers the most concise, engaging, and accessible introduction to the subject, fully explaining what spin glasses are, why they are important, and how they are opening up new ways of thinking about complexity. This one-of-a-kind guide to spin glasses begins by explaining the fundamentals of order and symmetry in condensed matter physics and how spin glasses fit into and modify this framework. The book then explores how spin-glass concepts and ideas have found applications in areas as diverse as computational complexity, biological and artificial neural networks, protein folding, immune response maturation, combinatorial optimization, and social network modeling. Providing an essential overview of the history, science, and growing significance of this exciting field, the book also features a forward-looking discussion of what spin glasses may teach us in the future about complex systems. This is a useful book for students and practitioners in the natural and social sciences, with new material even for the experts.Less
Spin glasses are disordered magnetic systems that have led to the development of mathematical tools with an array of real-world applications, from airline scheduling to neural networks. This book offers the most concise, engaging, and accessible introduction to the subject, fully explaining what spin glasses are, why they are important, and how they are opening up new ways of thinking about complexity. This one-of-a-kind guide to spin glasses begins by explaining the fundamentals of order and symmetry in condensed matter physics and how spin glasses fit into and modify this framework. The book then explores how spin-glass concepts and ideas have found applications in areas as diverse as computational complexity, biological and artificial neural networks, protein folding, immune response maturation, combinatorial optimization, and social network modeling. Providing an essential overview of the history, science, and growing significance of this exciting field, the book also features a forward-looking discussion of what spin glasses may teach us in the future about complex systems. This is a useful book for students and practitioners in the natural and social sciences, with new material even for the experts.
Guillaume Fertin, Anthony Labarre, Irena Rusu, Eric Tannier, and Stéphane Vialette
- Published in print:
- 2009
- Published Online:
- August 2013
- ISBN:
- 9780262062824
- eISBN:
- 9780262258753
- Item type:
- book
- Publisher:
- The MIT Press
- DOI:
- 10.7551/mitpress/9780262062824.001.0001
- Subject:
- Mathematics, Mathematical Biology
From one cell to another, from one individual to another, and from one species to another, the content of DNA molecules is often similar. The organization of these molecules, however, differs ...
More
From one cell to another, from one individual to another, and from one species to another, the content of DNA molecules is often similar. The organization of these molecules, however, differs dramatically, and the mutations that affect this organization are known as genome rearrangements. Combinatorial methods are used to reconstruct putative rearrangement scenarios in order to explain the evolutionary history of a set of species, often formalizing the evolutionary events that can explain the multiple combinations of observed genomes as combinatorial optimization problems. This book offers a comprehensive survey of this rapidly expanding application of combinatorial optimization. It can be used as a reference for experienced researchers or as an introductory text for a broader audience. Genome rearrangement problems have proved so interesting from a combinatorial point of view that the field now belongs as much to mathematics as to biology. The book takes a mathematically oriented approach, but provides biological background when necessary. It presents a series of models, beginning with the simplest (which is progressively extended by dropping restrictions), each constructing a genome rearrangement problem. The book also discusses an important generalization of the basic problem known as the median problem, surveys attempts to reconstruct the relationships between genomes with phylogenetic trees, and offers a collection of summaries and appendixes with additional information.Less
From one cell to another, from one individual to another, and from one species to another, the content of DNA molecules is often similar. The organization of these molecules, however, differs dramatically, and the mutations that affect this organization are known as genome rearrangements. Combinatorial methods are used to reconstruct putative rearrangement scenarios in order to explain the evolutionary history of a set of species, often formalizing the evolutionary events that can explain the multiple combinations of observed genomes as combinatorial optimization problems. This book offers a comprehensive survey of this rapidly expanding application of combinatorial optimization. It can be used as a reference for experienced researchers or as an introductory text for a broader audience. Genome rearrangement problems have proved so interesting from a combinatorial point of view that the field now belongs as much to mathematics as to biology. The book takes a mathematically oriented approach, but provides biological background when necessary. It presents a series of models, beginning with the simplest (which is progressively extended by dropping restrictions), each constructing a genome rearrangement problem. The book also discusses an important generalization of the basic problem known as the median problem, surveys attempts to reconstruct the relationships between genomes with phylogenetic trees, and offers a collection of summaries and appendixes with additional information.
M. Mézard
- Published in print:
- 2004
- Published Online:
- September 2007
- ISBN:
- 9780198528531
- eISBN:
- 9780191713415
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198528531.003.0017
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics
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 ...
More
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.Less
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.
Kumaraswamy Velupillai
- Published in print:
- 2000
- Published Online:
- November 2003
- ISBN:
- 9780198295273
- eISBN:
- 9780191596988
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/0198295278.003.0002
- Subject:
- Economics and Finance, Macro- and Monetary Economics
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, – ...
More
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.Less
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.
Marc Mézard and Andrea Montanari
- Published in print:
- 2009
- Published Online:
- September 2009
- ISBN:
- 9780198570837
- eISBN:
- 9780191718755
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198570837.003.0013
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics
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 ...
More
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.Less
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.
James Oxley
- Published in print:
- 2011
- Published Online:
- December 2013
- ISBN:
- 9780198566946
- eISBN:
- 9780191774904
- Item type:
- book
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198566946.001.0001
- Subject:
- Mathematics, Educational Mathematics
Seventy-five years of the study of matroids has seen the development of a rich theory with links to graphs, lattices, codes, transversals,0020and projective geometries. Matroids are of fundamental ...
More
Seventy-five years of the study of matroids has seen the development of a rich theory with links to graphs, lattices, codes, transversals,0020and projective geometries. Matroids are of fundamental importance in combinatorial optimization and their applications extend into electrical and structural engineering. This book falls into two parts: the first provides a comprehensive introduction to the basics of matroid theory, while the second treats more advanced topics. It contains over 700 exercises, and includes proofs of all of the major theorems in the subject. The last two chapters review current research and list more than eighty unsolved problems along with a description of the progress towards their solutions.Less
Seventy-five years of the study of matroids has seen the development of a rich theory with links to graphs, lattices, codes, transversals,0020and projective geometries. Matroids are of fundamental importance in combinatorial optimization and their applications extend into electrical and structural engineering. This book falls into two parts: the first provides a comprehensive introduction to the basics of matroid theory, while the second treats more advanced topics. It contains over 700 exercises, and includes proofs of all of the major theorems in the subject. The last two chapters review current research and list more than eighty unsolved problems along with a description of the progress towards their solutions.
