Table of Contents

Part I. Algebraic Structures: 1. Compositions and clones of Boolean functions Reinhard Pöschel and Ivo Rosenberg; 2. Decomposition of Boolean functions Jan C. Bioch; Part II. Logic: 3. Proof theory Alasdair Urquhart; 4. Probabilistic analysis of satisfiability algorithms John Franco; 5. Optimization methods in logic John Hooker; Part III. Learning Theory and Cryptography: 6. Probabilistic learning and Boolean functions Martin Anthony; 7. Learning Boolean functions with queries Robert H. Sloan, Balázs Szörényi and György Turán; 8. Boolean functions for cryptography and error-correcting codes Claude Carlet; 9. Vectorial Boolean functions for cryptography Claude Carlet; Part IV. Graph Representations and Efficient Computation Models: 10. Binary decision diagrams Beate Bollig, Martin Sauerhoff, Detlef Sieling and Ingo Wegener; 11. Circuit complexity Matthias Krause and Ingo Wegener; 12. Fourier transforms and threshold circuit complexity Jehoshua Bruck; 13. Neural networks and Boolean functions Martin Anthony; 14. Decision lists and related classes of Boolean functions Martin Anthony; Part V. Applications in Engineering: 15. Hardware equivalence and property verification J. H. Roland Jiang and Tiziano Villa; 16. Synthesis of multi-level Boolean networks Tiziano Villa, Robert K. Brayton and Alberto L. Sangiovanni-Vincentelli; 17. Boolean aspects of network reliability Charles J. Colbourn.

Promotional Information

A collection of papers written by prominent experts that examine a variety of advanced topics related to Boolean functions and expressions.

About the Author

Dr Yves Crama is Professor of Operations Research and Production Management and the former Director General of the HEC Management School of the University of Liège, Belgium. He is widely recognized as a prominent expert in the field of Boolean functions, combinatorial optimization, and operations research, and he has coauthored more than 70 papers on these subjects. Dr Crama is a member of the Editorial Board of Discrete Optimization, Journal of Scheduling, and 4OR – The Quarterly Journal of the Belgian, French and Italian Operations Research Societies. The late Peter L. Hammer (1936–2006) was a Professor of Operations Research, Mathematics, Computer Science, Management Science, and Information Systems at Rutgers University and the Director of the Rutgers University Center for Operations Research (RUTCOR). He was the founder and editor-in-chief of the journals Annals of Operations Research, Discrete Mathematics, Discrete Applied Mathematics, Discrete Optimization, and Electronic Notes in Discrete Mathematics. Dr Hammer was the initiator of numerous pioneering investigations of the use of Boolean functions in operations research and related areas, of the theory of pseudo-Boolean functions, and of the logical analysis of data. He has published more than 240 papers and 19 books on these topics.

Reviews

' … is likely to become the reference book for applications of Boolean functions. A common effort of twenty two authors and two editors, leading experts in their fields, the monograph, over 700 pages long, covers all important topics and presents state-of-the-art of applications of Boolean functions. This well written volume can be useful to graduate students, researchers in discrete mathematics, computer science, or other fields, as well as practitioners of operations research and combinatorial optimization. Also readers like me, who want to learn more about Boolean functions, will find this volume very informative.' Marcin Kaminski, SIGACT News