# Deciding the Most Significant Bit of Binary Multiplication

I am interested in determining the complexity of the following decision problem: Given two integers $l_1$ and $l_2$ (each with at most m bits), decide whether the most significant bit of the multiplication $l_1 \cdot l_2$ is 1 (where the result is printed in 2m bits with possibly leading 0's)?

Some background on the problem: Obviously, this problem is a special case of binary multiplication that asks whether the $i$-th bit of the multiplication $l_1 \cdot l_2$ is 1. In their paper, Uniform constant-depth threshold circuits for division and iterated multiplication, Hesse, Allender and Barrington prove that iterated (and thus binary) multiplication is in $\mathsf{DLogTime}$-uniform $\mathsf{TC}^0$. Moreover, it seems to be well-known that binary multiplication is already $\mathsf{DLogTime}$-uniform $\mathsf{TC}^0$-hard. However, I was not able to find a particular source proving this hardness result. As a non-expert in circuit complexity, I would also appreciate a pointer to this general hardness result. Finally, assuming that binary multiplication is $\mathsf{DLogTime}$-uniform $\mathsf{TC}^0$-hard, my question can also be read as: Does it remain $\mathsf{DLogTime}$-uniform $\mathsf{TC}^0$-hard if we want to decide only the most significant bit of binary multiplication?

UPDATE: Kaveh's answer clarifies why binary multiplication is $\mathsf{TC}^0$-hard (reduction from COUNT). The precise complexity of deciding the most significant bit of binary multiplication remains open (and the bounty is for this question).

• 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. – Kaveh Aug 28 '17 at 13:13
• 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). – Gamow Aug 28 '17 at 13:16
• @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. – Heyheyhey Aug 28 '17 at 13:43
• @Kaveh: In the Descriptive Complexity Book, only the upper bound is mentioned. I could not find anything regarding hardness of binary multiplication, though. – Heyheyhey Aug 28 '17 at 14:00
• 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. – Thomas Klimpel Aug 28 '17 at 21:13

Multiplication is complete for $\mathsf{TC}^0$ and this is a well know result. The reduction is from Count (number of 1 bits in a binary number). Comparison of binary numbers is in $\mathsf{AC^0}$ so $\mathsf{Majority}$ is reducible to $\mathsf{Count}$.
To reduce $\mathsf{Count}$ to $\mathsf{Mult}$ do as follows: consider input is $a_0a_1\ldots a_n$. Insert $k$ 0s between $a_i$s and call it $a$. Multiply it with $b$ which is like $a$ except that $a_i$s in it are replaced with 1s. Pick $k>3n$. The number in the middle section of $ab$ is the answer. The reduction is in $\mathsf{FO}$ and shows that $\mathsf{Count} \in \mathsf{FO(Mult)}$.
• If $x=\lfloor2^{n+1/2}\rfloor$ and $y=\lceil2^{n+1/2}\rceil$, then the MSB of $x^2$ is 0, and the MSB of $y^2$ is 1, even though $x$ and $y$ may only differ in one, least significant, bit. – Emil Jeřábek supports Monica Aug 29 '17 at 6:53