Math/ECE 842 - Fall 2004
303 Van Vleck Hall or 3619 Engineering Hall.
Telephone: 263-4753 or 265-3817.
Office Hours: Tuesdays, 10-11 (in 303 VV), Wednesdays 11-12 (in 3619 EH), Thursdays 2:20-3:20 (in 303 VV).
- Lecture: TR 11:00-12:15, B129 Van Vleck.
Useful Web Materials
Rob Calderbank's similar Princeton course
Practical applications of IT, including an explanation of the 56K modem
Survey of space-time coding
For many years engineers and computer scientists
have applied tools from analysis such as probability, differential
equations, ... but lately algebraic tools have found increasing
applicability. For example, the theory of curves over finite (Galois)
fields yields the best public-key cryptosystems for low power applications,
some of the best codes, and the best low-discrepancy sequences, providing
deterministic alternatives to Monte Carlo simulations (and now finding
financial applications in pricing derivatives). Space-time codebooks for
multiple antennae applications use advanced ideas from group theory and
algebraic number theory, object recognition uses invariants of Lie groups acting
on varieties, and so forth. This course will give a systematic explanation
of these tools with an emphasis on examples and applications.
More Detailed Plan
1. We begin as with Calderbank's note covering coding theory (classical,
convolutional, space-time), simultaneously using this as motivation
to introduce mathematical concepts, groups, lattices, fields, etc. (although
without proofs - for proofs see his notes or the books below).
2. Discussing of codes would not be complete without describing LDPC (and
more generally graph-based) codes, which finally answer Shannon's challenge from 1948 of obtaining practical codes with rates close to channel capacity. See
my survey lectures, with figures here. We also mention the currently hot topic of network coding, which employs some algebraic geometry.
3. Digital watermarking - in particular Quantization Index Modulation, which
uses lattices, and the Atallah-Wagstaff scheme, which uses quadratic reciprocity.
4. Cryptography. Public-key cryptography depends for its security on the
difficulty of solving some hard problem. For RSA it's the problem of factoring large integers, but using the number field sieve it's now feasible to factor 576-bit integers. In constrained environments companies are turning to elliptic curve cryptography (ECC). Private-key cryptography recently came up with a new
AES (Advanced Encryption Standard), Rijndael, but its structured nature has
drawn attacks using commutative algebra.
5. Mathematical Finance. Deterministic numerical estimates for integrals over
high-dimensional cubes (as are used in pricing tranches of mortgages) come
from finding low-discrepancy sequences. The lowest star discrepancies so far
attained come from curves over finite fields with lots of points (the same
design criterion as for good codes from algebraic geometry, i.e. Goppa codes).
Financial software companies now use these.
6. Signal Processing. Filter design and bounds (see e.g. the Makhoul conjecture challenge).
Manipulation of the transfer function of the filter leads to algebraic geometry. Transfer functions also arise in robust control theory.
generalized principal component analysis.
Both use some algebraic geometry.
8. Computer vision. Study of invariants of Lie groups acting on varieties.
Note that mathematically the same topics keep coming up again and again in
various contexts, e.g. groups and in particular finite groups of rotations in
Euclidean 3-space; lattices and in particular density questions; finite fields
and curves defined over them; algebraic number fields particularly cyclotomic
The grade will be based on a 10-20 page report due the last day of class.
The topic can be any that involves real-world applications of abstract algebra
such as above. It is suggested that you pair off, pure mathematicians with applied
students, so as to enhance the range of topics you can attempt (but the final
reports must be by individuals).
Including the links to topics already given above, here are some further suggestions.
NOTE:- P next to a topic means that a pure mathematician is wanted to work with an
applied person who has chosen this topic. A next to a topic means that an applied
person is wanted to work with a pure mathematician who has chosen this topic.
1. Information Theory in Modem Practice.
2. Applications of Geometric Algebra
3P. On the Use of Quasi-Monte Carlo Methods in Computational Finance
4P. Real algebraic geometry and convex optimization
5A. Multiple antenna applications
6P. The Makhoul conjecture
7. Code Division Multiple Access
8. Graphical codes
9. Network coding
10. AES attacks
11. Generalized principal component analysis
12. Cyclotomic fields and space-time codes
13. Implementing elliptic curve cryptography
14. Cryptography and braid groups
15. Algebraic curves and computational vision
16. Steganography and data-hiding
17. Tomography and computer algebra
18. Quantum information processing and geometric algebra
19. Quantum error-correcting codes
20. Algebraic number theory and signal constellations
Some familiarity with groups, rings, and fields will help. We'll cover the basics
and you'll see lots of examples in applications but it'll be fast.
If you wish to read up on this sort of thing in advance, one of the many books
on a first course in abstract algebra would help, see e.g.
Also the course Math 541
covers all you might need (but is not required).
Some Final Reports
Andrew Bolstad: Braid group cryptography untangled
James P.Cossey: Applications of finite group theory to multiple-antenna design
Kei Hao: Perfect space-time block codes and ultra-wideband
Jarvis Haupt: New sequences from old: a search for low discrepancy sequences
Anders Hendrickson: Space-time block codes from cyclic division algebras: an introduction
Martin Hock: Braid compression
Christopher Holden: Perfect space-time block codes
Eunmo Kang: Review and performance comparison of finite-rate feedback strategies: vector quantization, systematic unitary construction and Grassmannian packing
Sarah Knoop: Supersingular curves and the Weil pairing in elliptic curve cryptography
Wei-Yang Lin: Implementation of elliptic curve cryptography
Wei-Yang Lin: Invariants of isometric transformations
Karl Mahlburg: An overview of braid group cryptography
Harris Nover: Algebraic cryptanalaysis of AES: an overview
Michael Rabbat: Discrete-time signal processing and Makhoul's conjecture
Vasanthan Raghavan: When is limited feedback for transmit beamforming useful?
Changfang Zhu: Algebraic-geometric and probabilistic approaches for clustering and dimension reduction of mixtures of principal component subspaces