SC700 - Modern Information Protocols

Tentative Syllabus

The following is a tentative syllabus for SC700. The actual material covered will be mitigated by the class background and progress.

I. Introduction

a) Simple data structures

b) Graphs

c) Big-oh analysis

d) Essential number theory

e) Rings

f) Finite fields

II. Compression

a) Information theory

b) Lossless

• Huffman coding

• Lempel-Ziv and variants

c) Lossy

• JPEG, MPEG

• wavelet/fractal compression

III.Error-correction

a) Background

• generator/parity-check matrix

• Shannon bound

b) Encoding

• Hamming codes

• BCH, Reed-Solomon codes, algebraic-geometry codes

• Low Density Parity-Check codes

• design and constraints

c) Decoding

• syndrome decoding

• trellis decoding

• iterative decoding, belief propagation

• code design

IV. Cryptography

a) Classical

• cipher systems

• cryptanalysis

• Kasiski test, Incidence of Coincidence

b) Private-key systems

• DES, etc.

c) Psuedo-random numbers

• exponential, LFSR

d) Public-key systems

• Merkle-Hellman, Diffie-Helman

• RSA, elliptic-curve

• McEliece

e) Attacks and weaknesses

• social engineering

• number theoretic

• Pollard rho, Quadratic sieve

• Hastad, Franklin-Reiter, Coppersmith

• implementational

• timing

• random faults

V. Information dispersion

a) resource discovery

b) data reconciliation

c) CPIsync

• deterministic

• probabilistic

• multi-round

d) Relations

• to ECC, to graph coloring

e) network synchronization

f) gossip protocols