Aspects of Complexity: Minicourses in Algorithmics, Complexity and Computational Algebra. Mathematics Workshop, Kaikoura, January 7-15, 2000

✍ Scribed by Rod Downey (editor); Denis R. Hirschfeldt (editor)

Publisher: De Gruyter
Year: 2001
Tongue: English
Leaves: 180
Series: De Gruyter Series in Logic and Its Applications; 4
Edition: Reprint 2010
Category: Library

No coin nor oath required. For personal study only.

✦ Synopsis

The book contains 8 detailed expositions of the lectures given at the Kaikoura 2000 Workshop on Computability, Complexity, and Computational Algebra.

Topics covered include basic models and questions of complexity theory, the Blum-Shub-Smale model of computation, probability theory applied to algorithmics (randomized alogrithms), parametric complexity, Kolmogorov complexity of finite strings, computational group theory, counting problems, and canonical models of ZFC providing a solution to continuum hypothesis.

The text addresses students in computer science or mathematics, and professionals in these areas who seek a complete, but gentle introduction to a wide range of techniques, concepts, and research horizons in the area of computational complexity in a broad sense.

✦ Table of Contents

Preface
Basic complexity
Three lectures on real computation
Parameterized complexity: new developments and research frontiers
Kolmogorov complexity
Complexity and computation in matrix groups
The complexity of counting problems
The Ω conjecture
List of contributors

📜 SIMILAR VOLUMES

Aspects of Complexity: Minicourses in Al

📁 Aspects of Complexity: Minicourses in Algorithmics, Complexity and Computational Algebra, Mathematics Workshop, Kaikoura, January 7-15, 2000

✍ Rod Downey, Denis Hirschfeld 📂 Library 📅 2001 🏛 Walter De Gruyter 🌐 English

This text contains 8 detailed expositions of the lectures given at the Kaikoura 2000 Workshop on Computability, Complexity, and Computational Algebra. Topics covered include basic models and questions of complexity theory, the Blum-Shub-Smale model of computation, probability theory applied to algor

Aspects of Complexity: Minicourses in Al

📁 Aspects of Complexity: Minicourses in Algorithmics, Complexity and Computational Algebra, Mathematics Workshop, Kaikoura, January 7-15, 2000

✍ Rod Downey, Denis Hirschfeld 📂 Library 📅 2001 🏛 Walter De Gruyter Inc 🌐 English

Algebraic Aspects of Cryptography (Algor

📁 Algebraic Aspects of Cryptography (Algorithms and Computation in Mathematics)

✍ Neal Koblitz 📂 Library 📅 2004 🏛 Springer 🌐 English

From the reviews: "This is a textbook in cryptography with emphasis on algebraic methods. It is supported by many exercises (with answers) making it appropriate for a course in mathematics or computer science. [...] Overall, this is an excellent expository text, and will be very useful to both the s

Completeness and Reduction in Algebraic

📁 Completeness and Reduction in Algebraic Complexity Theory

✍ Peter Bürgisser (auth.) 📂 Library 📅 2000 🏛 Springer-Verlag Berlin Heidelberg 🌐 English

<p>One of the most important and successful theories in computational complex ity is that of NP-completeness. This discrete theory is based on the Turing machine model and achieves a classification of discrete computational prob lems according to their algorithmic difficulty. Turing machines forma

Randomness and Completeness in Computati

📁 Randomness and Completeness in Computational Complexity

✍ Dieter van Melkebeek (auth.) 📂 Library 📅 2000 🏛 Springer-Verlag Berlin Heidelberg 🌐 English

<p>This book contains a revised version of the dissertation the author wrote at the Department of Computer Science of the University of Chicago. The thesis was submitted to the Faculty of Physical Sciences in conformity with the requirements for the PhD degree in June 1999. It was honored with the 1

Randomness and Completeness in Computati

📁 Randomness and Completeness in Computational Complexity

✍ Dieter van Melkebeek (auth.) 📂 Library 📅 2000 🏛 Springer-Verlag Berlin Heidelberg 🌐 English