The interconnection network is one of the most basic components of a massively parallel computer system. Such systems consist of hundreds or thousands of processors interconnected to work cooperatively on computations. One of the central problems in parallel computing is the task of mapping a collection of processes onto the processors and routing network of a parallel machine. Once this mapping is done, it is critical to schedule computations within and communication among processors so that the necessary inputs for a process are available where and when the process is scheduled to be computed.This book contains the refereed proceedings of a DIMACS Workshop on Massively Parallel Computation, held in February 1994. The workshop brought together researchers from universities and laboratories, as well as practitioners involved in the design, implementation, and application of massively parallel systems. Focusing on interconnection networks of parallel architectures of today and of the near future, the book includes topics such as network topologies, network properties, message routing, network embeddings, network emulation, mappings, and efficient scheduling.

This book contains papers presented at the Workshop on Parallel Processing of Discrete Optimization Problems held at DIMACS in April 1994. The contents cover a wide spectrum of the most recent algorithms and applications in parallel processing of discrete optimization and related problems. Topics include parallel branch and bound algorithms, scalability, load balancing, parallelism and irregular data structures and scheduling task graphs on parallel machines. Applications include parallel algorithms for solving satisfiability problems, location problems, linear programming, quadratic and linear assignment problems. This book would be suitable as a textbook in advanced courses on parallel algorithms and combinatorial optimization.

This volume contains papers presented at the DIMACS workshop on Specification of Parallel Algorithms, held in May 1994 at Princeton University. The goal of the workshop was to bring together some of the best researchers in parallel languages, algorithms, and systems to present and discuss recent developments in their areas of expertise. Among the topics discussed were new specification techniques for concurrent and distributed systems, behavioral and operational specification techniques, new parallel language and system abstractions, novel concurrent architectures and systems, large-scale parallel systems, specification tools and environments, and proof techniques for concurrent systems.

This book is devoted to the lectures presented at the Sixth International Conference on Formal Power Series and Algebraic Combinatorics held at DIMACS in May 1994. The conference attracted approximately 180 graduate students and junior and senior researchers from all over the world. Generally speaking, algebraic combinatorics involves the use of techniques from algebra, algebraic topology, and algebraic geometry in solving combinatorial problems; or it involves using combinatorial methods to attack problems in these areas. Combinatorial problems amenable to algebraic methods can arise in these or other areas of mathematics, or in areas such as computer science, operations research, physics, chemistry, and, more recently, biology. Because of this interplay among many fields of mathematics and science, algebraic combinatorics is an area in which a wide variety of ideas and methods come together. The papers in this volume reflect the interesting aspects of this rich interaction.

This volume is the result of the Third DIMACS Implementation Challenge that was conducted as part of the 1993-1994 Special Year on Parallel Algorithms. The Implementation Challenge was formulated in order to provide a forum for a concerted effort to study effective algorithms for combinatorial problems and to investigate opportunities for massive speedups on parallel computers. The challenge included two problem areas for research study: tree searching algorithms, used in game search and combinatorial optimization, for example, and algorithms for sparse graphs. Participants at sites in the U.S. and Europe undertook projects from November 1993 through October 1994. The workshop was held at DIMACS in November 1994. Participants were encouraged to share test results, to rework their implementations considering feedback at the workshop, and to submit a final report for the proceedings. Nine papers were selected for this volume.

This book contains the proceedings of two workshops on computational aspects of geometric group theory. The workshops, held in the winter of 1994 at DIMACS and at the Geometry Center, covered practical group theoretic computation and theoretical problems. Containing both research and expository articles, this book is the only one available concentrating on the computational aspects of geometric group theory. Because this area involves an interplay between group theory, geometry, and automata theory, the expository articles in this book should help researchers in these fields to make connections to the other areas.

This book contains refereed papers presented at a remarkable interdisciplinary scientific meeting attended by a mix of leading biochemists and computer scientists held at DIMACS in March 1995. It describes the development of a variety of new methods which are being developed for attacking the important problem of molecular structure. This book focuses on global optimization algorithms and heuristics for molecular conformation and protein folding problems. It presents the most efficient recent algorithms. It covers a spectrum of algorithmic issues and applications.

The satisfiability (SAT) problem is central in mathematical logic, computing theory, and many industrial applications. There has been a strong relationship between the theory, the algorithms, and the applications of the SAT problem. This book aims to bring together work by the best theorists, algorithmists, and practitioners working on the SAT problem and on industrial applications, as well as to enhance the interaction between the three research groups. The book features the application of theoretical/algorithmic results to practical problems and presents practical problems for theoretical/algorithmic study.Major topics covered in the book include practical and industrial SAT problems and benchmarks, significant case studies and applications of the SAT problem and SAT algorithms, new algorithms and improved techniques for satisfiability testing, specific data structures and implementation details of the SAT algorithms, and the theoretical study of the SAT problem and SAT algorithms. It features: a comprehensive review of SAT research work over the past 25 years; the most recent research results; and a spectrum of algorithmic issues and applications.

