Labeled points in $\{0,1\}^n$ such that every linear separator requires exponential weights

Question

I want to find labeled samples in $\{0,1\}^n$ such that the Perceptron algorithm takes $2^{\Omega(n)}$ steps to converge. One way to do this would be to find a sequence of labeled examples that are linearly separable, but require every linear separator to have at least one exponentially large weight. To show that the samples are linearly separable, it is enough to show that they are consistent with a decision list, which should be apparent from the list of samples. So, my question is

Does there exist a set of labeled samples $S$ in $\{0,1\}^n$ that are consistent with a decision list and such that any linear threshold function that correctly labels $S$ has at least one exponentially large weight $w_i = 2^{\Omega(n)}$?

Here are the definitions that I'm working with: A linear threshold function $f \colon \{0,1\}^n \to \{0,1\}$ with associated weights $w_0, \dots, w_n \in \mathbb{R}$ gives $f(x) = 1$ if and only if $w_1x_1 + w_2x_2 + \dots + w_nx_n \geq w_0$. Given a set $S$ of points in $\{0,1\}^n$ labeled $0$ or $1$, we say that a linear threshold function $f$ correctly labels $S$ if $f(x) = 1$ whenever $x$ is labeled $1$ and $f(x) = 0$ whenever $x$ is labeled $0$ for all $x \in S$.

Note: I had asked the same question on math.stackexchange since it seemed relevant to both fields. Here is the link for that.

Answer 1

Håstad gave an even better example in his paper On the Size of Weights for Threshold Gates, which requires super exponential weights.

A simple example which requires exponential weights is the function $\sum_i 2^i (x_i - y_i) \geq 0$ or variants.