BAP: Lecture 10 (Mar 14, 2002)
The notes for this lecture are available in
In this lecture, we
 Introduced a smoothed model for bandwidth, and proved that
it was weaker than the monotone adversary model. We also observed
that Turner's theorem holds for the monotone adversary model, so it holds
for the smoothed model.
Papers on the monotone adversary model include:

@article{ blum95coloring,
author = "Avrim Blum and Joel Spencer",
title = "Coloring Random and SemiRandom kColorable Graphs",
journal = "J. Algorithms",
volume = "19",
number = "2",
pages = "204234",
year = "1995",
url = "citeseer.nj.nec.com/blum95coloring.html" }
 "Heuristics for Semirandom Graph Problems" by Uri Feige and Joe Kilian.
To appear in Journal of Computer and System Sciences.
A preliminary version, named "Heuristics for finding large independent sets, with applications to coloring semirandom graphs", appeared in the Proceedings of 39th FOCS, 674683, 1998.
Available at
Uri Feige's homepage.

"Improved performance guarantees for bandwidth minimization heuristics", by
Uri Feige and R. Krauthgamer .
Unpublished manuscript, November 1998. Available at
Robert Krauthgamer's homepage.
 We discussed algorithms for bisection in the planted bisection model.
Papers mentioned included:

@article{ condon01algorithms,
author = "Anne Condon and Richard M. Karp",
title = "Algorithms for graph partitioning on the planted partition model",
journal = "Random Structures and Algorithms",
volume = "18",
number = "2",
pages = "116140",
year = "2001",
url = "citeseer.nj.nec.com/article/condon99algorithms.html" }
 "Eigenvalues and graph bisection: an averagecase analysis", by
Ravi Boppana. Appeared in the Proceedings of the 28th Annual IEEE Symposium on
Foundations of Computer Science, pages 280285, IEEE Computer Society Press, 1987.
 Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning, D. S. Johnson, C. R. Aragon, L. A.
McGeoch and C. Shevon, Operations Research, 37:6 (1989), 865892. (available at JSTOR).
 We then examined Frank McSherry's analysis of a spectral partitioning
algorithm for the planted bisection model. The paper is:
"Spectral Partitioning of Random Graphs", and it appeared in STOC '01.
In class, we tested out McSherry's algorithm. Here is a transcript of
matlab session (with a few useless lines removed).
n = 100;
a = [rand(n) < .2, rand(n) < .1; rand(n) < .1, rand(n) < .2];
a = a + a';
spy(a)
p = randperm(200);
b = a(p,p);
spy(b)
[v,d] = eigs(b,4);
Iteration 10: a few Ritz values of the 20by20 matrix:
13.5374
14.5138
21.7683
59.6353
d
d =
59.6353 0 0 0
0 21.7683 0 0
0 0 14.5138 0
0 0 0 13.5374
[w,perm] = sort(v(:,2));
plot(w)
c = b(perm,perm);
spy(c)
figure(2)
plot(p(perm))
pp = p(perm);
sort(pp(1:100))
ans =
Columns 1 through 14
101 102 103 104 105 106 107 108 109 110 111 112 113 114
Columns 15 through 28
115 116 117 118 119 120 121 122 123 124 125 126 127 128
Columns 29 through 42
129 130 131 132 133 134 135 136 137 138 139 140 141 142
Columns 43 through 56
143 144 145 146 147 148 149 150 151 152 153 154 155 156
Columns 57 through 70
157 158 159 160 161 162 163 164 165 166 167 168 169 170
Columns 71 through 84
171 172 173 174 175 176 177 178 179 180 181 182 183 184
Columns 85 through 98
185 186 187 188 189 190 191 192 193 194 195 196 197 198
Columns 99 through 100
199 200
plot(w)
diary off