The workshop 'Groups and Computations' took place at the Center for Discrete Mathematics and Theoretical Computer Science (DIMACS) at Rutgers University in June 1995. This and an earlier workshop (see Groups and Computation, Finkelstein and Kantor, c1993, American Mathematical Society) held in October 1991 was aimed at merging theory and practice within the broad area of computation with groups. The primary goal of the previous workshop was to foster a dialogue between researchers studying the computational complexity of group algorithms and those engaged in the development of practical software. It was expected that this would lead to a deeper understanding of the mathematical issues underlying group computation and that this understanding would lead, in turn, to faster algorithms.Comment and subsequent work indicated that this goal had been achieved beyond expectations. The second workshop was designed to reinforce the progress in these directions. The scientific program consisted of invited lectures and research announcements, as well as informal discussions and software demonstrations. The eight extended talks discussed randomization, permutation groups, matrix groups, software systems, fast Fourier transforms and their applications to signal processing and data analysis, computations with finitely presented groups, and implementation and complexity questions. As in the previous workshop, speakers ranged from established researchers to graduate students.

'We hope that this small volume will suggest directions of synergy and contact for future researchers to build upon, creating connections and making discoveries that will help explain some of the many mysteries of computation' - from the Preface. Finite model theory can be succinctly described as the study of logics on finite structures. It is an area of research existing between mathematical logic and computer science. This area has been developing through continuous interaction with computational complexity, database theory, and combinatorics. The volume presents articles by leading researchers who delivered talks at the 'Workshop on Finite Models and Descriptive Complexity' at Princeton in January 1996 during a DIMACS-sponsored Special Year on Logic and Algorithms. Each article is self-contained and provides a valuable introduction to the featured research areas connected with finite model theory.

Questions of mathematical proof and logical inference have been a significant thread in modern mathematics and have played a formative role in the development of computer science and artificial intelligence. Research in proof complexity and feasible theories of arithmetic aims at understanding not only whether logical inferences can be made, but also what resources are required to carry them out. Understanding the resources required for logical inferences has major implications for some of the most important problems in computational complexity, particularly the problem of whether NP is equal to co-NP. In addition, these have important implications for the efficiency of automated reasoning systems. The last dozen years have seen several breakthroughs in the study of these resource requirements.Papers in this volume represent the proceedings of the DIMACS workshop on 'Feasible Arithmetics and Proof Complexity' held in April 1996 at Rutgers University in New Jersey as part of the DIMACS Institute's Special Year on Logic and Algorithms. This book brings together some of the most recent work of leading researchers in proof complexity and feasible arithmetic reflecting many of these advances. It covers a number of aspects of the field, including lower bounds in proof complexity, witnessing theorems and proof systems for feasible arithmetic, algebraic and combinatorial proof systems, interpolation theorems, and the relationship between proof complexity and Boolean circuit complexity.

This volume contains selected papers from the DIMACS Workshop on Logic and Random Structures held in November 1995. The workshop was a major event of the DIMACS Special Year on Logic and Algorithms. The central theme was the relationship between logic and probabilistic techniques in the study of finite structures. In the last several years, this subject has developed into a very active area of mathematical logic with important connections to computer science. The DIMACS workshop was the first of its kind devoted to logic and random structures. Recent work of leaders in the field is contained in the volume, as well as new theoretical developments and applications to computer science.

This book presents surveys on the theory and practice of modeling, specifying, and validating concurrent systems. It contains surveys of techniques used in tools developed for automatic validation of systems. Other papers present recent developments in concurrency theory, logics of programs, model-checking, automata and formal languages theory. The volume contains the proceedings from the workshop, Partial Order Methods in Verification, which was held in Princeton, NJ, in July 1996. The workshop focused on both the practical and the theoretical aspects of using partial order models, including automata and formal languages, category theory, concurrency theory, logic, process algebra, program semantics, specification and verification, topology, and trace theory. The book also includes a lively e-mail debate that took place about the importance of the partial order dichotomy in modeling concurrency.

This volume contains research and expository papers by African-American mathematicians on issues related to their involvement in the mathematical sciences. Little is known, taught, or written about African-American mathematicians. Information is lacking on their past and present contributions and on the qualitative and quantitative nature of their existence in and distribution throughout mathematics. This lack of information leads to a number of questions that have to date remained unanswered. This volume provides details and pointers to help answer some of these questions. This title features: research articles by distinguished African-American mathematicians; accomplishments of African-American researchers in the mathematical sciences; and, articles that explore issues important to the African-American community and to the mathematics community as a whole. This book is an inspiration for African-American students who wish to pursue advancement in the mathematical sciences.

What is Spin? Spin is a general tool for the specification and formal verification of software for distributed systems. It has been used to detect design errors in a wide range of applications, such as abstract distributed algorithms, data communications protocols, operating systems code, and telephone switching code. The verifier can check for basic correctness properties, such as absence of deadlock and race conditions, logical completeness, or unwarranted assumptions about the relative speeds of correctness properties expressed in the syntax of Linear-time Temporal Logic (LTL). The tool translates LTL formulae automatically into automata representations, which can be used in an efficient on-the-fly verifications procedure.This DIMACS volume presents the papers contributed to the second international workshop that was held on the Spin verification system at Rutgers University in August 1996. The work covers theoretical and foundational studies of formal verification, empirical studies of the effectiveness of different types of algorithms, significant practical applications of the Spin verifier, and discussions of extensions and revisions of the basic code.

