Abstract | ||
---|---|---|
We study the effect of addition on the Hamming weight of a positive integer. Consider the first $2^n$ positive integers, and fix an $\alpha$ among them. We show that if the binary representation of $\alpha$ consists of $\Theta(n)$ blocks of zeros and ones, then addition by $\alpha$ causes a constant fraction of low Hamming weight integers to become high Hamming weight integers. This result has applications in complexity theory to the hardness of computing powering maps using bounded-depth arithmetic circuits over $\mathbb{F}_2$. Our result implies that powering by $\alpha$ composed of many blocks require exponential-size, bounded-depth arithmetic circuits over $\mathbb{F}_2$. |
Year | Venue | Field |
---|---|---|
2015 | CoRR | Integer,Arithmetic circuits,Discrete mathematics,Combinatorics,Hamming weight,Mathematics,Binary number |
DocType | Volume | Citations |
Journal | abs/1503.01170 | 0 |
PageRank | References | Authors |
0.34 | 7 | 1 |
Name | Order | Citations | PageRank |
---|---|---|---|
John Y. Kim | 1 | 2 | 1.12 |