We study the e?ect of addition on the Hamming weight of a positive integer. Consider the first 2n positive integers, and fix an ? among them. We show that if the binary representation of ? consists of ?(n) blocks of zeros and ones, then addition by ? 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 F2. Our result implies that powering by ? composed of many blocks requires exponential-size, bounded-depth arithmetic circuits over F2.
展开▼