The fledgling field of DNA computers began in 1994 when Leonard Adleman surprised the scientific community by using DNA molecules, protein enzymes, and chemicals to solve an instance of a hard computational problem. This volume presents results from the second annual meeting on DNA computers held at Princeton only one and one-half years after Adleman's discovery. By drawing on the analogy between DNA computing and cutting-edge fields of biology (such as directed evolution), this volume highlights some of the exciting progress in the field and builds a strong foundation for the theory of molecular computation. DNA computing is a radically different approach to computing that brings together computer science and molecular biology in a way that is wholly distinct from other disciplines. This book outlines important advances in the field and offers comprehensive discussion on potential pitfalls and the general practicality of building DNA based computers.

The mathematical approach to the study of hierarchies presents the theoretical basis for many important areas of current scientific investigation. Biology has benefited from this research and has also stimulated the mathematical study of hierarchies. This collection presents papers devoted to theoretical, algorithmical, and application issues related to: reconstructing hierarchies (trees or ranking) from (dis)similarity or entity-to-character data; using hierarchies for modeling evolution and other processes; and, combining (gene) trees. The papers in this volume provide a contemporary sample of many new results in hierarchy theory with applications in biology, psychology, data analysis, and systems engineering.It's features include: mathematical treatment of hierarchies in several interconnected frameworks: set systems, linear subspaces, graph objects, and tree metrics; the relationship of hierarchies to many issues of current application-from learning robots to wavelets to intron evolution to the evolution of language; and, solutions to several important problems.

This volume features highlights from the DIMACS Special Year on 'Mathematical Support for Molecular Biology'. Top researchers presented both new research results and comprehensive overviews on the use of mathematics (especially discrete mathematics) and theoretical computer science in molecular biology. The book provides a unique 'snapshot' of this growing area of study. It will be of interest to both experts and novices seeking information on the state of the research.

These papers cover a variety of issues related to network switching, including network environment, routing, network topology, switching components, nonblockingness, and optimization.

This volume presents papers from a DIMACS workshop on network threats. The workshop brought together computer scientists (theorists and practitioners) working in this area to discuss topics such as network security, prevention and detection of security attacks, modeling threats, risk management, threats to individual privacy, and methods of security analysis. The book demonstrates the wide and diverse range of topics involved in electronic interactions and transactions-including the less desirable aspects: security breaches. The volume offers a timely assessment of avoiding or minimizing network threats. Presented here is an interdisciplinary, system-oriented approach that encompasses security requirements, specifications, protocols, and algorithms.The text includes implementation and development strategies using real-world applications that are reliable, fault-tolerant, and performance oriented. The book would be suitable for a graduate seminar on computer security. It features: discussion of Internet, Web and Java security; information on new attacks and weaknesses; and formal and informal analysis methods to identify, quantify, and combat security threats.

Connectivity and facilities location are two important topics in network design, with applications in data communication, transportation, production planning, and VLSI designs. There are two issues concerning these topics: design and optimization. They involve combinatorial design and combinatorial optimization. This volume features talks presented at an interdisciplinary research workshop held at DIMACS in April 1997. The workshop was attended by leading theorists, algorithmists, and practitioners working on network design problems. Finding the solution of design problems and the optimal or approximate solution of the related optimization problem are challenging tasks because no polynomial time algorithms are known.Such problems include some variations of Steiner tree problems (such as multiple-connected Steiner network, independent flow problem, and subset-interconnection designs), topology network design, nonlinear assignment problems (such as quadratic assignment problems), problems in facilities location and allocation, and network problems appearing in VLSI design. The focus of this book is on combinatorial, algorithmic, and applicational aspects of these problems. The volume would be suitable as a textbook for advanced courses in computer science, mathematics, engineering, and operations research.

This volume presents the proceedings from the third DIMACS workshop on ""DNA Based Computers"" held at the University of Pennsylvania (Philadelphia). The workshop was part of the Special Year on Molecular Biology and the Special Year on DNA Computing. The focus of this proceedings volume is on the multidisciplinary nature of the workshop with emphasis on the interaction between biology and biochemistry on one hand and computer science and mathematics on the other.

This volume is based on proceedings held during the DIMACS workshop on Randomization Methods in Algorithm Design in December 1997 at Princeton. The workshop was part of the DIMACS Special Year on Discrete Probability. It served as an interdisciplinary research workshop that brought together a mix of leading theorists, algorithmists and practitioners working in the theory and implementation aspects of algorithms involving randomization. Randomization has played an important role in the design of both sequential and parallel algorithms. The last decade has witnessed tremendous growth in the area of randomized algorithms. During this period, randomized algorithms went from being a tool in computational number theory to finding widespread applications in many problem domains.Major topics covered include randomization techniques for linear and integer programming problems, randomization in the design of approximate algorithms for combinatorial problems, randomization in parallel and distributed algorithms, practical implementation of randomized algorithms, de-randomization issues, and pseudo-random generators. This volume focuses on theory and implementation aspects of algorithms involving randomization. It would be suitable as a graduate or advanced graduate text.

