Progresss on the margin problem

Avrim Blum alerts me to something I should've remembered from his class -- one can force a perceptron to make exponentially many mistakes (i.e., achieve an exponentially small margin) with a properly concocted decision list. In fact, digging up my solution to his '04 final exam problem, here is such an example. Assuming my readers think in MATLAB (much as Scott thinks in BASIC), consider the following function:

function [X,Y] = badmargin(n)
X = eye(n);
for k=2:2:n
X(1:1+n-k,k:n) = X(1:1+n-k,k:n) + eye(n-k+1);
end
X = [[X;zeros(1,n)] ones(n+1,1)];
Y = (-ones(n+1,1)).^([2:n+2]');
return


Here's the output [X Y] for n=9:
1 1 0 1 0 1 0 1 1 1
0 1 1 0 1 0 1 0 1 -1
0 0 1 1 0 1 0 1 1 1
0 0 0 1 1 0 1 0 1 -1
0 0 0 0 1 1 0 1 1 1
0 0 0 0 0 1 1 0 1 -1
0 0 0 0 0 0 1 1 1 1
0 0 0 0 0 0 0 1 1 -1
0 0 0 0 0 0 0 0 1 1


(the vectors x in {0,1}^9 are treated as rows, and the labels y = +/-1 are appended at the end).


Using badmargin(n), for n=2 to 20, to generate labeled data sets and running SVM on these, we get the following plot:


which is highly suggestive of exponential decay. It remains to actually prove that this explicit construction achieves exponentially small max-margin. Any takers?