Skip to main content
Theoretical Computer Science

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

Required fields*

7
  • $\begingroup$ There is a proof in Descriptive Complexity book iirc. Am not sure what you mean by most significant bit being one, it always is one by definition. $\endgroup$ Commented Aug 28, 2017 at 13:13
  • $\begingroup$ This is just a joke of your teacher: Bits are 0 or 1, and the most significant bit is the non-0 bit in the highest position. It equals 1 by definition (unless one of the factors $l_1$ and $l_2$ is zero). $\endgroup$ Commented Aug 28, 2017 at 13:16
  • $\begingroup$ @Kaveh Thanks for the reference: I'll check it out. Sorry for the confusion regarding the most significant bit. I am implicitly assuming that the result is printed in 2m-1 bits and if necessary with leading 0's. $\endgroup$ Commented Aug 28, 2017 at 13:43
  • $\begingroup$ @Kaveh: In the Descriptive Complexity Book, only the upper bound is mentioned. I could not find anything regarding hardness of binary multiplication, though. $\endgroup$ Commented Aug 28, 2017 at 14:00
  • $\begingroup$ You write: "Moreover, it seems to be well-known that binary multiplication is already $\mathsf{DLogTime}$-uniform $\mathsf{TC}^0$-hard." Why does it seem so? I know that binary multiplication is not in $\mathsf{AC}^0$, and that is all I currently care about. $\endgroup$ Commented Aug 28, 2017 at 21:13