Discrete mathematics stands among the leading disciplines of mathematics and theoretical computer science. This is due primarily to its increasing role in university curricula and its growing importance in applications ranging from optimization to molecular biology. An inaugural conference was held cooperatively by DIMATIA and DIMACS to focus on the versatility, width, and depth of current progress in the subject area. This volume offers a well-balanced blend of research and survey papers reflecting the exciting, attractive topics in contemporary discrete mathematics. Discussed in the book are topics such as graph theory, partially ordered sets, geometrical Ramsey theory, computational complexity issues and applications.

This volume presents the proceedings of a conference held at Princeton University in April 1995 as part of the DIMACS Special Year on Mathematical Support for Molecular Biology. The subject of the conference was the new area of DNA based computing. DNA based computing is the study of using DNA strands as individual computers. The concept was initiated by Leonard Adleman's paper in Science in November 1994.

This volume contains the proceedings from the first DIMACS meeting on discrete mathematical chemistry held at Rutgers University (New Brunswick, NJ). The contributions reflect the presentations and spotlight the breadth of current research on the topic - from the Benzenoid Clar problem to the Wulff-shape of sphere packings. Much of the volume reflects the combined mathematical and physical interest in the new molecules, fullerenes. This DIMACS conference highlighted the range of opportunities for fruitful and informed collaboration across the mathematics-chemistry boundaries. The interdisciplinary nature of the contributions pays testament to the fact that 'real' chemistry and 'real' mathematics do indeed interact.

This volume presents the proceedings from the DIMACS Workshop in Distributed Computing held at Rutgers University. It provides a broad survey of major topics concerning modern applications of networks in the context of distributed computing. Articles included touch upon fundamental problems and challenges related to recent technological advances in the networking industry which are directly relevant and interesting to research on the mathematical principles of distributed computing.Included are issues on diverse areas of networking such as ATM networking technology, issues on routing and flow control in communications networks, security, optical networking and mobile computing. This volume provides state-of-the-art research in these significant areas. The material should acquaint the theoretical community of distributed computing with related issues and problems. Treatment is applied and tailored to industrial advances in networking, however the underlying material presents a rich variety of theoretical problems in distributed computing that carry significant interest and challenge for the modern mathematician.

Time division multiplexing (TDM) has been the fundamental basis for adding capacity to digital telecommunications networks for decades. However, within the past two years, wavelength division multiplexing (WDM) has been emerging as an important and widely deployed complement to TDM. Sales of systems based on the new technology have risen at breathtaking speed. The driving force behind this sales explosion was the unexpected rapid exhaustion of long distance fiber network capacity. This fiber exhaust, combined with favorable economics for WDM, led to the use of this technology over other alternatives. The WDM deployment raises fundamental and challenging problems that require novel and innovative solutions.This volume presents papers from an interdisciplinary workshop held at DIMACS on multichannel optical networks. Leading computer science theorists and practitioners discussed admissions control, routing and channel assignment, multicasting and protection, and fault-tolerance. The book features application of theoretical and/or algorithmical results to practical problems and addresses the influence of practical problems to theoretical/algorithmic studies. The volume can serve as a text for an advanced course in computer science, networking, and operations research.

We are especially proud to announce the publication of this ""DIMACS"" book - the 50th volume in this series, published by the AMS. The series was established out of a collaborative venture geared to unite the cutting-edge research at DIMACS with the resources at the AMS to produce useful, well-designed, important mathematical and computational sciences works. This volume is a hallmark in this firmly grounded and well-received AMS series. The AMS' 50th ""DIMACS"" volume is also particularly notable at this time: The year 1999 marks the 10th anniversary of the founding of DIMACS as a center. Participants in the DIMACS national research project are Rutgers University, Princeton University, AT&T Labs-Research, Bell Labs (Lucent Technologies), Telcordia Technologies, and NEC Research Institute.The success of the joint publishing venture between the AMS and DIMACS is excellent. We continue to work concordantly with the Center to further their goal of playing a key national leadership role in the development, application, and dissemination of discrete mathematics and theoretical computer science. This 50th ""DIMACS"" volume is in celebration of that dynamic, ongoing partnership. About the book: special techniques from computer science and mathematics are used to solve combinatorial problems whose associated data require a hierarchy of storage devices. These solutions employ 'extended memory algorithms'. The input/output (I/O) communication between the levels of the hierarchy is often a significant bottleneck, especially in applications that process massive amounts of data. Gains in performance are possible by incorporating locality directly into the algorithms and managing the contents of each storage level.The relative difference in data access speeds is more apparent between random access memory and magnetic disks. Therefore, much research has been devoted to algorithms that focus on this I/O bottleneck. These algorithms are usually called 'external memory', 'out-of-core', or 'I/O algorithms'.This volume presents new research results and current techniques for the design and analysis of external memory algorithms. The articles grew out of the workshop, 'External Memory Algorithms and Visualization' held at DIMACS. Leading researchers were invited to give lectures and to contribute their work. The topics presented include problems in computational geometry, graph theory, data compression, disk scheduling, linear algebra, statistics, software libraries, text and string processing, visualization, wavelets, and industrial applications. The vitality of the research and the interdisciplinary nature of the event produced fruitful ground for the compelling fusion of ideas and methods. This volume comprises the rich results that grew out of that process.

