Applied Math Colloquium

Error-correcting codes are combinatorial designs constructed to deal with the problem of noise in information transmission. A code describes how to judiciously add redundancy information so that if a small number of errors occur during transmission, then this can be detected. Furthermore if the number of errors that occur is even smaller, then one can even correct the errors in an information theoretic sense. In the seminal paper that introduced error-correcting codes, Hamming (1950) showed that a code is capable of detecting d errors if and only if it is capable of correcting d/2 errors uniquely. Subsequently the study of error-correcting codes has led to many codes where these tasks are achievable algorithmically.

What happens when if we try to recover from more than d/2 errors when the code designed to detect d errors? Hamming's result is often misinterpreted to suggest that this task is ill-posed. However, it turns out that there is a reasonable notion of recovery called "list-decoding" dating back to Elias (1957), where the decoding algorithm simply outputs a list of codewords that are close to a received vector. In this talk we will discuss this notion and describe some recent works that give simple and efficient list-decoding algorithms for one of the most popular family of error-correcting codes - the Reed-Solomon codes.

Joint work with Venkatesan Guruswami (MIT -> UCB -> U.Wash.)

---

About the speaker

Madhu Sudan recieved his Bachelor's degree from the Indian Institute of Technology at New Delhi in 1987 and his Ph.D. from the University of California at Berkeley in 1992. Madhu Sudan is an Associate Professor in the Department of Electrical Engineering and Computer Science at the Massachusetts Institute of Technology. He was a Research Staff Member at IBM's Thomas J. Watson Research Center in Yorktown Heights, NY from 1992 to 1997 and has been at his current position at MIT since 1997.

Madhu Sudan's research interests include computational complexity theory, algorithms and coding theory. He is best known for his works on probabilistic checking of proofs, and on the design of list-decoding algorithms for error-correcting codes. He has served on numerous program committees for conferences in theoretical computer science including STOC'95, FOCS'97, SODA'98, FOCS'01 and was the program committee chair of the IEEE Conference on Computational Complexity '01. He is currently a member of the editorial boards of the SIAM Journal on Computing, the SIAM Journal on Discrete Mathematics, and Information and Computation. Madhu Sudan is a recipient of ACM's Doctoral Dissertation Award (1993), the Alfred P. Sloan Foundation Fellowship (1997), the NSF Career Award (1998), the IEEE Information Theory Paper Award (2000), the Goedel Prize (2001), and the Nevanlinna Prize (2002).

Claude Berge proposed the conjecture in 1961 that, in every graph with no odd hole or odd antihole, the number of colours needed to properly colour the graph equals the size of the largest complete subgraph. (A "hole" means an induced subgraph which is a cycle of length >= 4, and an "antihole" is the same in the complement graph.) This has become one of the most well-known and popular open problems in graph theory. Most attempts on it have been based on linear programming methods, studying the properties of a minimal counterexample; they go a long way, but appear eventually to get stuck. Recently, however, a new approach was initiated by Conforti and Cornuejols, an attempt to actually find explicit constructions for all the graphs not containing odd holes or antiholes, and checking directly that they satisfy Berge's conjecture. I am happy to report that this works. In joint work with Maria Chudnovsky, Neil Robertson and Robin Thomas, we have been able to carry out the Conforti-Cornuejols program, and thereby prove Berge's conjecture.

A key ingredient in the solution of a large, sparse system of linear equations by an iterative method like conjugate gradients is a preconditioner, which is in a sense an approximation to the matrix of coefficients. Ideally, the iterative method converges much faster on the preconditioned system at the extra cost of onesolve against the preconditioner per iteration.

I will present a little-known technique for preconditioning sparse systems of linear equations, called support-graph preconditioning, that borrows some combinatorial tools from sparse Gaussian elimination. Support-graph preconditioning was introduced by Vaidya and has been extended by several others. I will survey the method (not assuming any background in sparse matrix computation) and then show how to use it to analyze some preconditioners based on incomplete factorization and on multilevel diagonal scaling.

I will conclude with a couple of open problems whose solutions will require both combinatorial and algebraic techniques.

This is joint work with Marshall Bern, Bruce Hendrickson, Nhat Nguyen, and Sivan Toledo.

A very classical result, with broad implications, is that the quotient of the ring of polynomials in $n$ variables, by the ideal generated by constant term free symmetric polynomials, is of dimension $n$!. We will discuss a similar problem concerning the quotient of ring $QSym$ of quasi-symmetric polynomials by the ideal (in $QSym$) generated by constant term free symmetric polynomials, and extensions of all these questions to a diagonal setup. Together with $C$. Reutenauer, we have given a whole set of conjectures boiling down to stating that $QSym$ is a free $Sym$ module. This has been shown to be true by Garsia and Wallach, but we will show that this is not the end of the question. We will then extend this question and others to the context of diagonally symmetric and diagonally quasi-symmetric polynomials.

We are interested in a generalization of a problem considered by Von Neumann: Is it possible to simulate a coin with bias f(p) given an independent sequence of coins with (unknown) bias p, where f : (0,1) -> (0,1)?

We show that f(p) can be simulated by a finite automaton if and only if it is a rational function. We show that if f(p) is simulated by a pushdown automaton, then f is algebraic, and construct pushdown automata simulating non-rational functions.

We will also discuss how this model is related to the Chomsky Schutzenberger theory, exact sampling and the theory of computability.

Joint work with Yuval Peres