Boolean Function Complexity: Advances and Frontiers
by Stasys Jukna
Springer-Verlag, 2012, XVI, 617 p. 70 illus, Series: Algorithms and Combinatorics, Vol. 27, ISBN 978-3-642-24507-7
| TOC [pdf] | Blurb Preface | |
| Chapter 1 | Preview at Google | |
| List of errata | Comments, links, etc. |
Here is the chapter on monotone circuits related to the current controversy ... Norbert's attempt to prove P!=NP using Razborov's Method of Approximations (its symmetric version). If true, Norbert's argument would also work for Tardos' function. But this function can be computed by polynomial size circuits ... More details about the Tardos' function itself are here .
Three months before the book was finished,
Andrew Drucker has made an appeal on his
blog
asking interested people to help to improve
the grammar and idiomatic English of the book (I am not a native English speaker).
Following this appeal,
Andrew Drucker,
William Gasarch,
Jonathan Katz,
Massimo Lauria,
Troy Lee,
Matthew Smedberg,
Ross Snider,
Marcos Villagra,
and
Ryan Williams
took parts of the book for proofreading. (Sorry, I couldn't find reliable links to home pages of Matthew and Ross.)
They have done a great job!
Not only English was substantially improved -- I received a lot of useful comments/suggestions
concerning the contents as well. This was a
unique in all respects adventure.
Many thanks to Andy and all you friends, also in the name of future readers!
All remaining errors are entirely my fault.
Review by William Gasarch in ACM SIGACT news
My own summary in Bulletin of EATCS (invited by Kazuo Iwama)
From the reviews (collected by Springer):
"All material in the book is accessible to graduate or even undergraduate students of computer science, mathematics or electrical engineering. ... I gladly recommend this book to beginning students, who will find this book a good starting point in exploring the field of complexity theory, as well as to mature researchers who would like to bring themselves up-to-date on some aspect of the theory. ... the book contains a large number of open research problems, including some really enticing ones! (Sergey Yekhanin, SIAM Review, Vol. 57 (3), September, 2015)
The results stated in the book are well motivated and given with an intuitive explanation of their proof idea wherever appropriate. Each chapter of the book contains open research problems and a section with exercises to deepen the understanding of the presented material and make the book suitable for course work. The book is well suited for graduate students and professionals who seek an accessible, research-oriented guide to the important techniques for proving lower bounds on the complexity of problems connected to Boolean functions. (Michael Thomas, Mathematical Reviews, January, 2013)
This monograph is about circuit complexity, dealing with establishing lower bounds on the computational complexity of specific problems. The book is mainly devoted to mathematicians, to researchers in computer science wishing to complete their knowledge about the state of the art in circuit complexity, as well as to graduate students in mathematics and computer science, and is self-contained. An impressive work providing a large amount of information on circuit complexity. (Ioan Tomescu, Zentralblatt MATH, Vol. 1235, 2012)
Jukna, a well-known researcher in the field, has succeeded in producing an excellent comprehensive exposition on the field, starting from early results from the '40s and '50s and proceeding to the most recent achievements. The book is going to be very useful for researchers and graduate students in computer science and discrete mathematics. The style of writing is pleasant. The many exercises and research problems round out the highlights of this recommendable book. (Arto Salomaa, ACM Computing Reviews, June, 2012)