Randal Bryant developed an exponential size lower bound for any BDD encoding the middle bit output of the multiplication function, regardless of variable permutation.But at the same time the multiplication function is decidable in logarithmic space. Of course related to P versus NP, the lower bounds complexity of its inverse function is currently unknown. Having an efficient BDD encoding for multiplication also provides a mechanism for efficient factoring, so I understand that this would seem implausible.However, if a function belongs to L (such as multiplication or so I think), it most certainly belongs to L/Poly which is (to my understanding) the class of polynomial sized BDDs.From what I can discern, Bryant's proof relies on communication complexity rather than crypto-hardness assumptions or building upon mainstream conjecture. So what's going on here that seems a blatant contradiction in known lower bounds?For some related background see this post:https://cstheory.stackexchange.com/questions/3462/most-significant-bit-of-integer-multiplication-and-binary-decision-diagrams
Multiplication function BDD size lower bounds
complexity theory;bdd
I think the resolution to the paradox comes from looking more carefully what is meant when we say that multiplication can be performed in logarithmic space, and looking more carefully at what we mean by a BDD.Suppose we want to multiply two $n$-bit numbers $a,b$, and suppose the two numbers $a,b$ are stored in read-only memory.  Then we can calculate any desired bit of the product using only $O(\lg n)$ additional bits of space.  However, this fundamentally requires us to have (read-only) access to the numbers being multiplied.(Take a look at the formula in Wikipedia for $r_i$: $r_i$ depends on $a$, $b$, and $c_{i-1}$.  The carry $c_{i-1}$ needs only $O(\lg n)$ bits of space to store.  However, just storing the carry alone is not enough.  We also need to have the numbers $a,b$ stored, and that requires $\Theta(n)$ bits of storage.)In short, multiplying two numbers takes $\Theta(n)$ bits (read-only) for the numbers being multiplied and $\Theta(\lg n)$ bits (read-write) of additional storage.  This does prove that multiplication is in $L$.  However, it doesn't prove that there is a polynomial-size BDD for multiplication.First, let's understand what we mean by BDD.  There are many types of BDD, but the most relevant one here is the notion of a ROBDD (read-once binary decision diagram).  A ROBDD is allowed to read each bit of the input only once.  Normally, BDD means a ROBDD: for a reference, see, e.g., the Wikipedia article on BDDs, which writes In popular usage, the term BDD almost always refers to Reduced Ordered Binary Decision Diagram (ROBDD.  Moreover, the lower bound for the size of a BDD for multiplication is actually a lower bound on the size of a ROBDD for multiplication.  Therefore, in this answer I'll assume BDD means ROBDD.Now, here's why the above algorithm doesn't prove there is a polynomial-size (RO)BDD for multiplication.  Given an algorithm with space complexity $s$ and time complexity $t$, you can construct a BDD with something like $2^s \times t$ nodes (but here $s$ must include all input bits that might be read more than once, as well as all additional storage).  This means that the number of nodes in a BDD could be as much as exponential in $s$.  In the case of multiplication, we have $s = \Theta(n+\lg n) = \Theta(n)$, so from the existence of the multiplication algorithm above, all we can conclude is that the size of the BDD could be (at most) exponential in $n$.  This isn't enough to show that there exists a polynomial-size BDD.What about L vs L/poly vs BDDs?  I don't think it's true that just because a problem is in L/poly, that means it has a polynomial-size BDD.Roughly speaking (ignoring uniformity vs non-uniformity), a problem is in L or L/poly if there is an algorithm that has read-only access to the inputs and uses only $O(\lg n)$ additional bits of (read-write) storage.  If we also knew that this algorithm reads each bit of its input only once, then that would imply that there is a polynomial-size (RO)BDD for the problem.  But if the algorithm scans back and forth over the input bits, reading them many times, then I don't think there necessarily exists a polynomial-sized (RO)BDD for the problem.  At least, I don't know of any result that implies that.  I could be missing something.I know Wikipedia says that L/poly is a complexity class that captures the complexity of problems with polynomially sized BDDs.  I am not sure that is exactly correct.