The interconnection network is one of the most basic components of a massively parallel computer system. Such systems consist of hundreds or thousands of processors interconnected to work cooperatively on computations. One of the central problems in parallel computing is the task of mapping a collection of processes onto the processors and routing network of a parallel machine. Once this mapping is done, it is critical to schedule computations within and communication among processors so that the necessary inputs for a process are available where and when the process is scheduled to be computed.This book contains the refereed proceedings of a DIMACS Workshop on Massively Parallel Computation, held in February 1994. The workshop brought together researchers from universities and laboratories, as well as practitioners involved in the design, implementation, and application of massively parallel systems. Focusing on interconnection networks of parallel architectures of today and of the near future, the book includes topics such as network topologies, network properties, message routing, network embeddings, network emulation, mappings, and efficient scheduling.

This book contains papers presented at the Workshop on Parallel Processing of Discrete Optimization Problems held at DIMACS in April 1994. The contents cover a wide spectrum of the most recent algorithms and applications in parallel processing of discrete optimization and related problems. Topics include parallel branch and bound algorithms, scalability, load balancing, parallelism and irregular data structures and scheduling task graphs on parallel machines. Applications include parallel algorithms for solving satisfiability problems, location problems, linear programming, quadratic and linear assignment problems. This book would be suitable as a textbook in advanced courses on parallel algorithms and combinatorial optimization.

This volume contains papers presented at the DIMACS workshop on Specification of Parallel Algorithms, held in May 1994 at Princeton University. The goal of the workshop was to bring together some of the best researchers in parallel languages, algorithms, and systems to present and discuss recent developments in their areas of expertise. Among the topics discussed were new specification techniques for concurrent and distributed systems, behavioral and operational specification techniques, new parallel language and system abstractions, novel concurrent architectures and systems, large-scale parallel systems, specification tools and environments, and proof techniques for concurrent systems.

This book is devoted to the lectures presented at the Sixth International Conference on Formal Power Series and Algebraic Combinatorics held at DIMACS in May 1994. The conference attracted approximately 180 graduate students and junior and senior researchers from all over the world. Generally speaking, algebraic combinatorics involves the use of techniques from algebra, algebraic topology, and algebraic geometry in solving combinatorial problems; or it involves using combinatorial methods to attack problems in these areas. Combinatorial problems amenable to algebraic methods can arise in these or other areas of mathematics, or in areas such as computer science, operations research, physics, chemistry, and, more recently, biology. Because of this interplay among many fields of mathematics and science, algebraic combinatorics is an area in which a wide variety of ideas and methods come together. The papers in this volume reflect the interesting aspects of this rich interaction.

This volume is the result of the Third DIMACS Implementation Challenge that was conducted as part of the 1993-1994 Special Year on Parallel Algorithms. The Implementation Challenge was formulated in order to provide a forum for a concerted effort to study effective algorithms for combinatorial problems and to investigate opportunities for massive speedups on parallel computers. The challenge included two problem areas for research study: tree searching algorithms, used in game search and combinatorial optimization, for example, and algorithms for sparse graphs. Participants at sites in the U.S. and Europe undertook projects from November 1993 through October 1994. The workshop was held at DIMACS in November 1994. Participants were encouraged to share test results, to rework their implementations considering feedback at the workshop, and to submit a final report for the proceedings. Nine papers were selected for this volume.

This book contains the proceedings of two workshops on computational aspects of geometric group theory. The workshops, held in the winter of 1994 at DIMACS and at the Geometry Center, covered practical group theoretic computation and theoretical problems. Containing both research and expository articles, this book is the only one available concentrating on the computational aspects of geometric group theory. Because this area involves an interplay between group theory, geometry, and automata theory, the expository articles in this book should help researchers in these fields to make connections to the other areas.

This book contains refereed papers presented at a remarkable interdisciplinary scientific meeting attended by a mix of leading biochemists and computer scientists held at DIMACS in March 1995. It describes the development of a variety of new methods which are being developed for attacking the important problem of molecular structure. This book focuses on global optimization algorithms and heuristics for molecular conformation and protein folding problems. It presents the most efficient recent algorithms. It covers a spectrum of algorithmic issues and applications.

The satisfiability (SAT) problem is central in mathematical logic, computing theory, and many industrial applications. There has been a strong relationship between the theory, the algorithms, and the applications of the SAT problem. This book aims to bring together work by the best theorists, algorithmists, and practitioners working on the SAT problem and on industrial applications, as well as to enhance the interaction between the three research groups. The book features the application of theoretical/algorithmic results to practical problems and presents practical problems for theoretical/algorithmic study.Major topics covered in the book include practical and industrial SAT problems and benchmarks, significant case studies and applications of the SAT problem and SAT algorithms, new algorithms and improved techniques for satisfiability testing, specific data structures and implementation details of the SAT algorithms, and the theoretical study of the SAT problem and SAT algorithms. It features: a comprehensive review of SAT research work over the past 25 years; the most recent research results; and a spectrum of algorithmic issues and applications.

