CSC 80020: TOPICS IN COMBINATORIAL ALGORITHMS: Advanced Combinatorics

Instructor: Prof. V. Pan

Weds., 4:15 - 6:15PM

3 cr., Rm. 6417

Course description: The seminar studies most effective methods in the fields of algebraic and numerical computing and focuses on the advances based on merging the methods in both fields. This relatively recent direction has been well recognized by now, but fresh research topics are still abundant. The study in the seminar has lead many students to many publications and PhD Theses (17 Theses have been defended in the last 9 years in the PhD programs in Computer Science and Mathematics.) The students who prefer just learning are also welcome, however. The subjects in the seminar can be partly adjusted to the students' interests and background.

Recently covered topics include:

a) Recent novel methods for classical matrix computations, in particular for solving large linear systems of equations and computing the eigenvalues and eigenvectors of a matrix, and the extensions and applications to computations in algebra and geometry.

b) Structured (e.g., Toeplitz, Hankel, Cauchy, Pick, and semiseparable) matrices. They are omnipresent in modern computations as well as in many areas of math, and they are closely related to fundamental algebraic computations with polynomials and rational functions.

c) Solving a polynomial equation, which was the central and most influential problem in math for 4 millennia and remains highly important in computer algebra. Some extensions to the fundamentals of the solution of systems of multivariate polynomial equations have been studied.

d) Polynomial and rational interpolation.

e) Algebraic techniques for coding and cryptography.

f) Fast and certified computation of the sign of the determinant, with applications to some fundamental geometric computations.

The seminar resumes with new topics every semester. Background knowledge is welcome but is not a prerequisite because the students are divided into the entry level group and the advanced group. The instructor usually meets separately for two hours per week with each group. The entry level students eventually join the group of advanced students.

Survey and research papers are supplied as handouts. Some relevant papers are available at the instructor's homepage at http://comet.lehman.cuny.edu/vpan/ and some as his Tech Reports at the CS Dept. in the Graduate Center. The students can also use the texts published by the instructor and available in the GC library.

The Computer Science students are encouraged to implement new algorithms devised in the seminar, and the Math students to solve the relevant open problems in math. The successful results become parts of the theses and research articles.

Last Modified on: 11/01/2006

Webmaster