Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Hamming weight:
TR05-049 | 1st April 2005
Joan Boyar, rene peralta

The Exact Multiplicative Complexity of the Hamming Weight Function

We consider the problem of computing the Hamming weight of an n-bit vector using a circuit with gates for GF2 addition and multiplication only. We show the number of multiplications necessary and sufficient to build such a circuit is n - |n| where |n| is the Hamming weight of the ... more >>>

TR14-096 | 29th July 2014
Vikraman Arvind, Sebastian Kuhnert, Johannes Köbler, Jacobo Toran

Solving Linear Equations Parameterized by Hamming Weight

Given a system of linear equations $Ax=b$ over the binary field $\mathbb{F}_2$ and an integer $t\ge 1$, we study the following three algorithmic problems:
1. Does $Ax=b$ have a solution of weight at most $t$?
2. Does $Ax=b$ have a solution of weight exactly $t$?
3. Does $Ax=b$ have a ... more >>>

ISSN 1433-8092 | Imprint