Consider the standard logistic regression ('LR') function, $ y = \sigma(w^T \cdot x + b) $, where $\sigma$ is the logistic function ('sigmoid'). When checking the accuracy, we will consider the argmax of this classifier as it's output (binary output and not probabilistic output).
Consider the $n$-dimensional parity binary classification problem, given a binary string $x$, the ground truth $y=parity(x)$ is the parity of the number of $1$ bits in $x$, meaning $0$ if there are an even number of $1$-bits, and $1$ otherwise.
For example, in $2$ dimensions, we have $parity(00)=0$, $parity(01)=1$, $parity(10)=1$, and $parity(11)=0$ which is exactly the XOR problem, for which the maximal accuracy of the LR is $0.75$ (that is, just implementing an AND).
In the $3$ dimensional case, using some geometrical intuition, I managed to build a solution for LR with $0.75$ accuracy as well.
I'm wondering what is the formula for the general case, i.e.,
What is the maximal accuracy of LR for the $n$-dimensional parity problem?