Math/ECE 842 - Fall 2004


Nigel Boston

Contact Information

303 Van Vleck Hall or 3619 Engineering Hall.

Telephone: 263-4753 or 265-3817.

E-mail: boston@math.wisc.edu

Homepage

Office Hours: Tuesdays, 10-11 (in 303 VV), Wednesdays 11-12 (in 3619 EH), Thursdays 2:20-3:20 (in 303 VV).

Sections

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

Course Description

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.
7. Tomography, 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 ones.

Grading

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 challenge
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

Prerequisite

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. Rotman's book. 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