function [Gamma,D]=madv(X,Y,cost)
% cost must be a vector of length bits

[nx, bits]=size(X);
[ny, bits]=size(Y);

n=nx+ny;
s=n^2;

% make the F matrix and its complement
F=[zeros(nx,nx) ones(nx,ny); ones(ny,nx) zeros(ny,ny)];
FC=ones(n)-F;

% Now we make the positional matrices
D=zeros(s,bits);
for j=1:nx
 for i=1:ny
   D(j*nx+(j-1)*ny+i,:)= X(j,:)~= Y(i,:);
 end
end
for j=1:ny
 for i=1:nx
   D(n*nx+(j-1)*n+i,:)= Y(j,:) ~= X(i,:);
 end
end

% Target vector c
c=[ones(n,1); sparse((2*bits+1)*s,1)];

% We set up the constraints Ax=b
% First we define the vector b
b=[1; sparse((2*bits+1)*s,1)];

% Now we set up the matrix A
% Notice that we actually construct A'
% Sedumi is smart enough to notice this

% The condition that Z.*F=1
Zeye=[n+1:1:n+s];
j1=ones(1,s);
entries=vec(F)';

% The condition that Z is 0 when F is 0
j2=[2:1:1+s];
entries=[entries vec(FC)'];

i=[Zeye Zeye];
j=[j1 j2];

% The semidefinite conditions
for k=1:bits
  i1=[n+k*s+1:1:n+(k+1)*s];
  i2=[n+bits*s+k*s+1:1:n+bits*s+(k+1)*s];
  i3=[1:n];

  j1=[2+k*s:1:1+(k+1)*s];
  j2=[2+bits*s+k*s:1:1+bits*s+(k+1)*s];
  j3=[2+k*s:n+1:1+(k+1)*s];
  j4=[2+bits*s+k*s:n+1:1+bits*s+(k+1)*s];

  i=[i Zeye Zeye i1 i2 i3 i3];
  j=[j j1 j2 j1 j2 j3 j4];

  entries=[entries -1/cost(k)*D(:,k)' 1/cost(k)*D(:,k)' -1*ones(1,2*s) ones(1,2*n)];
end

A=sparse(i,j,entries,n+(2*bits+1)*s,1+(2*bits+1)*s,(6*bits+2)*s);

% nonnegativity and semidefinite constraints
K.f=n+s;
% K.xcomplex=1:n+s;
K.s=n*ones(1,2*bits);
% K.scomplex=1:2*bits;

% We run sedumi
% pars.eps=10^(-15);
% [x,y,info]=sedumi(A,b,c,K,pars);
[x,y,info]=sedumi(A,b,c,K);
disp('MADversary bound calculated');
bound=1/(c'*x)
disp('The adversary matrix is');
                                                                                
a=x(1:n).^(-.5);
Z=mat(x(n+1:n+s));
Gamma=Z.*(a*a');
