16 citations · 22 across the 2 of their papers we have counts for
Showing cs.CCShow all
2 papers · 1 filter
cs.CC2003★ 6 cited
Hardness of approximating the weight enumerator of a binary linear code
M. N. Vyalyi
We consider the problem of evaluation of the weight enumerator of a binary linear code. We show that the exact evaluation is hard for polynomial hierarchy. More exactly, if WE is a…
cs.CC2001
A comparison of Zeroes and Ones of a Boolean Polynomial
M. N. Vyalyi
In this paper we consider the computational complexity of the following problem. Let be a Boolean polynomial. What value of , 0 or 1, is taken more frequently? The problem i…