This book brings together contributions by leading researchers in computational complexity theory written in honor of Somenath Biswas on the occasion of his sixtieth birthday. They discuss current trends and exciting developments in this flourishing area of research and offer fresh perspectives on various aspects of complexity theory. The topics covered include arithmetic circuit complexity, lower bounds and polynomial identity testing, the isomorphism conjecture, space-bounded computation...

MULTIPLY your chances of understanding DISCRETE MATHEMATICSIf you're interested in learning the fundamentals of discrete mathematics but can't seem to get your brain to function, then here's your solution. Add this easy-to-follow guide to the equation and calculate how quickly you learn the essential concepts.Written by award-winning math professor Steven Krantz, Discrete Mathematics Demystified explains this challenging topic in an effective and e...

Despite growing interest, basic information on methods and models for mathematically analyzing algorithms has rarely been directly accessible to practitioners, researchers, or students. An Introduction to the Analysis of Algorithms, Second Edition, organizes and presents that knowledge, fully introducing primary techniques and results in the field.Robert Sedgewick and the late Philippe Flajolet have drawn from both classical mathematics and computer scienc...

This beginning graduate textbook describes both recent achievements and classical results of computational complexity theory. Requiring essentially no background apart from mathematical maturity, the book can be used as a reference for self-study for anyone interested in complexity, including physicists, mathematicians, and other scientists, as well as a textbook for a variety of courses and seminars. More than 300 exercises are included with a selected hint set. The book starts with a bro...

The bible of all fundamental algorithms and the work that taught many of today's software developers most of what they know about computer programming.–Byte, September 1995I can't begin to tell you how many pleasurable hours of study and recreation they have afforded me! I have pored over them in cars, restaurants, at work, at home... and even at a Little League game when my son wasn't in the line-up.–Charles LongIf you think y...

This fundamental monograph introduces both the probabilistic and algebraic aspects of information theory and coding. It has evolved from the authors' years of experience teaching at the undergraduate level, including several Cambridge Maths Tripos courses. The book provides relevant background material, a wide range of worked examples and clear solutions to problems from real exam papers. It is a valuable teaching aid for undergraduate and graduate students, or for researchers and engineer...

Algebraic & geometry methods have constituted a basic background and tool for people working on classic block coding theory and cryptography. Nowadays, new paradigms on coding theory and cryptography have arisen such as: Network coding, S-Boxes, APN Functions, Steganography and decoding by linear programming. Again understanding the underlying procedure and symmetry of these topics needs a whole bunch of non trivial knowledge of algebra and geometry that will be used to both, evaluate thos...

Phylogenetic combinatorics is a branch of discrete applied mathematics concerned with the combinatorial description and analysis of phylogenetic trees and related mathematical structures such as phylogenetic networks and tight spans. Based on a natural conceptual framework, the book focuses on the interrelationship between the principal options for encoding phylogenetic trees: split systems, quartet systems and metrics. Such encodings provide useful options for analyzing and manipulating p...

The focus of this book is the P versus NP Question and the theory of NP-completeness. It also provides adequate preliminaries regarding computational problems and computational models. The P versus NP Question asks whether or not finding solutions is harder than checking the correctness of solutions. An alternative formulation asks whether or not discovering proofs is harder than verifying their correctness. It is widely believed that the answer to these equivalent formulations is positive...

Computability Theory: An Introduction to Recursion Theory provides a concise, comprehensive, and authoritative introduction to contemporary computability theory, techniques, and results. The basic concepts and techniques of computability theory are placed in their historical, philosophical and logical context. This presentation is characterized by an unusual breadth of coverage and the inclusion of advanced topics not to be found elsewhere in the literature at this level. The text includes...

This is the second edition of a popular book on combinatorics, a subject dealing with ways of arranging and distributing objects, and which involves ideas from geometry, algebra and analysis. The breadth of the theory is matched by that of its applications, which include topics as diverse as codes, circuit design and algorithm complexity. It has thus become essential for workers in many scientific fields to have some familiarity with the subject. The authors have tried to be as comprehensi...