The workshop 'Groups and Computations' took place at the Center for Discrete Mathematics and Theoretical Computer Science (DIMACS) at Rutgers University in June 1995. This and an earlier workshop (see Groups and Computation, Finkelstein and Kantor, c1993, American Mathematical Society) held in October 1991 was aimed at merging theory and practice within the broad area of computation with groups. The primary goal of the previous workshop was to foster a dialogue between researchers studying the computational complexity of group algorithms and those engaged in the development of practical software. It was expected that this would lead to a deeper understanding of the mathematical issues underlying group computation and that this understanding would lead, in turn, to faster algorithms.Comment and subsequent work indicated that this goal had been achieved beyond expectations. The second workshop was designed to reinforce the progress in these directions. The scientific program consisted of invited lectures and research announcements, as well as informal discussions and software demonstrations. The eight extended talks discussed randomization, permutation groups, matrix groups, software systems, fast Fourier transforms and their applications to signal processing and data analysis, computations with finitely presented groups, and implementation and complexity questions. As in the previous workshop, speakers ranged from established researchers to graduate students.

'We hope that this small volume will suggest directions of synergy and contact for future researchers to build upon, creating connections and making discoveries that will help explain some of the many mysteries of computation' - from the Preface. Finite model theory can be succinctly described as the study of logics on finite structures. It is an area of research existing between mathematical logic and computer science. This area has been developing through continuous interaction with computational complexity, database theory, and combinatorics. The volume presents articles by leading researchers who delivered talks at the 'Workshop on Finite Models and Descriptive Complexity' at Princeton in January 1996 during a DIMACS-sponsored Special Year on Logic and Algorithms. Each article is self-contained and provides a valuable introduction to the featured research areas connected with finite model theory.

Questions of mathematical proof and logical inference have been a significant thread in modern mathematics and have played a formative role in the development of computer science and artificial intelligence. Research in proof complexity and feasible theories of arithmetic aims at understanding not only whether logical inferences can be made, but also what resources are required to carry them out. Understanding the resources required for logical inferences has major implications for some of the most important problems in computational complexity, particularly the problem of whether NP is equal to co-NP. In addition, these have important implications for the efficiency of automated reasoning systems. The last dozen years have seen several breakthroughs in the study of these resource requirements.Papers in this volume represent the proceedings of the DIMACS workshop on 'Feasible Arithmetics and Proof Complexity' held in April 1996 at Rutgers University in New Jersey as part of the DIMACS Institute's Special Year on Logic and Algorithms. This book brings together some of the most recent work of leading researchers in proof complexity and feasible arithmetic reflecting many of these advances. It covers a number of aspects of the field, including lower bounds in proof complexity, witnessing theorems and proof systems for feasible arithmetic, algebraic and combinatorial proof systems, interpolation theorems, and the relationship between proof complexity and Boolean circuit complexity.

This volume contains selected papers from the DIMACS Workshop on Logic and Random Structures held in November 1995. The workshop was a major event of the DIMACS Special Year on Logic and Algorithms. The central theme was the relationship between logic and probabilistic techniques in the study of finite structures. In the last several years, this subject has developed into a very active area of mathematical logic with important connections to computer science. The DIMACS workshop was the first of its kind devoted to logic and random structures. Recent work of leaders in the field is contained in the volume, as well as new theoretical developments and applications to computer science.

This book presents surveys on the theory and practice of modeling, specifying, and validating concurrent systems. It contains surveys of techniques used in tools developed for automatic validation of systems. Other papers present recent developments in concurrency theory, logics of programs, model-checking, automata and formal languages theory. The volume contains the proceedings from the workshop, Partial Order Methods in Verification, which was held in Princeton, NJ, in July 1996. The workshop focused on both the practical and the theoretical aspects of using partial order models, including automata and formal languages, category theory, concurrency theory, logic, process algebra, program semantics, specification and verification, topology, and trace theory. The book also includes a lively e-mail debate that took place about the importance of the partial order dichotomy in modeling concurrency.

This volume contains research and expository papers by African-American mathematicians on issues related to their involvement in the mathematical sciences. Little is known, taught, or written about African-American mathematicians. Information is lacking on their past and present contributions and on the qualitative and quantitative nature of their existence in and distribution throughout mathematics. This lack of information leads to a number of questions that have to date remained unanswered. This volume provides details and pointers to help answer some of these questions. This title features: research articles by distinguished African-American mathematicians; accomplishments of African-American researchers in the mathematical sciences; and, articles that explore issues important to the African-American community and to the mathematics community as a whole. This book is an inspiration for African-American students who wish to pursue advancement in the mathematical sciences.

What is Spin? Spin is a general tool for the specification and formal verification of software for distributed systems. It has been used to detect design errors in a wide range of applications, such as abstract distributed algorithms, data communications protocols, operating systems code, and telephone switching code. The verifier can check for basic correctness properties, such as absence of deadlock and race conditions, logical completeness, or unwarranted assumptions about the relative speeds of correctness properties expressed in the syntax of Linear-time Temporal Logic (LTL). The tool translates LTL formulae automatically into automata representations, which can be used in an efficient on-the-fly verifications procedure.This DIMACS volume presents the papers contributed to the second international workshop that was held on the Spin verification system at Rutgers University in August 1996. The work covers theoretical and foundational studies of formal verification, empirical studies of the effectiveness of different types of algorithms, significant practical applications of the Spin verifier, and discussions of extensions and revisions of the basic code.

