1

 Stephen Miller
 Department of Mathematics
 Rutgers University

2

 1957 (age 12): first kid on his block in Detroit to make thiokol
 (after Sputnik, Mumford High School produced many prominent scientists)
 1958: Boosters for model rockets
 1960: Unsupervised, copycat neighbor launches house, which rotates 3
degrees and almost lands on foundation

3

 SAFETY
 Keep fingers with you at all times
 Count to ten as necessary
 From being around other chemists, how to write a referee’s report:
 “this paper should be greatly reduced
 …or violently oxidized”

4


5


6


7


8


9

 There are only 2 possible coupling constants between atoms, namely
 Selfcoupling
 Nearest neighbor coupling
 The rest are set to be zero
 Accordingly, with linear change of the energy scale (i.e. replace E with
a*E+b) the coupling values can be normalized to be:

10


11


12


13

 Mathematical notion of graph = a set of vertices (aka nodes) and edges
connecting them
 A kregular graph has exactly k edges meeting at each vertex (i.e.
valency=k)
 The adjacency matrix has exactly k 1’s in each row and column
 Therefore the constant vector whose entries are all equal to 1 is an
eigenvector with eigenvalue k
 If the graph is connected all other eigenvalues are < k.
 There may be eigenvalues = k
 All other eigenvalues are strictly between –k and k
 A expander sequence of graphs is one where all other eigenvalues are
bounded away from –k and k by an absolute, fixed amount.

14

 Known to exist by counting arguments (it was known that the number of
graphs which were not expanders was far smaller than the total
 Margulis (1982 and earlier), LubotzkyPhillipsSarnak (1986) gave
explicit constructions using group theory, number theory
 More recently, ideas from computer science: ZigZag construction, covers
 JaoMillerVenkatesan: constructions depending on the generalized
Riemann hypothesis to prove expansion.
 Simplest example: Let Q be a large prime, and vertices labeled {1,…,Q1}. Connect vertex x to vertex px, where p
is a prime smaller than (log Q)^{A}.

15


16


17

 Because the random walk converges quickly, expander graphs make for
excellent random number generators.
 They can convert “bad generators” into better ones
 Rivest’s RC4 is based on expanders on permutation groups
 When the nodes represent different instances of the same problem, the
random walk can sometimes be used to show that each instance is as
“difficult” as the rest.
 Such “selfreducibility” is important in cryptography, because one wants
all versions of a given system to be hard to break.
 Recent application (Jao, Miller, Venkatesan): ensuring security of
Microsoft’s next product key (a 25 digit alphanumeric code one enters
when installing Windows or Office).

18

 Eigenvectors of adjacency matrices of graphs give good (Huckel)
approximations to wave functions
 The largest nontrivial eigenvalue of a regular graph gives a measure of
how close the graph is to being disconnected
 “Expander Graphs” – those with a large separation (spectral gap) between
the trivial and nontrivial eigenvalues  are highly desirable
 Expander graphs have important theoretical applications, as well as
emerging cryptographic utility

19

