Integer addition and Hamming weight

zbMATH Open1351.11081MaRDI QIDQ2830409FDOQ2830409

Authors John Y. Kim

Publication date 28 October 2016

Published in Integers (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1503.01170

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

Hamming weightbounded-depth arithmetic circuitshardness of computing

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Linear codes (general theory) (94B05) Number-theoretic algorithms; complexity (11Y16)

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

Recommendations

• The Hamming weight of the non-adjacent-form under various input statistics
• On the number of carries occurring in an addition mod \(2^k -1\)
• scientific article; zbMATH DE number 5968524
• On the distribution of low Hamming weight sequence
• Impact of the Hamming weight of the difference of two random variables on the probability of its preservation after addition and subtraction

Cited in

(3)

• Means of Numbers with Fixed Hamming Weight
• The Hamming weight of the non-adjacent-form under various input statistics
• Impact of the Hamming weight of the difference of two random variables on the probability of its preservation after addition and subtraction

This page was built for publication: Integer addition and Hamming weight

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2830409)