The fledgling field of DNA computers began in 1994 when Leonard Adleman surprised the scientific community by using DNA molecules, protein enzymes, and chemicals to solve an instance of a hard computational problem. This volume presents results from the second annual meeting on DNA computers held at Princeton only one and one-half years after Adleman's discovery. By drawing on the analogy between DNA computing and cutting-edge fields of biology (such as directed evolution), this volume highlights some of the exciting progress in the field and builds a strong foundation for the theory of molecular computation. DNA computing is a radically different approach to computing that brings together computer science and molecular biology in a way that is wholly distinct from other disciplines. This book outlines important advances in the field and offers comprehensive discussion on potential pitfalls and the general practicality of building DNA based computers.

The mathematical approach to the study of hierarchies presents the theoretical basis for many important areas of current scientific investigation. Biology has benefited from this research and has also stimulated the mathematical study of hierarchies. This collection presents papers devoted to theoretical, algorithmical, and application issues related to: reconstructing hierarchies (trees or ranking) from (dis)similarity or entity-to-character data; using hierarchies for modeling evolution and other processes; and, combining (gene) trees. The papers in this volume provide a contemporary sample of many new results in hierarchy theory with applications in biology, psychology, data analysis, and systems engineering.It's features include: mathematical treatment of hierarchies in several interconnected frameworks: set systems, linear subspaces, graph objects, and tree metrics; the relationship of hierarchies to many issues of current application-from learning robots to wavelets to intron evolution to the evolution of language; and, solutions to several important problems.

This volume features highlights from the DIMACS Special Year on 'Mathematical Support for Molecular Biology'. Top researchers presented both new research results and comprehensive overviews on the use of mathematics (especially discrete mathematics) and theoretical computer science in molecular biology. The book provides a unique 'snapshot' of this growing area of study. It will be of interest to both experts and novices seeking information on the state of the research.

These papers cover a variety of issues related to network switching, including network environment, routing, network topology, switching components, nonblockingness, and optimization.

This volume presents papers from a DIMACS workshop on network threats. The workshop brought together computer scientists (theorists and practitioners) working in this area to discuss topics such as network security, prevention and detection of security attacks, modeling threats, risk management, threats to individual privacy, and methods of security analysis. The book demonstrates the wide and diverse range of topics involved in electronic interactions and transactions-including the less desirable aspects: security breaches. The volume offers a timely assessment of avoiding or minimizing network threats. Presented here is an interdisciplinary, system-oriented approach that encompasses security requirements, specifications, protocols, and algorithms.The text includes implementation and development strategies using real-world applications that are reliable, fault-tolerant, and performance oriented. The book would be suitable for a graduate seminar on computer security. It features: discussion of Internet, Web and Java security; information on new attacks and weaknesses; and formal and informal analysis methods to identify, quantify, and combat security threats.

Connectivity and facilities location are two important topics in network design, with applications in data communication, transportation, production planning, and VLSI designs. There are two issues concerning these topics: design and optimization. They involve combinatorial design and combinatorial optimization. This volume features talks presented at an interdisciplinary research workshop held at DIMACS in April 1997. The workshop was attended by leading theorists, algorithmists, and practitioners working on network design problems. Finding the solution of design problems and the optimal or approximate solution of the related optimization problem are challenging tasks because no polynomial time algorithms are known.Such problems include some variations of Steiner tree problems (such as multiple-connected Steiner network, independent flow problem, and subset-interconnection designs), topology network design, nonlinear assignment problems (such as quadratic assignment problems), problems in facilities location and allocation, and network problems appearing in VLSI design. The focus of this book is on combinatorial, algorithmic, and applicational aspects of these problems. The volume would be suitable as a textbook for advanced courses in computer science, mathematics, engineering, and operations research.

This volume presents the proceedings from the third DIMACS workshop on ""DNA Based Computers"" held at the University of Pennsylvania (Philadelphia). The workshop was part of the Special Year on Molecular Biology and the Special Year on DNA Computing. The focus of this proceedings volume is on the multidisciplinary nature of the workshop with emphasis on the interaction between biology and biochemistry on one hand and computer science and mathematics on the other.

This volume is based on proceedings held during the DIMACS workshop on Randomization Methods in Algorithm Design in December 1997 at Princeton. The workshop was part of the DIMACS Special Year on Discrete Probability. It served as an interdisciplinary research workshop that brought together a mix of leading theorists, algorithmists and practitioners working in the theory and implementation aspects of algorithms involving randomization. Randomization has played an important role in the design of both sequential and parallel algorithms. The last decade has witnessed tremendous growth in the area of randomized algorithms. During this period, randomized algorithms went from being a tool in computational number theory to finding widespread applications in many problem domains.Major topics covered include randomization techniques for linear and integer programming problems, randomization in the design of approximate algorithms for combinatorial problems, randomization in parallel and distributed algorithms, practical implementation of randomized algorithms, de-randomization issues, and pseudo-random generators. This volume focuses on theory and implementation aspects of algorithms involving randomization. It would be suitable as a graduate or advanced graduate text.

