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

<p>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&gt;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)}$.</p>

CC BY-SA 3.0
2017-08-29T05:57:14.907Z
Thanks for the answers! Yes, this verifies that binary multiplication is complete for TC0.  As for most significant bit, there are some issues remaining. The most significant bit of the multiplication (111 x 111) = 110001 is 1, and for this one (100 x 100)= 010000, it is 0. Note that the most significant bits of the multiplicands are the same in both cases. Therefore, I do not think that, in general, it is sufficient to add up the most significant bits. Am I missing something?
Heyheyhey
CC BY-SA 3.0
2017-08-29T06:53:35.677Z
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
CC BY-SA 3.0
2017-08-29T08:31:31.877Z
@EmilJeřábek Yes, the naive argument in the answer works for the least significant bit, but not for the most significant one. The carry bits influence the result of the most significant bit. Somehow we are forced to do iterated addition to reflect the carry bits (which is TC0-hard). I'd be surprised if the problem turns out to be in AC0.
Heyheyhey
CC BY-SA 3.0
2017-08-30T06:19:36.960Z
The edit is not correct. Since we are adding m numbers, there may not be just one bit of carry, but log m. Deciding how much of it propagates is then much more difficult.
Emil Jeřábek
CC BY-SA 3.0
2017-08-30T06:23:44.693Z
Indeed, disregarding everything else: computing the carry out of a single position (say, somewhere in the middle) is already equivalent to Count, hence TC^0-complete.
Emil Jeřábek
CC BY-SA 3.0
2017-08-30T07:15:54.120Z
@EmilJeřábek Yes, the updated answer is still wrong: the depth of this circuit is not constant. Actually, the way it has been described it looks like it has even linear depth. This is by no means an AC0 circuit. I also think that this problem is TC0-hard, but just cannot come up with the correct reduction.
Heyheyhey
CC BY-SA 3.0
2017-08-30T10:30:53.023Z
@Emil, you are right. It is not necessary that all of them have at least a 1.
Kaveh
CC BY-SA 3.0
2017-08-30T10:32:40.837Z
@Heyheyhey, the formula I wrote is FO and therefore in uniform AC0.
Kaveh
CC BY-SA 3.0
2017-08-30T14:19:22.187Z
@Kaveh, your current answer only shows TC0-hardness of binary multiplication, which I had appreciated already in my first comment. The original question regarding the most significant bit remains unanswered.
Heyheyhey
CC BY-SA 3.0
2017-08-30T15:52:38.853Z
Yes, I am referring to the formula you referred to in your previous comment. That formula is FO and therefore in uniform AC0. Your statement that it is not is wrong.
Kaveh
CC BY-SA 3.0
2017-08-30T17:15:26.220Z
@Kaveh OK, I see, that is true! Edit's are confusing ;-) I am still trying to get an hardness result (as to me it seems less likely that MSB is in AC0)
Heyheyhey
CC BY-SA 3.0
2017-08-29T02:06:31.907Z
2017-08-30T10:31:17.700Z
2017-08-30T10:31:17.700Z
Kaveh
<p>I am interested in determining the complexity of the following decision problem: <em>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)?</em> </p>

<p>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, <em>Uniform constant-depth threshold circuits for division and iterated multiplication</em>, Hesse, Allender and Barrington prove that iterated (and thus binary) multiplication is in $\mathsf{DLogTime}$-<em>uniform</em> $\mathsf{TC}^0$. Moreover, it seems to be well-known that binary multiplication is already $\mathsf{DLogTime}$-<em>uniform</em> $\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}$-<em>uniform</em> $\mathsf{TC}^0$-hard, my question can also be read as: Does it remain $\mathsf{DLogTime}$-<em>uniform</em> $\mathsf{TC}^0$-hard if we want to decide only the most significant bit of binary multiplication?</p>

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

