Hardback (ISBN-13: 9780521884730)
Page extent: 500 pages
Size: 253 x 177 mm
Complexity theory is a central field of the theoretical foundations of computer science. It is concerned with the general study of the intrinsic complexity of computational tasks; that is, it addresses the question of what can be achieved within limited time (and/or with other limited natural computational resources). This book offers a conceptual perspective on complexity theory. It is intended to serve as an introduction for advanced undergraduate and graduate students, either as a textbook or for self-study. The book will also be useful to experts, since it provides expositions of the various sub-areas of complexity theory such as hardness amplification, pseudorandomness and probabilistic proof systems. In each case, the author starts by posing the intuitive questions that are addressed by the sub-area and then discusses the choices made in the actual formulation of these questions, the approaches that lead to the answers, and the ideas that are embedded in these answers.
* Presents a conceptual perspective, meaning the text evolves around the
underlying intuitive questions on the subject * The focus is on motivation
and ideas * Organized around conceptual themes
Contents
1. Introduction and preliminaries; 2. P, NP and NP-completeness; 3. Variations
on P and NP; 4. More resources, more power*; 5. Space complexity; 6. Randomness
and counting; 7. The bright side of hardness; 8. Pseudorandom generators;
9. Probabalistic proof systems; 10. Relaxing the requirements; Epilogue;
A. Glossary of complexity classes; B. On the quest for lower bounds; C.
On the foundations of modern cryptography; D. Probabalistic preliminaries
and advanced topics in randomization; E. Explicit constructions; F. Some
omitted proofs; G. Some computational problems.
Series: Cambridge Tracts in Mathematics (No. 175)
Hardback (ISBN-13: 9780521888516)
10 line diagrams 9 tables
14 exercises 5 figures 13 worked examples
Page extent: 280 pages
Size: 228 x 152 mm
Among the modern methods used to study prime numbers, the esievef has been one of the most efficient. Originally conceived by Linnik in 1941, the elarge sievef has developed extensively since the 1960s, with a recent realisation that the underlying principles were capable of applications going well beyond prime number theory. This book develops a general form of sieve inequality, and describes its varied applications, including the study of families of zeta functions of algebraic curves over finite fields; arithmetic properties of characteristic polynomials of random unimodular matrices; homological properties of random 3-manifolds; and the average number of primes dividing the denominators of rational points on elliptic curves. Also covered in detail are the tools of harmonic analysis used to implement the forms of the large sieve inequality, including the Riemann Hypothesis over finite fields, and Property (T) or Property (tau) for discrete groups.
* Explores new and surprising applications of the large sieve method, an
important technique of analytic number theory * Presents applications in
fields as wide ranging as topology, probability, arithmetic geometry and
discrete group theory * Motivated, clear and self-contained discussions
introduce readers to a technique previously confined to one field
Contents
Preface; Prerequisites and notation; 1. Introduction; 2. The principle of the large sieve; 3. Group and conjugacy sieves; 4. Elementary and classical examples; 5. Degrees of representations of finite groups; 6. Probabilistic sieves; 7. Sieving in discrete groups; 8. Sieving for Frobenius over finite fields; Appendix A. Small sieves; Appendix B. Local density computations over finite fields; Appendix C. Representation theory; Appendix D. Property (T) and Property (Ñ); Appendix E. Linear algebraic groups; Appendix F. Probability theory and random walks; Appendix G. Sums of multiplicative functions; Appendix H. Topology; Bibliography; Index.
Series: Cambridge Studies in Advanced Mathematics (No. 60)
Paperback (ISBN-13: 9780521047586)
6 line diagrams
Page extent: 432 pages
Size: 228 x 152 mm
Weight: 0.658 kg
This book provides a careful and detailed algebraic introduction to Grothendieckfs
local cohomology theory, and provides many illustrations of applications
of the theory in commutative algebra and in the geometry of quasi-affine
and quasi-projective varieties. Topics covered include Castelnuovo*Mumford
regularity, the Fulton*Hansen connectedness theorem for projective varieties,
and connections between local cohomology and both reductions of ideals
and sheaf cohomology. It is designed for graduate students who have some
experience of basic commutative algebra and homological algebra, and also
for experts in commutative algebra and algebraic geometry.
* Gives a detailed and comprehensive account of this material * Covers
important applications * Uses detailed examples designed to illustrate
the geometrical significance of aspects of local cohomology
Contents
Preface; Notation and conventions; 1. The local cohomology functors; 2.
Torsion modules and ideal transforms; 3. The Mayer*Vietoris Sequence; 4.
Change of rings; 5. Other approaches; 6. Fundamental vanishing theorems;
7. Artinian local cohomology modules; 8. The Lichtenbaum*Hartshorne theorem;
9. The Annihilator and Finiteness Theorems; 10. Matlis duality; 11. Local
duality; 12. Foundations in the graded case; 13. Graded versions of basic
theorems; 14. Links with projective varieties; 15. Castelnuovo regularity;
16. Bounds of diagonal type; 17. Hilbert polynomials; 18. Applications
to reductions of ideals; 19. Connectivity in algebraic varieties; 20. Links
with sheaf cohomology; Bibliography; Index.
Series: Cambridge Tracts in Mathematics (No. 160)
Paperback (ISBN-13: 9780521045674)
40 exercises
Page extent: 290 pages
Size: 228 x 152 mm
Weight: 0.435 kg
Algebraic numbers can approximate and classify any real number. Here, the
author gathers together results about such approximations and classifications.
Written for a broad audience, the book is accessible and self-contained,
with complete and detailed proofs. Starting from continued fractions and
Khintchinefs theorem, Bugeaud introduces a variety of techniques, ranging
from explicit constructions to metric number theory, including the theory
of Hausdorff dimension. So armed, the reader is led to such celebrated
advanced results as the proof of Mahlerfs conjecture on S-numbers, the
Jarnik*Besicovitch theorem, and the existence of T-numbers. Brief consideration
is given both to the p-adic and the formal power series cases. Thus the
book can be used for graduate courses on Diophantine approximation (some
40 exercises are supplied), or as an introduction for non-experts. Specialists
will appreciate the collection of over 50 open problems and the rich and
comprehensive list of more than 600 references.
* Broad treatment accessible to graduate students and non-specialists *
Rich and comprehensive list of references * Collection of 50 open problems
Contents
Preface; Frequently used notation; 1. Approximation by rational numbers; 2. Approximation to algebraic numbers; 3. The classifications of Mahler and Koksma; 4. Mahlerfs conjecture on S-numbers; 5. Hausdorff dimension of exceptional sets; 6. Deeper results on the measure of exceptional sets; 7. On T-numbers and U-numbers; 8. Other classifications of real and complex numbers; 9. Approximation in other fields; 10. Conjectures and open questions; Appendix A. Lemmas on polynomials; Appendix B. Geometry of numbers; References; Index.
EMS Tracts in Mathematics Vol. 4
ISBN 978-3-03719-040-1
November 2007, 777 pages, hardcover, 17.0 cm x 24.0 cm.
Mixed, transmission, or crack problems belong to the analysis of boundary value problems on manifolds with singularities. The Zaremba problem with a jump between Dirichlet and Neumann conditions along an interface on the boundary is a classical example. The central theme of this book is to study mixed problems in standard Sobolev spaces as well as in weighted edge spaces where the interfaces are interpreted as edges. Parametrices and regularity of solutions are obtained within a systematic calculus of boundary value problems on manifolds with conical or edge singularities. This calculus allows singularities on the interface, and homotopies between mixed and crack problems. Additional edge conditions are computed in terms of relative index results. In a detailed final chapter, the intuitive ideas of the approach are illustrated, and there is a discussion of future challenges. A special feature of the text is the inclusion of many worked out examples which help the reader to appreciate the scope of the theory and to treat new cases of practical interest.
This book is addressed to mathematicians and physicists interested in models with singularities, associated boundary value problems, and their solvability strategies based on pseudo-differential operators. The material is also useful for students in higher semesters and young researchers, as well as for experienced specialists working in analysis on manifolds with geometric singularities, the applications of index theory and spectral theory, operator algebras with symbolic structures, quantisation, and
Table of contents