Discrete mathematics stands among the leading disciplines of mathematics and theoretical computer science. This is due primarily to its increasing role in university curricula and its growing importance in applications ranging from optimization to molecular biology. An inaugural conference was held cooperatively by DIMATIA and DIMACS to focus on the versatility, width, and depth of current progress in the subject area. This volume offers a well-balanced blend of research and survey papers reflecting the exciting, attractive topics in contemporary discrete mathematics. Discussed in the book are topics such as graph theory, partially ordered sets, geometrical Ramsey theory, computational complexity issues and applications.

This volume presents the proceedings of a conference held at Princeton University in April 1995 as part of the DIMACS Special Year on Mathematical Support for Molecular Biology. The subject of the conference was the new area of DNA based computing. DNA based computing is the study of using DNA strands as individual computers. The concept was initiated by Leonard Adleman's paper in Science in November 1994.

This volume contains the proceedings from the first DIMACS meeting on discrete mathematical chemistry held at Rutgers University (New Brunswick, NJ). The contributions reflect the presentations and spotlight the breadth of current research on the topic - from the Benzenoid Clar problem to the Wulff-shape of sphere packings. Much of the volume reflects the combined mathematical and physical interest in the new molecules, fullerenes. This DIMACS conference highlighted the range of opportunities for fruitful and informed collaboration across the mathematics-chemistry boundaries. The interdisciplinary nature of the contributions pays testament to the fact that 'real' chemistry and 'real' mathematics do indeed interact.

This volume presents the proceedings from the DIMACS Workshop in Distributed Computing held at Rutgers University. It provides a broad survey of major topics concerning modern applications of networks in the context of distributed computing. Articles included touch upon fundamental problems and challenges related to recent technological advances in the networking industry which are directly relevant and interesting to research on the mathematical principles of distributed computing.Included are issues on diverse areas of networking such as ATM networking technology, issues on routing and flow control in communications networks, security, optical networking and mobile computing. This volume provides state-of-the-art research in these significant areas. The material should acquaint the theoretical community of distributed computing with related issues and problems. Treatment is applied and tailored to industrial advances in networking, however the underlying material presents a rich variety of theoretical problems in distributed computing that carry significant interest and challenge for the modern mathematician.

Time division multiplexing (TDM) has been the fundamental basis for adding capacity to digital telecommunications networks for decades. However, within the past two years, wavelength division multiplexing (WDM) has been emerging as an important and widely deployed complement to TDM. Sales of systems based on the new technology have risen at breathtaking speed. The driving force behind this sales explosion was the unexpected rapid exhaustion of long distance fiber network capacity. This fiber exhaust, combined with favorable economics for WDM, led to the use of this technology over other alternatives. The WDM deployment raises fundamental and challenging problems that require novel and innovative solutions.This volume presents papers from an interdisciplinary workshop held at DIMACS on multichannel optical networks. Leading computer science theorists and practitioners discussed admissions control, routing and channel assignment, multicasting and protection, and fault-tolerance. The book features application of theoretical and/or algorithmical results to practical problems and addresses the influence of practical problems to theoretical/algorithmic studies. The volume can serve as a text for an advanced course in computer science, networking, and operations research.

We are especially proud to announce the publication of this ""DIMACS"" book - the 50th volume in this series, published by the AMS. The series was established out of a collaborative venture geared to unite the cutting-edge research at DIMACS with the resources at the AMS to produce useful, well-designed, important mathematical and computational sciences works. This volume is a hallmark in this firmly grounded and well-received AMS series. The AMS' 50th ""DIMACS"" volume is also particularly notable at this time: The year 1999 marks the 10th anniversary of the founding of DIMACS as a center. Participants in the DIMACS national research project are Rutgers University, Princeton University, AT&T Labs-Research, Bell Labs (Lucent Technologies), Telcordia Technologies, and NEC Research Institute.The success of the joint publishing venture between the AMS and DIMACS is excellent. We continue to work concordantly with the Center to further their goal of playing a key national leadership role in the development, application, and dissemination of discrete mathematics and theoretical computer science. This 50th ""DIMACS"" volume is in celebration of that dynamic, ongoing partnership. About the book: special techniques from computer science and mathematics are used to solve combinatorial problems whose associated data require a hierarchy of storage devices. These solutions employ 'extended memory algorithms'. The input/output (I/O) communication between the levels of the hierarchy is often a significant bottleneck, especially in applications that process massive amounts of data. Gains in performance are possible by incorporating locality directly into the algorithms and managing the contents of each storage level.The relative difference in data access speeds is more apparent between random access memory and magnetic disks. Therefore, much research has been devoted to algorithms that focus on this I/O bottleneck. These algorithms are usually called 'external memory', 'out-of-core', or 'I/O algorithms'.This volume presents new research results and current techniques for the design and analysis of external memory algorithms. The articles grew out of the workshop, 'External Memory Algorithms and Visualization' held at DIMACS. Leading researchers were invited to give lectures and to contribute their work. The topics presented include problems in computational geometry, graph theory, data compression, disk scheduling, linear algebra, statistics, software libraries, text and string processing, visualization, wavelets, and industrial applications. The vitality of the research and the interdisciplinary nature of the event produced fruitful ground for the compelling fusion of ideas and methods. This volume comprises the rich results that grew out of that process.