CC BY-SA 3.0
2017-08-28T13:13:08.080Z
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
CC BY-SA 3.0
2017-08-28T13:16:57.633Z
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
CC BY-SA 3.0
2017-08-28T13:43:04.290Z
@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
CC BY-SA 3.0
2017-08-28T14:00:53.703Z
@Kaveh: In the Descriptive Complexity Book, only the upper bound is mentioned. I could not find anything regarding hardness of binary multiplication, though.
Heyheyhey
CC BY-SA 3.0
2017-08-28T21:13:04.950Z
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
CC BY-SA 3.0
2017-08-28T22:53:21.090Z
I think the most significant bit case is very easy and can be done in constant time by taking the AND of the most significant bits of the multiplicants. Proof: Assume one of the multiplicants has its most significant bit 0. Take the maximum values that both multiplicants can represent under this restriction and multiply them. Observe the result is smaller than the minimum value that requires the (2m-1)-th bit to be 1 for m>1. The m=1 case is easily seen to be the same by taking all possible cases.
chazisop
CC BY-SA 3.0
2017-08-29T06:02:29.107Z
@ThomasKlimpel, yes I read papers, mentioning TC0-hardness of binary multiplication, without citing any references; so this should be folklore. In fact, it is: please see the argument in Kaveh's response.
Heyheyhey
<cc.complexity-theory><circuit-complexity>
Deciding the Most Significant Bit of Binary Multiplication
Heyheyhey
# Deciding the Most Significant Bit of Binary Multiplication

(Asked by: username_0 on 2017-08-28)

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).

**Tags:** cc.complexity-theory, circuit-complexity
> **Comments:**
> **username_1**: 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.  
> **username_2**: 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).  
> **username_0**: @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.  
> **username_0**: @Kaveh: In the Descriptive Complexity Book, only the upper bound is mentioned. I could not find anything regarding hardness of binary multiplication, though.  
> **username_3**: 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.  
> **username_4**: I think the most significant bit case is very easy and can be done in constant time by taking the AND of the most significant bits of the multiplicants. Proof: Assume one of the multiplicants has its most significant bit 0. Take the maximum values that both multiplicants can represent under this restriction and multiply them. Observe the result is smaller than the minimum value that requires the (2m-1)-th bit to be 1 for m>1. The m=1 case is easily seen to be the same by taking all possible cases.  
> **username_0**: @ThomasKlimpel, yes I read papers, mentioning TC0-hardness of binary multiplication, without citing any references; so this should be folklore. In fact, it is: please see the argument in Kaveh's response.  

---

## 1 answers

### Answer by username_1 on 2017-08-29. Score: 6

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)}$.

> **Comments:**
> **username_0**: Thanks for the answers! Yes, this verifies that binary multiplication is complete for TC0.  As for most significant bit, there are some issues remaining. The most significant bit of the multiplication (111 x 111) = 110001 is 1, and for this one (100 x 100)= 010000, it is 0. Note that the most significant bits of the multiplicands are the same in both cases. Therefore, I do not think that, in general, it is sufficient to add up the most significant bits. Am I missing something?  
> **username_5**: 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.  
> **username_0**: @EmilJeřábek Yes, the naive argument in the answer works for the least significant bit, but not for the most significant one. The carry bits influence the result of the most significant bit. Somehow we are forced to do iterated addition to reflect the carry bits (which is TC0-hard). I'd be surprised if the problem turns out to be in AC0.  
> **username_5**: The edit is not correct. Since we are adding m numbers, there may not be just one bit of carry, but log m. Deciding how much of it propagates is then much more difficult.  
> **username_5**: Indeed, disregarding everything else: computing the carry out of a single position (say, somewhere in the middle) is already equivalent to Count, hence TC^0-complete.  
> **username_0**: @EmilJeřábek Yes, the updated answer is still wrong: the depth of this circuit is not constant. Actually, the way it has been described it looks like it has even linear depth. This is by no means an AC0 circuit. I also think that this problem is TC0-hard, but just cannot come up with the correct reduction.  
> **username_1**: @Emil, you are right. It is not necessary that all of them have at least a 1.  
> **username_1**: @Heyheyhey, the formula I wrote is FO and therefore in uniform AC0.  
> **username_0**: @Kaveh, your current answer only shows TC0-hardness of binary multiplication, which I had appreciated already in my first comment. The original question regarding the most significant bit remains unanswered.  
> **username_1**: Yes, I am referring to the formula you referred to in your previous comment. That formula is FO and therefore in uniform AC0. Your statement that it is not is wrong.  
> **username_0**: @Kaveh OK, I see, that is true! Edit's are confusing ;-) I am still trying to get an hardness result (as to me it seems less likely that MSB is in AC0)  

---

