Integer addition and Hamming weight

zbMATH Open1351.11081arXiv1503.01170MaRDI QIDQ2830409FDOQ2830409

Authors: John Y. Kim 

Publication date: 28 October 2016

Published in: Integers (Search for Journal in Brave)

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

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

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

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

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)

Cited In (3)

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

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)