3
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • 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$
    – András Salamon
    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$
    – Sasho Nikolov
    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
    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$
    – Michael Blondin
    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
    Jan 2, 2015 at 21:35

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

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

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