I am interested in Boolean function polynomial/rational exact/approximate/one sided approximate representation, relation to circuit/communication complexity, tools utilized to study Boolean functions (such as combinatorics, analysis, approximation theory, algebra etc).

What are some of the important references, lecture notes and key papers (including survey) in the field of Boolean functions for someone wanting to learn the growth of the area from 80s till today.

Even open problems in the area would be a good introduction as one can usually trace back the literature. One important open problem is sensitivity-block sensitivity conjecture.

  • 3
    $\begingroup$ Are you familiar with the textbooks by Jukna, O'Donnell, and Crama/Hammer, which themselves have hundreds of references? As is, this question is way too broad for a useful answer here. If you just want polynomial representations, then please make that more explicit. $\endgroup$ Commented Jan 1, 2015 at 13:33
  • 2
    $\begingroup$ I second what Andras said. This question is ridiculously broad. I am puzzled how it was left open. $\endgroup$ Commented Jan 1, 2015 at 19:10
  • 1
    $\begingroup$ The question might have made sense a few years ago but now that we have books by Stasys Jukna and Ryan O'Donnel I don't think it does (at least not until you have read those books). $\endgroup$
    – Kaveh
    Commented Jan 1, 2015 at 20:10
  • 1
    $\begingroup$ What about the book Boolean Function Complexity: springer.com/mathematics/applications/book/978-3-642-24507-7 ? $\endgroup$ Commented Jan 2, 2015 at 19:11
  • $\begingroup$ @MichaelBlondin That is a reasonable reference (gives overview to various topics). Field is deep also broad. $\endgroup$
    – Turbo
    Commented Jan 2, 2015 at 21:35

1 Answer 1


Bryant's "Graph-Based Algorithms for Boolean Function Manipulation" introduced Reduced-Order Binary Decision Diagrams (ROBDDs) for representing and manipulating Boolean functions. I believe these see a lot of use in CAD tools and circuit synthesis problems. Bryant's paper is a good place to start a literature review for BDD. He cites a few key earlier works and a lot of the more recent work grew out of, and cited, his paper.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.