<p><a href="http://dl.acm.org/citation.cfm?id=6433" rel="nofollow">Bryant's "Graph-Based Algorithms for Boolean Function Manipulation"</a> 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. </p>

CC BY-SA 3.0
2015-01-01T15:23:54.590Z
2015-01-01T15:23:54.590Z
Logan Mayfield
<p>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).</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2015-01-01T13:33:17.790Z
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.
András Salamon
CC BY-SA 3.0
2015-01-01T19:10:25.490Z
I second what Andras said. This question is ridiculously broad. I am puzzled how it was left open.
Sasho Nikolov
CC BY-SA 3.0
2015-01-01T20:10:27.663Z
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).
Kaveh
CC BY-SA 3.0
2015-01-02T19:11:16.463Z
What about the book Boolean Function Complexity: http://www.springer.com/mathematics/applications/book/978-3-642-24507-7 ?
Michael Blondin
CC BY-SA 3.0
2015-01-02T21:35:10.683Z
@MichaelBlondin That is a reasonable reference (gives overview to various topics). Field is deep also broad.
Turbo
<big-list><big-picture><boolean-functions><survey>
Important papers and open problems in Boolean functions
Turbo
# Important papers and open problems in Boolean functions

(Asked by: username_0 on 2014-11-26)

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.

**Tags:** big-list, big-picture, boolean-functions, survey

> **Comments:**
> **username_1**: 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.  
> **username_2**: I second what Andras said. This question is ridiculously broad. I am puzzled how it was left open.  
> **username_3**: 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).  
> **username_4**: What about the book Boolean Function Complexity: http://www.springer.com/mathematics/applications/book/978-3-642-24507-7 ?  
> **username_0**: @MichaelBlondin That is a reasonable reference (gives overview to various topics). Field is deep also broad.  

---

## 1 answers

### Answer by username_5 on 2015-01-01. Score: 2

[Bryant's "Graph-Based Algorithms for Boolean Function Manipulation"](http://dl.acm.org/citation.cfm?id=6433) 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.


---

