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.

$\endgroup$
  • 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 '15 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 '15 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 '15 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 '15 at 19:11
  • $\begingroup$ @MichaelBlondin That is a reasonable reference (gives overview to various topics). Field is deep also broad. $\endgroup$ – T.... Jan 2 '15 at 21:35
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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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