HN Theater @HNTheaterMonth

Knuth - "Fun With Binary Decision Diagrams (BDDs)" (June 5, 2008)

https://www.youtube.com/watch?v=SQE21efsf7Y

He has some other good material on BDDs, some of it in TAoCP.

(My search fu is failing me this morning. I found https://crypto.stanford.edu/pbc/notes/zdd/ which seems interesting, and Ben Lynn has some cool stuff linked from his home page: "Lambda calculus one-line self-interpreter", "Haskell compiler that runs in the browser"...)

⬐ dunham

Ben Lynn's "Award winning compiler" is one of my favorites, and he keeps adding to that page.

⬐ dubya

Knuth also has sample code here:

https://www-cs-faculty.stanford.edu/~knuth/programs.html

I couldn't get some of it to work due to pointer hijinks not cooperating with Macos, but it's fine in a Linux vm.

I wouldn't do it justice[1], it deserves a blog post or a book [2] but in general solving almost any boolean algebra problem, in hundreds, and hundreds of thousands variables, very efficiently and in very compact representation (via ordered sparse bit vectors[3]).

While with Karnaugh maps you can simplify a boolean function with a few variables, BDDs can solve for thousands, fast.

And no need to explain applications of high-dimensional boolean algebra on HN, with boolean algebra you can solve any logic problem expressed as boolean function, any combinatorial problem (except for those with nasty functions), classic graph theory problems.

Surprisingly it allows to solve optimization problems[4], like boolean programming, SAT solver, max independent set or max cut in graphs, very efficiently, it can be used in something like belief propagation or lattice induction for inference, but if that's not enough you can use it for random number generation, lossless compression, perfect hashing, etc, etc.

I haven't seen such a versatile data structure elsewhere, most of the other things developed in the last 35 years, like the ones in the comment below are solving special cases, BDD is truly one of the most fundamental and severely underrated "swiss army knives" (that is in CS, EE people know it very well in logic synthesis and verification, BDD's first "killer app").

It's probably easier to list what you can't do with BDD, kind of like what you can't do with (high-dimensional) boolean logic.

I think it skipped the radar of CompSci community at large because it was too quickly siloed into "that circuit analysis/verification tool used by electrical engineers".

Yes, it's "just" a DAG but with very particular (and very simple) constraints which allow it to solve infinite variety of problems in a very elegant and surprising way [5].

[1] it's really worth watching the lecture on BDDs by Don Knuth , starting around 13:32, his enthusiasm is contagious: https://www.youtube.com/watch?v=SQE21efsf7Y&t=13m32s

Part 2 on ZDD: https://www.youtube.com/watch?v=-HzQYeqS9Wc

[2] TAOCP, volume 4A, Combinatorial Algorithms, p.202 - 280: https://www.amazon.com/Art-Computer-Programming-Combinatoria...

There is a free preprint here https://www-cs-faculty.stanford.edu/~knuth/fasc1b.ps.gz

[3] https://en.wikipedia.org/wiki/Zero-suppressed_decision_diagr...

[4] Bergman, David, et al. "Discrete optimization with decision diagrams." INFORMS Journal on Computing 28.1 (2016): 47-66.

[5] Bryant, Randal E. "Graph-based algorithms for boolean function manipulation." Computers, IEEE Transactions on 100.8 (1986): 677-691.

I hope that answers your question, dang, and sorry for title mishap.

⬐ jan_Inkepa

Just watching through the Knuth lecture now. 40 minutes in (~54m mark) and I learned something new (to me) and useful and cool (randomly picking maximal independent sets of graphs). And I'm only half way in. Very nice; thanks for the recommendation :)

⬐ bra-ket

Part 2 on ZDD: https://www.youtube.com/watch?v=-HzQYeqS9Wc

also some notes here on implementation: https://crypto.stanford.edu/pbc/notes/zdd/

related, Knuth's Fun with Binary Decision Diagrams, https://www.youtube.com/watch?v=SQE21efsf7Y

⬐ gmiller123456

They've posted a whole bunch of Knuth videos on their channel in the past couple of weeks [1]

[1] https://www.youtube.com/user/stanfordonline/videos

⬐ reidjs

Don’t have the attention span to watch the whole video right now, but I love that now with youtube and people posting lectures online I can come back to it later. Thanks for posting!