This book grew out of our research, industry consulting and con­ tinuing education courses. Turbo coding initially seemed to belong to a restricted research area, while now has become a part of the mainstream telecommu­ nication theory and practice. The turbo decoding principles have found widespread applications not only in error control, but in de­ tection, interference suppression and equalization. Intended for use by advanced students and professional engi­ neers, involved in coding and telecommunication research, the book includes both basic and advanced material. The chapters are se­ quenced so that the knowledge is acquired in a logical and progres­ sive way. The algorithm descriptions and analysis are supported by examples throughout the book. Performance evaluations of the presented algorithms are carried out both analytically and by sim­ ulations. Basic material included in the book has been taught to students and practicing professionals over the last four years in the form of senior undergraduate or graduate courses, lecture series and short continuing education courses.

Logic and Complexity looks at basic logic as it is used in Computer Science, and provides students with a logical approach to Complexity theory. With plenty of exercises, this book presents classical notions of mathematical logic, such as decidability, completeness and incompleteness, as well as new ideas brought by complexity theory such as NP-completeness, randomness and approximations, providing a better understanding for efficient algorithmic solutions to problems.

This book addresses the interplay between stochastic processes and partial differential equations. More specifically, it focuses on the connection between the nonlinear p-Laplace equation and the stochastic game called tug-of-war with noise. The connection in this context was discovered approximately 15 years ago and has since provided new insights and approaches. These lecture notes provide a brief but detailed and accessible introduction to the subject and to the more research-oriented literature. The book also presents the parabolic case side by side with the elliptic case, highlighting the fact that elliptic and parabolic equations are close in spirit in certain aspects. Moreover, it covers some parts of the regularity theory for these problems.

This book constitutes the refereed proceedings of the 21st International Workshop on Approximation and Online Algorithms, WAOA 2023, held in Amsterdam, The Netherlands, during September 7–8, 2023 The 16 full papers included in this book are carefully reviewed and selected from 43 submissions. The topics of WAOA 2023 were algorithmic game theory, algorithmic trading, coloring and partitioning, competitive analysis, computational advertising, computational finance, cuts and connectivity, FPT-approximation algorithms, geometric problems, graph algorithms, inapproximability results, mechanism design, network design, packing and covering, paradigms for the design and analysis of approximation and online algorithms, resource augmentation, and scheduling problems.

A unified, modern treatment of the theory of random graphs-including recent results and techniques
Since its inception in the 1960s, the theory of random graphs has evolved into a dynamic branch of discrete mathematics. Yet despite the lively activity and important applications, the last comprehensive volume on the subject is Bollobas's well-known 1985 book. Poised to stimulate research for years to come, this new work covers developments of the last decade, providing a much-needed, modern overview of this fast-growing area of combinatorics. Written by three highly respected members of the discrete mathematics community, the book incorporates many disparate results from across the literature, including results obtained by the authors and some completely new results.

Introduces and clarifies the basic theories of 12 structural concepts, offering a fundamental theory of groups, rings and other algebraic structures. Identifies essentials and describes interrelationships between particular theories. Selected classical theorems and results relevant to current research are proved rigorously within the theory of each structure. Throughout the text the reader is frequently prompted to perform integrated exercises of verification and to explore examples.

The aim of this text is to treat selected topics of the subject of contemporary cryptology, structured in five quite independent but related themes:

Cryptography in Chinese consists of two characters meaning "secret coded". Thanks to Ch'in Chiu-Shao and his successors, the Chinese Remainder Theorem became a cornerstone of public key cryptography. Today, as we observe the constant usage of high-speed computers interconnected via the Internet, we realize that cryptography and its related applications have developed far beyond "secret coding". China, which is rapidly developing in all areas of technology, is also writing a new page of history in cryptography. As more and more Chinese become recognized as leading researchers in a variety of topics in cryptography, it is not surprising that many of them are Professor Xiao's former students.

In this introductory textbook the author explains the key topics in cryptography. He takes a modern approach, where defining what is meant by "secure" is as important as creating something that achieves that goal, and security definitions are central to the discussion throughout.

The finite - infinite interplay is central in human thinking, from ancient philosophers and mathematicians (Zeno, Pythagoras), to modern mathe­ matics (Cantor, Hilbert) and computer science (Turing, Godel). Recent developments in mathematics and computer science suggest a) radically new answers to classical questions (e. g. , does infinity exist?, where does infinity come from?, how to reconcile the finiteness of the human brain with the infinity of ideas it produces?), b) new questions of debate (e. g. , what is the role played by randomness?, are computers capable of handling the infinity through unconventional media of computation?, how can one approximate efficiently the finite by the infinite and, conversely, the infinite by finite?). Distinguished authors from around the world, many of them architects of the mathematics and computer science for the new century, contribute to the volume. Papers are as varied as Professor Marcus' activity, to whom this volume is dedicated. They range from real analysis to DNA com­ puting, from linguistics to logic, from combinatorics on words to symbolic dynamics, from automata theory to geography, and so on, plus an incursion into the old history of conceptions about infinity and a list of philosophical "open problems". They are mainly mathematical and theoretical computer science texts, but not all of them are purely mathematical.

Numbers, Information and Complexity is a collection of about 50 articles in honour of Rudolf Ahlswede. His main areas of research are represented in the three sections, Information Theory (Channels and Networks, Combinatorial and Algebraic Coding, Cryptology, with the related fields Data Compression, Entropy Theory, Symbolic Dynamics, Probability and Statistics)', and `Complexity'.

Defined as solutions of linear differential or difference equations with polynomial coefficients, D-finite functions play an important role in various areas of mathematics. This book is a comprehensive introduction to the theory of these functions with a special emphasis on computer algebra algorithms for computing with them: algorithms for detecting relations from given data, for evaluating D-finite functions, for executing closure properties, for obtaining various kinds of “explicit” expressions, for factoring operators, and for definite and indefinite symbolic summation and integration are explained in detail.

This book presents an enticing introduction to tropical circuits and their use as a rigorous mathematical model for dynamic programming (DP), which is one of the most fundamental algorithmic paradigms for solving combinatorial, discrete optimization problems.