Partition functions arise in combinatorics and related problems of statistical physics as they encode in a succinct way the combinatorial structure of complicated systems. The main focus of the book is on efficient ways to compute (approximate) various partition functions, such as permanents, hafnians and their higher-dimensional versions, graph and hypergraph matching polynomials, the independence polynomial of a graph and partition functions enumerating 0-1 and integer points in polyhedra, which allows one to make algorithmic advances in otherwise intractable problems. The book unifies various, often quite recent, results scattered in the literature, concentrating on the three main approaches: scaling, interpolation and correlation decay. The prerequisites include moderate amounts of real and complex analysis and linear algebra, making the book accessible to advanced math and physics undergraduates.
This book for graduate students and researchers introduces examples of complexity phenomena related to observed plasma processes in the space environment.
This textbook tackles the problem of formulating AI systems by combining probabilistic modeling and deep learning. Moreover, it goes beyond typical predictive modeling and brings together supervised learning and unsupervised learning. The resulting paradigm, called deep generative modeling, utilizes the generative perspective on perceiving the surrounding world. It assumes that each phenomenon is driven by an underlying generative process that defines a joint distribution over random variables and their stochastic interactions, i.e., how events occur and in what order. The adjective "deep" comes from the fact that the distribution is parameterized using deep neural networks. There are two distinct traits of deep generative modeling. First, the application of deep neural networks allows rich and flexible parameterization of distributions. Second, the principled manner of modeling stochastic dependencies using probability theory ensures rigorous formulation and prevents potential flaws in reasoning. Moreover, probability theory provides a unified framework where the likelihood function plays a crucial role in quantifying uncertainty and defining objective functions. Deep Generative Modeling is designed to appeal to curious students, engineers, and researchers with a modest mathematical background in undergraduate calculus, linear algebra, probability theory, and the basics in machine learning, deep learning, and programming in Python and PyTorch (or other deep learning libraries). It will appeal to students and researchers from a variety of backgrounds, including computer science, engineering, data science, physics, and bioinformatics, who wish to become familiar with deep generative modeling. To engage the reader, the book introduces fundamental concepts with specific examples and code snippets. The full code accompanying the book is available on github. The ultimate aim of the book is to outline the most important techniques in deep generative modeling and, eventually, enable readers to formulate new models and implement them.
Annotation The two-volume set LNCS 6198 and LNCS 6199 constitutes the refereed proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP 2010, held in Bordeaux, France, in July 2010. The 106 revised full papers (60 papers for track A, 30 for track B, and 16 for track C) presented together with 6 invited talks were carefully reviewed and selected from a total of 389 submissions. The papers are grouped in three major tracks on algorithms, complexity and games; on logic, semantics, automata, and theory of programming; as well as on foundations of networked computation: models, algorithms and information management. LNCS 6198 contains 60 contributions of track A selected from 222 submissions as well as 2 invited talks.
This book constitutes the refereed proceedings of the 16th Annual International Conference on Computing and Combinatorics, held in Dallas, TX, USA, in August 2011. The 54 revised full papers presented were carefully reviewed and selected from 136 submissions. Topics covered are algorithms and data structures; algorithmic game theory and online algorithms; automata, languages, logic, and computability; combinatorics related to algorithms and complexity; complexity theory; computational learning theory and knowledge discovery; cryptography, reliability and security, and database theory; computational biology and bioinformatics; computational algebra, geometry, and number theory; graph drawing and information visualization; graph theory, communication networks, and optimization; parallel and distributed computing.
This book presents a systematic overview on partition function form games: a game form in cooperative game theory to integrate externalities for various applications. Cooperative game theory has been immensely useful to study a wide range of issues, but the standard approaches ignore the side effects of cooperation. Recently interest shifted to problems where externalities play the main roles such as models of cooperation in market competition or the shared use of public resources. Such problems require richer models that can explicitly evaluate the side-effects of cooperation. In partition function form games the value of cooperation depends on the outsiders' actions. A recent surge of interest driven by applications has made results very fragmented. This book offers an accessible, yet comprehensive and systematic study of properties, solutions and applications of partition function games surveying both theoretical results and their applications. It assembles a survey of existing research and smaller original results as well as original interpretations and comparisons. The book is self-contained and accessible for readers with little or no knowledge of cooperative game theory.
The topic of this book is the following optimisation problem: given a set of discrete variables and a set of functions, each depending on a subset of the variables, minimise the sum of the functions over all variables. This fundamental research problem has been studied within several different contexts of discrete mathematics, computer science and artificial intelligence under different names: Min-Sum problems, MAP inference in Markov random fields (MRFs) and conditional random fields (CRFs), Gibbs energy minimisation, valued constraint satisfaction problems (VCSPs), and, for two-state variables, pseudo-Boolean optimisation. In this book the author presents general techniques for analysing the structure of such functions and the computational complexity of the minimisation problem, and he gives a comprehensive list of tractable cases. Moreover, he demonstrates that the so-called algebraic approach to VCSPs can be used not only for the search for tractable VCSPs, but also for other questions such as finding the boundaries to the applicability of certain algorithmic techniques. The book is suitable for researchers interested in methods and results from the area of constraint programming and discrete optimisation.
This two-part volume represents the proceedings of the Fifth International Congress of Chinese Mathematicians, held at Tsinghua University, Beijing, in December 2010. The Congress brought together eminent Chinese and overseas mathematicians to discuss the latest developments in pure and applied mathematics. Included are 60 papers based on lectures given at the conference.
This book constitutes the refereed proceedings of the 4th International Frontiers of Algorithmics Workshop, FAW 2010, held in Wuhan, China, in August 2010. The 28 revised full papers presented together with the abstracts of 3 invited talks were carefully reviewed and selected from 57 submissions. The Workshop will provide a focused forum on current trends of research on algorithms, discrete structures, and their applications, and will bring together international experts at the research frontiers in these areas to exchange ideas and to present significant new results. The mission of the Workshop is to stimulate the various fields for which algorithmics can become a crucial enabler, and to strengthen the ties between the Eastern and Western research communities of algorithmics and applications.
