Classical algorithm for the Majority Problem
Presentation of the problem : The majority problem is equivalent to the perceptron learning. For each $$a \in \mathbb{Z}_n$$ define a function $$m_a : \mathbb{Z}_2^N \rightarrow \mathbb{Z}_2$$ : $$m_a(x)= \begin{cases} 1 & \text{ if } wt(a-x)\leq n/2 \\0 & \text{ otherwise } \end{cases}$$ Where wt is the weight of a bit-string (number of 1). Alternatively we can write : $$ m_a(x) = \Theta (n/2 – wt(x-a) )$$. The problem is : determine a given an access to answers from $$m_a$$. »