Search

This book is about relations between three different areas of mathematics and theoretical computer science: combinatorial group theory, cryptography, and complexity theory. It is explored how non-commutative (infinite) groups, which are typically studied in combinatorial group theory, can be used in public key cryptography. It is also shown that there is a remarkable feedback from cryptography to combinatorial group theory because some of the problems motivated by cryptography appear to be new to group theory, and they open many interesting research avenues within group theory. Then, complexity theory, notably generic-case complexity of algorithms, is employed for cryptanalysis of various cryptographic protocols based on infinite groups, and the ideas and machinery from the theory of generic-case complexity are used to study asymptotically dominant properties of some infinite groups that have been applied in public key cryptography so far. Its elementary exposition makes the book accessible to graduate as well as undergraduate students in mathematics or computer science.

We are currently witnessing a proliferation in parallel and distributed processing technologies and applications. However, more new technologies have ushered in unprecented challenges to the research community across the range of high-performance computing, multi-core microprocessor architecture, networks and pervasive computing, as well as new paradigm computing issues. APPT 2007 was sponsored by the China Computer Federation, in cooperation with TCPP of the Institute for Electrical and Electronics Engineers (IEEE). The highly positive responses to the previous APPT workshops encouraged us to continue this international event. This year, APPT was upgraded to the International Symposium on Advanced Parallel Processing Technologies. However, it kept its traditional flavor by sharing of the underlying theories and applications, and the establishment of new and long-term collaborative channels. And it will continue to provide a forum for researchers, professionals, and industrial practitioners from around the world to report on new advances in high-performance architecture and software, as well as to identify issues and directions for research and development in the new era of evolving technologies. The success of APPT 2007 was a result of the hard work and planning of a large group of renowned researchers from around the world, who served on the Technical Program Committee and the Organizing Committee. Their invaluable efforts in developing this technical program are most gratefully acknowledged. In particular, we would like to thank the Program Co-chairs, Xin Chen, Xuejun Yang, and Albert Y. Zomaya.

Experimental algorithmics, as its name indicates, combines algorithmic work and experimentation: algorithms are not just designed, but also implemented and tested on a variety of instances. Perhaps the most important lesson in this process is that designing an algorithm is but the first step in the process of developing robust and efficient software for applications. Based on a seminar held at Dagstuhl Castle, Germany in September 2000, this state-of-the-art survey presents a coherent survey of the work done in the area so far. The 11 carefully reviewed chapters provide complete coverage of all current topics in experimental algorithmics.

Although this may seem a paradox, all exact science is dominated by the idea of approximation. Bertrand Russell (1872-1970) Most natural optimization problems, including those arising in important application areas, are NP-hard. Therefore, under the widely believed con­ jecture that P -=/= NP, their exact solution is prohibitively time consuming. Charting the landscape of approximability of these problems, via polynomial time algorithms, therefore becomes a compelling subject of scientific inquiry in computer science and mathematics. This book presents the theory of ap­ proximation algorithms as it stands today. It is reasonable to expect the picture to change with time. This book is divided into three parts. In Part I we cover combinato­ rial algorithms for a number of important problems, using a wide variety of algorithm design techniques. The latter may give Part I a non-cohesive appearance. However, this is to be expected - nature is very rich, and we cannot expect a few tricks to help solve the diverse collection of NP-hard problems. Indeed, in this part, we have purposely refrained from tightly cat­ egorizing algorithmic techniques so as not to trivialize matters. Instead, we have attempted to capture, as accurately as possible, the individual character of each problem, and point out connections between problems and algorithms for solving them.