Skip to content
Register Sign in Wishlist

Complexity Dichotomies for Counting Problems

Volume 1. Boolean Domain

AUD$218.95 inc GST

  • Authors:
  • Jin-Yi Cai, University of Wisconsin, Madison
  • Xi Chen, Columbia University, New York
  • Date Published: November 2017
  • availability: Available
  • format: Hardback
  • isbn: 9781107062375

AUD$ 218.95 inc GST

Add to cart Add to wishlist

Other available formats:

Looking for an inspection copy?

Please email to enquire about an inspection copy of this book

Product filter button
About the Authors
  • Complexity theory aims to understand and classify computational problems, especially decision problems, according to their inherent complexity. This book uses new techniques to expand the theory for use with counting problems. The authors present dichotomy classifications for broad classes of counting problems in the realm of P and NP. Classifications are proved for partition functions of spin systems, graph homomorphisms, constraint satisfaction problems, and Holant problems. The book assumes minimal prior knowledge of computational complexity theory, developing proof techniques as needed and gradually increasing the generality and abstraction of the theory. This volume presents the theory on the Boolean domain, and includes a thorough presentation of holographic algorithms, culminating in classifications of computational problems studied in exactly solvable models from statistical mechanics.

    • Presents a proper foundation for a unified classification theory leading to major dichotomy theorems
    • Broadly accessible as progresses from concrete results to generalized and abstract concepts
    • Provides a distilled yet thorough presentation of new developments including mathgates and holographic algorithms
    Read more

    Reviews & endorsements

    'This remarkable volume presents persuasive evidence that computer applications obey beautiful unities: within the significant classes considered, the problems that are not known to be polynomial time computable are all reducible to each other by a small number of elegant techniques. The treatment is original, comprehensive and thought provoking.' Leslie Valiant, Harvard University, Massachusetts

    'This book provides a thorough study of the complexity of counting. These basic problems arise in statistical physics, optimization, algebraic combinatorics and computational complexity. The past fifteen years of research have led to a (surprisingly clean) complete characterization of their complexity in the form of a 'dichotomy theorem', whose proof is the main goal of this volume. Along the way, the authors provide detailed explanations of basic methods for studying such problems, including holographic algorithms and reductions. The book is very well written and organized, and should be useful to researchers and graduate students in the fields above.' Avi Wigderson, Institute for Advanced Study, Princeton, New Jersey

    'This book would make an excellent introduction to the field of counting complexity for a mathematically literate reader with little or no background in computational complexity … Many of the results included in the book are recent, and have not appeared in book form before. As such, this thorough, self-contained treatment of the subject makes a very valuable contribution to the literature.' Kitty Meeks, MathSciNet

    See more reviews

    Customer reviews

    Not yet reviewed

    Be the first to review

    Review was not posted due to profanity


    , create a review

    (If you're not , sign out)

    Please enter the right captcha value
    Please enter a star rating.
    Your review must be a minimum of 12 words.

    How do you rate this item?


    Product details

    • Date Published: November 2017
    • format: Hardback
    • isbn: 9781107062375
    • length: 470 pages
    • dimensions: 236 x 158 x 30 mm
    • weight: 0.77kg
    • availability: Available
  • Table of Contents

    1. Counting problems
    2. Fibonacci gates and Holant problems
    3. Boolean #CSP
    4. Matchgates and holographic algorithms
    5. 2-spin systems on regular graphs
    6. Holant problems and #CSP
    7. Holant dichotomy for symmetric constraints
    8. Planar #CSP for symmetric constraints
    9. Planar Holant for symmetric constraints
    10. Dichotomies for asymmetric constraints.

  • Authors

    Jin-Yi Cai, University of Wisconsin, Madison
    Jin-Yi Cai is Professor of Computer Science and the Steenbock Professor of Mathematical Sciences at the University of Wisconsin, Madison. He studied at Fudan University, Shanghai (class of 77) and at Cornell University, New York, receiving his Ph.D. in 1986. He held faculty positions at Yale University, Connecticut (1986–1989), Princeton University, New Jersey (1989–1993), and State University of New York, Buffalo (1993–2000), where he rose from Assistant Professor to Full Professor in 1996. He received a Presidential Young Investigator Award (1990), an Alfred P. Sloan Fellowship (1994), and a John Simon Guggenheim Fellowship (1998). He is a Fellow of the Association for Computing Machinery (ACM) and the American Association for the Advancement of Science (AAAS).

    Xi Chen, Columbia University, New York
    Xi Chen is Associate Professor of Computer Science at Columbia University, New York. He studied at Tsinghua University and received his Ph.D. in 2007. His research focuses on complexity theory and algorithmic game theory. He is the recipient of a NSF CAREER Award, an Alfred P. Sloan Fellowship (2012), and an European Association for Theoretical Computer Science (EATCS) Presburger Award (2015).

Sign In

Please sign in to access your account


Not already registered? Create an account now. ×

Sorry, this resource is locked

Please register or sign in to request access. If you are having problems accessing these resources please email

Register Sign in
Please note that this file is password protected. You will be asked to input your password on the next screen.

» Proceed

You are now leaving the Cambridge University Press website. Your eBook purchase and download will be completed by our partner Please see the permission section of the catalogue page for details of the print & copy limits on our eBooks.

Continue ×

Continue ×

Continue ×

Find content that relates to you

Join us online

This site uses cookies to improve your experience. Read more Close

Are you sure you want to delete your account?

This cannot be undone.


Thank you for your feedback which will help us improve our service.

If you requested a response, we will make sure to get back to you shortly.

Please fill in the required fields in your feedback submission.